[答478] 正方形の個数

[答478] 正方形の個数


　本問では、１辺の長さが 1cm の正方形を「正方形」、長さが 1cm の線分を「線分」ということにします。

　図は、線分 29本で平面上に重ならないように正方形を 11個作った図です。

　では、線分 1000本で平面上に重ならないように正方形を作ると最多で何個？


[解答]

　右図のような順に、なるべく少ない線分で正方形を増やしていきます。

　まず、最初の正方形を作るときに線分は４本必要です。

　正方形を１個増やす場合に、

　それまでの正方形が長方形状に並んでいない(欠けた部分がある)場合は２本追加することになり、

　それまでの正方形が長方形状(正方形状を含む)に並んでいる場合は３本追加することになります。

　そのとき、その後に、２本の線分で正方形をなるべく多く増やすことを考えれば、

　長方形の長い方の辺の端に、線分を３本追加して正方形をつけることになります。

　このように考えれば、正方形状に並んだ k² 個の正方形に１個増やすときと、

　長方形状に並んだ　k(k＋1) 個の正方形に１個増やすときが線分を３本追加するときです。

　右図の数は、そのようにして効率よく正方形を作る順番の１つです。

　このように考えると、３本の線分の追加が必要な正方形は、

　上に並んだ、2，5，10，17，26，……，k²＋1，…… 番目、

　斜めに並んだ、3，7，13，21，31，……，k(k＋1)＋1，…… 番目、

　になります。

　ｎ個の正方形をつくるときに、最初の正方形以外に

　上に並ぶ正方形の個数は、k²＋1≦n より k≦√(n－1) だから、[√(n－1)]個、

　斜めに並ぶ正方形の個数は、k(k＋1)＋1≦n 、(2k＋1)²≦4n－3 、

　 k≦{√(4n－3)－1}/2 だから、[{√(4n－3)－1}/2]個 です。

　最初の正方形を作るときに線分は４本必要で、

　正方形を増やすのに、３本の線分の追加が必要なのは、[√(n－1)]＋[{√(4n－3)－1}/2]個、

　他は２本の線分の追加が必要になります。

　従って、ｎ個の正方形を作るのに必要な線分の最少数を 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 で、これが答になります。


☆ 正方形の数が k²，k(k＋1) でないときは、欠ける部分に余裕があり、

　例の図の 11個の正方形の場合も、その下に示したようなものも考えられます。

.