[答478] 正方形の個数
[答478] 正方形の個数
本問では、1辺の長さが 1cm の正方形を「正方形」、長さが 1cm の線分を「線分」ということにします。
図は、線分 29本で平面上に重ならないように正方形を 11個作った図です。
では、線分 1000本で平面上に重ならないように正方形を作ると最多で何個?
[解答]
右図のような順に、なるべく少ない線分で正方形を増やしていきます。
まず、最初の正方形を作るときに線分は4本必要です。
正方形を1個増やす場合に、
それまでの正方形が長方形状に並んでいない(欠けた部分がある)場合は2本追加することになり、
それまでの正方形が長方形状(正方形状を含む)に並んでいる場合は3本追加することになります。
そのとき、その後に、2本の線分で正方形をなるべく多く増やすことを考えれば、
長方形の長い方の辺の端に、線分を3本追加して正方形をつけることになります。
このように考えれば、正方形状に並んだ k2 個の正方形に1個増やすときと、
長方形状に並んだ k(k+1) 個の正方形に1個増やすときが線分を3本追加するときです。
右図の数は、そのようにして効率よく正方形を作る順番の1つです。
このように考えると、3本の線分の追加が必要な正方形は、
上に並んだ、2,5,10,17,26,……,k2+1,…… 番目、
斜めに並んだ、3,7,13,21,31,……,k(k+1)+1,…… 番目、
になります。
n個の正方形をつくるときに、最初の正方形以外に
上に並ぶ正方形の個数は、k2+1≦n より k≦√(n-1) だから、[√(n-1)]個、
斜めに並ぶ正方形の個数は、k(k+1)+1≦n 、(2k+1)2≦4n-3 、
k≦{√(4n-3)-1}/2 だから、[{√(4n-3)-1}/2]個 です。
最初の正方形を作るときに線分は4本必要で、
正方形を増やすのに、3本の線分の追加が必要なのは、[√(n-1)]+[{√(4n-3)-1}/2]個、
他は2本の線分の追加が必要になります。
従って、n個の正方形を作るのに必要な線分の最少数を f(n) とすれば、
f(n)=2n+2+[√(n-1)]+[{√(4n-3)-1}/2] になります。
f(n) は明らかに単調増加で、f(500)>1000 、f(470)=984 、f(480)=1004 等、
範囲を絞っていけば、f(n)=1000 となるのは、n=478 で、これが答になります。
☆ 正方形の数が k2,k(k+1) でないときは、欠ける部分に余裕があり、
例の図の 11個の正方形の場合も、その下に示したようなものも考えられます。
.