一个大圆里能放多少个小圆？世界难题等圆packing简介

前段时间，有人在微头条里，说长期疫情假后，很多学生都懈怠了，自家孩子勤快，自己给自己出题再解答。

然而那个题一看，是世界难题。不知道他家孩子给出的解答长什么样。

有很多题目，看起来很浅显，没上过学的人都能理解，但要得到精确的结果非常困难。

这是个什么题目呢?

半径为R的大圆内，最多可以放多少个半径为r的圆？

也可以换个问法：

n个半径为r的圆，放在一个大圆内，大圆的半径至少是多少？

当然这些小圆最多相切，不能相交。

该问题被称作packings of equal circles in a circle问题，亦即圆内等圆填充问题，常简称等圆packing问题。

由于不能重叠，也有用圆柱体的表述。可考的最早的论文就是1967年S. Kravitz的论文Packing cylinders into cylindrical containers, Math. Mag. 40 (1967) 2, 65–71.

如果是正方形那很好密铺，但圆不规则。

稍微有点数学敏感性的人都会想到，取圆的外接正六边形，可以按照蜂窝来密铺。

这个想法很好，问题是大圆的边界仍然是不规则的。在蜂窝的边界需要裁剪，可能还有更好的答案。

如图所示，四个小圆，可以放在(1+sqrt(2))r的大圆内，想要按照蜂窝式排布的话反而需要(1+sqrt(3))r，别的方法可能会更大。

2000年8月，有人用计算机列举了n<=200的可行解，2008年，n<=600的可行解被列出。

但这些可行解并没有达到最优，不断有人给出了一些n的新纪录。

怎样用计算机求解这个问题呢？我们把n视为已知，求最小的R.

为方便起见，小圆的半径取为1.

设所有小圆的坐标为(x_i,y_i)，那么圆不重叠就是

(x_i-x_j)^2+(y_i-y_j)^2>=1 (i不等于j)

我们把大圆放在原点上，希望 max (x_i^2+y_i^2)最小，如果它的最小值是K,那么sqrt(K)+1就是一个可行的R.

这样，问题就成了不等式约束下的极值问题，可以利用一些已知的数值算法来处理，不过仍然非常复杂。

到2014年，已经列出了n<=4495的可行解，但其中一部分又经常被刷新记录。