n=17正方形パッキングのための、さらに改善された下限値

2026/08/21 n=17正方形パッキングのための、さらに改善された下限値 今回のアイデアは、最近の結果を改善し、4.5058(?)≤s(17)を証明することです。これには以下の重みを使用します。 しかし、まずs(17)を定義しましょう。このトピックに関する古い記事から引用します。 s(n)を、n個の単位正方形を詰め込むことができる最小の正方形の辺長とします。n=16の場合、最適なのは明らかに4x4のアレイなので、s(16)=4です。 n=15の場合、15個の単位正方形も明らかに4x4の正方形に収めることができるので、s(15)≤4です。これが最小の正方形であることを証明するのは全く簡単ではありません。いずれにせよ、Erich Friedmanは1999年にこれを証明したので、s(15)=4です。 n=17の場合、明らかな外接正方形は5x5ですが、1998年にJohn Bidwellは4.6756…の正方形で十分であることを示す例を見つけました。したがって、s(17)≤4.6756…です。これは非常に興味深い配置なので、他の数値のバージョンと共に、コレクションを見る価値があります。 一方、Trevor Greenは2000年に4.4452…≤s(17)を証明しました（詳細は後述）。そのため、4.4452…≤s(17)≤4.6756…という大きなギャップがありました。 数週間前、Sam BurnsがChapGPT 5.6 Solと共に下限値を改善しました（？）。新しい下限値はまだコミュニティによってレビューされていません。私はそれを確認しましたが、非常に理にかなっており、正しいと考えていますが、証明や付随するプログラムの小さなコーナーケースを見落としているか、あるいは大きな欠陥を見落としている可能性があります。念のため数値に小さな（？）を付けますが、私はかなり楽観的で確信しているので、半分のフォントサイズのみを使用します。したがって、現在の境界は4.4452…≤4.4811(?)≤s(17)≤4.6756…です。 Sam Burnsの提案に対する私の主な異論は、本当に素晴らしいグラフィックに値するということです！そこで私の最初のステップは、ここに素晴らしいグラフィックを追加することです。また、プログラムにいくつかの改善を加えたところ、新しい下限値4.5058を見つけました。これで、4.4452…≤4.4811(?)≤4.5058(?)≤s(17)≤4.6756…となります。私の新しい例とコードの修正はここにありますが、新しい下限値を見つけるためのより技術的な詳細は、2番目の投稿の一部です。 Trevor Greenの下限値 Trevor Greenの古い証明（(19+40*sqrt(2))/17≅4.4452…≤s(17)）のアイデアは、4.4452…の正方形内に16個の非常に興味深い「避けられない」点を選び、その後、多くの幾何学を用いて、任意の単位正方形が少なくとも1つの点を含まなければならないことを証明することです。したがって、そこに17個の単位正方形を詰め込もうとすると、少なくとも2つの単位正方形が16個の興味深い点のいずれかを共有しなければなりません。この構成は、4x6グリッドから16個の点を選択します。 私は古い記事で点の画像を見つけただけですが、分析的な定義は見つけられませんでした。正方形の辺の長さの式を見て、規則といくつかの推測を使用すると、左/右の空きマージンは0.5で、上/下の空きマージンはsqrt(2)-1/2≅0.9142…であると思います。これらの選択により、元のグラフィックの対角線セグメントの長さは1となり、避けられない点の頂点を持つ三角形を作成するのに非常に役立つ数値です。（確認を聞けると嬉しいです。） これは、0.9142…と0.5000のマージンを持つ6x4グリッドを使用しており、グリッドの合計サイズは2.6168…と2.4452…です。 新しい構成と比較するために、対称化するのがより良いです。この対称化されたバージョンでは、各単位正方形は少なくとも4つの点を含みますが、一部の点は太く、二重点としてカウントされます（詳細は後述）。 Sam Burnsの下限値 ChatGPTを使用して4.4811(?)≤s(17)を証明するアイデアは、268個のやや興味深い点を4.4811の正方形内に選びます。これらの点には異なる重みがあり、合計の重みは16.9476です。いくつかの削減の後、有限個の方向のみをテストすればよく、Pythonプログラムを使用して「すべて」の可能な「ほぼ単位」（実際には.9973）正方形をテストし、各正方形内の重みの合計が少なくとも1（実際には1.0003）であることを確認します。したがって、そこに17個の単位正方形を詰め込もうとすると、少なくとも2つの単位正方形が268個のやや興味深い点のいずれかを共有しなければなりません（詳細は2番目の投稿で）。この方法には偽陰性があります。ソリューションを検証すれば、それは確かに正しいですが、プログラムが失敗した場合、間違いである可能性はごくわずかです。これは、重みが下限値を証明することを保証するのに適しています。 重みがどのように選択されたかは明確ではありません。このソリューションを古い記事のすべての例と比較すると、0.5のマージンは狭すぎます。なぜなら、ほとんどの例では約1.0または約9.1などを使用しているからです。重みの選択は私に同意しており、グリッドの最初/最後の行/列のすべての重みはゼロです。私の手っ取り早い意見では、2番目/最後から2番目の行/列も空であるべきですが、グリッドの(1, 11)には非ゼロの重みがあり、対称画像もあります。それがより良い例では必要ないことを願っています。3番目/最後から3番目の行/列はかなり満たされています。古い例よりも境界に近いので、下限値を改善するために境界近くにもっと点を追加することが良いアイデアのように思えます。 RacketとMetapictパッケージを使用して画像をレンダリングしました。各円の半径は、重みからr = sqrt(weight^(1/gamma)) * scaleとして計算されます。gamma = 1.0の場合、面積は重みに比例しますが、小さな重みは画像では小さすぎます。いくつかの調整の後、gamma=2.0は、小さな重みが見やすくなるため、見栄えが良いです。スケールはそれほど神秘的ではなく、どこかでpiを使用すべきでしたが、scale=0.07は私のマシンでは見栄えが良いです。円は半透明なので、スケールを上げると重なりが見える可能性があります。コードは下にあり、重みを1.0003（実際の最小合計）で割っています。 新しい下限値 私のアイデアは、マージンと内部グリッドサイズのさまざまな組み合わせを試すことでした。前述のように、Sam Burnsの例で重みがどのように選択されたかは明確ではありません。したがって、固定されたサイズごとに、それらを見つけるために線形計画法を使用することにしました。 その後、ブルートフォース検索と運の組み合わせを使用して、見つけられる最良のグリッドを取得しました。その後、重みを丸めて、見栄えが良く、きれいな分数になるようにしました（詳細は2番目の投稿で）。 かなりの時間を費やした後、最良の結果は4.5058(?)≤s(17)でした。新しいソリューションは、4.5058の辺を持つ正方形内に168個のやや興味深い点を使用し、29x29のグリッドです。それらの合計はわずか16.9166…です。各単位正方形は、少なくとも合計重み1を含みます。 0.77565のマージンがあり、内部グリッドの合計辺は3.9545です。前述のように、重みは、以前の例の2番目/最後から2番目の行/列の近くにある、古い例で予想していたよりも境界に近い位置にあります。また、重みの数が少ないため、コンピューターなしで正しいことを証明するのが容易になることを願っています。非対称バージョンを作成したいと考えており、それはさらに良くなる可能性があります。 Sam Burnsが公開したプログラムは、空のマージンが0.5であると仮定しているため、任意の境界と変数M（マージンの2倍）を許可するようにわずかに変更する必要がありました。その変更、新しいサイズ、および新しい重みテーブルを備えたバージョンは下にあります。そのプログラムを実行し、Sam Burnsが投稿した説明に明らかな変更を加えることで、新しい下限値が証明されます（？）。 結論と今後の作業 分布は角でかなり離散的に見えますが、中心近くに奇妙なバーがあります。グリッドサイズを増やして確認するのは良いでしょう。また、狭い空きマージンが役立つようです。 2番目の記事で公開されている私の検索プログラムは遅すぎます（約1時間）。そのため、グリッドサイズの変更は避けました。興味深い偶然がある場合、他のグリッドサイズを探索することは有用かもしれません。より多くの桁を追加するのは数分しかかかりませんでしたが、グリッドの洗練や回転の方向を増やす方が大きな変化をもたらすように思われたため、気にしませんでした。 この結果は、s(18)、s(19)、s(20)の下限値も自動的に改善します。しかし、これらの値についてより深い検索を行うと、さらに良い下限値が得られるはずです。合計重みが18になるケースを何度も見ました。18には何か興味深いことがあります。 非対称バージョンを見つけたいです。試すアイデアがいくつかあるので、数日中に再度確認してください。非対称バージョンは、おそらく重みの1/8程度になるでしょう。