10 × 10 的正方形最多可放入多少个直径为 1 的圆？

10 × 10 的正方形最多可放入多少个直径为 1 的圆？

知乎精选

酱紫君

可以放 106 个, 你可能会觉得, 一个框只能放一个怎么突破 100 个呢?

试着突破定势思维.

想想一个硬币最多可以和几个硬币相邻?

六个, 如果一个格子占一个才几个?

四个, 所以有大量的空间被浪费了.

这样, 就一共有 105 个了.

然后聪明的你发现还有点空隙, 能不能利用起来呢?

当然是可以的

这样安排就又多了个 10 排的, 神奇的又插了一个进去.

那么, 还能不能再用什么神奇的方法再搞一个进去呢?

不可能了...

但是如何在数学上证明不能放下 107 个圆呢? 有两种思路

  • 1.把正方形看做一个框, 把圆看成光滑的小球, 然后你取一个球, 使劲压, 看看能不能压进去.

当然现实中是没有绝对光滑小球的, 你实际没法做这个实验.

但数学上可以定义小球与小球, 小球与方框之间的势能, 然后用各种算法降低势能, 看看最小值能不能降到零即可.

  • 2.取 n 个小球, 然后放进一个方框, 方框使劲收缩, 收缩到无法再收缩为止.

最终结果就是最优平面圆堆积.这种方法比上一种要复杂一些

但是数学家一般喜欢研究第二个, 因为至少对于正方形等圆嵌入来说, 解决了第二个也就解决了第一个.对于矩形才会用第一种方法.

但这个思路说得轻巧, 可数学上怎么定义使劲收缩呢?

Talk is cheap, Show me the code!

Formulation Space Search for two-dimensional Packing Problems

这本书整理了这方面的研究成果, 第 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
查看知乎讨论