10*10的正方形裡，最多可以放多少個直徑為1的圓？不是100個！

為什麼不是

100個

昨天文章發出後，後臺也收到了許多留言，大家也針對末尾的題目，給出了不同的答案。

五花八門的答案，究竟哪一個才是正確的呢？現在就讓小天來給大家揭曉吧。

答案是106個。

在昨天的題目中，我們故意放了下圖，其實就是想看看大家能否試著突破定勢思維。

大家想想。一個硬幣最多能和幾個硬幣相鄰？

六個 ，那如歌一個格子放一個硬幣，那是佔幾個呢？

四個，這也意味著有大量的空間被浪費了。

所以，重新排列後，這樣就有105個圓了。

然後聰明的你是不是發現還有空隙？那就將它利用起來！

這樣安排就又多了個10排的，神奇的又插了一個進去。

那麼，還能不能再用什麼神奇的方法再搞一個進去呢？

不好意思，不可能了...強扭的瓜不甜，強塞的圓不……

我們現在來用數學證明不能放下107個圓呢？有兩種思路

• 1、把正方形看做一個框，把圓看成光滑的小球，然後你取一個球，使勁壓，看看能不能壓進去。

當然現實中是沒有絕對光滑小球的，實際沒法做這個實驗。

但數學上可以定義小球與小球，小球與方框之間的勢能，然後用各種算法降低勢能，看看最小值能不能降到零即可。

• 2、取n個小球，然後放進一個方框，方框使勁收縮，收縮到無法再收縮為止。

最終結果就是最優平面圓堆積，這種方法比上一種要複雜一些。

但是數學家一般喜歡研究第二個，因為至少對於正方形等圓嵌入來說，解決了第二個也就解決了第一個。對於矩形才會用第一種方法。

但這個思路說得輕巧，可數學上怎麼定義使勁收縮呢？

Talk is cheap, Show me the code!

https://bura.brunel.ac.uk/bitstream/2438/7455/1/FulltextThesis.pdf

這本書整理了這方面的研究成果，第72頁討論了圓塞入正方形，後面還有更難的不相等圖形塞進不規則邊框。

書中沒給結果，算法都是偽代碼，不用完全看懂公式也能復現。

運算時間要有心理準備，一次差不多要跑半個小時。

計算結果表明106個直徑為1的圓能放進邊長9.996960840529825的正方形

但是如果要放置107個直徑為1的圓就要邊長10.09975184413619的正方形

所以確實10*10的正方形只能塞下106個直徑為1的圓。

注意有輕微的形變，比如右下那個沒對齊，上邊框第五個圓脫離了邊框，但是隻有0.4%，整體上和原來差不多。

最後，附上全部的繪圖代碼：

t1=Flatten[Table[{i,j},{i,1,19,2},{j,1,19,2}],1];

Append[Circle/@t1,

{EdgeForm[Dashed],RGBColor[0,0,0,0],Rectangle[{0,0},{20,20}]}

]//Graphics

f10=Circle/@Table[{i,#},{i,1,19,2}]&;

f9=Circle/@Table[{i,#},{i,2,18,2}]&;

Join[

Table[{f10[1+(i-1)Sqrt[3]]},{i,1,11,2}],

Table[{f9[1+i Sqrt[3]]},{i,1,10,2}],

{EdgeForm[Dashed],RGBColor[0,0,0,0],Rectangle[{0,0},{20,20}]}

]//Graphics

Join[

Table[{f10[1+(i-1)Sqrt[3]]},{i,1,5,2}],

Table[{f9[1+i Sqrt[3]]},{i,1,4,2}],

Table[{f10[4Sqrt[3]+3+(i-1)Sqrt[3]]},{i,1,5,2}],

Table[{f9[4Sqrt[3]+3+i Sqrt[3]]},{i,1,4,2}],

{f10[19]},

{EdgeForm[Dashed],RGBColor[0,0,0,0],Rectangle[{0,0},{20,20}]}

]//Graphics

pts={

{-8.99696,-8.99696},{-8.99696,-5.39534},{-8.99696,-1.93124},{-8.99696,0.0687576},{-8.99696,3.53286},

{-8.99696,6.99696},{-8.99696,8.99696},{-8.03644,-7.23071},{-7.99696,-3.66329},{-7.99696,1.80081},

{-7.99696,5.26491},{-7.,-5.50556},{-6.99713,-8.97132},{-6.99696,-1.93124},{-6.99696,0.0687576},

{-6.99696,3.53286},{-6.99696,6.99696},{-6.99696,8.99696},{-6.,-7.23761},{-6.,-3.77351},{-5.99696,1.80081},

{-5.99696,5.26491},{-5.,-5.50556},{-5.,-2.04146},{-5.,-0.0414576},{-4.99729,-8.99696},{-4.99696,3.53286},

{-4.99696,6.99696},{-4.99696,8.99696},{-4.,-7.23961},{-4.,-3.77351},{-4.,1.69059},{-3.99696,5.26491},

{-3.,-5.50556},{-3.,-2.04146},{-3.,-0.0414576},{-3.,3.42264},{-2.99746,-8.97113},{-2.99696,6.99696},

{-2.99696,8.99696},{-2.,-7.23761},{-2.,-3.77351},{-2.,1.69059},{-2.,5.15469},{-1.,-5.50556},{-1.,-2.04146},

{-1.,-0.0414576},{-1.,3.42264},{-1.,6.88675},{-1.,8.88675},{-0.997623,-8.99696},{0.,-7.23961},{0.,-3.77351},

{0.,1.69059},{0.,5.15469},{0.996961,6.99696},{0.996961,8.99696},{1.,-5.50556},{1.,-2.04146},{1.,-0.0414576},

{1.,3.42264},{1.00221,-8.97093},{1.99696,5.26491},{2.,-7.23761},{2.,-3.77351},{2.,1.69059},{2.99696,3.53286},

{2.99696,6.99696},{2.99696,8.99696},{3.,-5.50556},{3.,-2.04146},{3.,-0.0414576},{3.00204,-8.99696},

{3.99696,1.80081},{3.99696,5.26491},{4.,-7.23961},{4.,-3.77351},{4.99696,-1.93124},{4.99696,0.0687576},

{4.99696,3.53286},{4.99696,6.99696},{4.99696,8.99696},{5.,-5.50556},{5.00187,-8.97074},{5.99696,-3.66329},

{5.99696,1.80081},{5.99696,5.26491},{6.,-7.23761},{6.99696,-5.39534},{6.99696,-1.93124},{6.99696,0.0687576},

{6.99696,3.53286},{6.99696,6.99696},{6.99696,8.99696},{7.00169,-8.99696},{7.99696,-7.12739},{7.99696,-3.66329},

{7.99696,1.80081},{7.99696,5.26491},{8.99696,-8.85945},{8.99696,-5.39534},{8.99696,-1.93124},{8.99696,0.0687576},

{8.99696,3.53286},{8.99696,6.99696},{8.99696,8.99696}

};

Echo[m = Max@First@Transpose@pts + 1, "Min: "];

Append[

Circle /@ pts,

{EdgeForm[Dashed], RGBColor[0, 0, 0, 0], Rectangle[{-m, -m}, {m, m}]}

] // Graphics

所以，你現在知道它為什麼只能塞進106個圓了嗎？

閱讀更多 超級數學建模 的文章

關鍵字: 算法 題目 定勢