盒子太小放不下？再挤挤？

本文从一道简单的美国中学生数学竞赛(AMC)试题入手, 联想到其在现实生产生活中的应用场景, 进而提出一连串疑问, 并逐步揭示一类经典的优化问题及其结论.

值此中秋佳节, 看完这道数学题, 你会联想到什么呢？

我们将问题翻译成一个具有现实背景的应用题:

问题

现将块半径相同的月饼以下图方式摆放在一个圆形包装盒内, 假设月饼半径为, 求月饼盒的半径.

那么在计算出如上摆放情况下的大圆半径后, 我们很自然地会联想到这样一个问题：

能不能找到一个更小的大圆装下这个小圆且能保证它们两两不重叠？

关于个等圆的最优摆放已有相关结论：

Fodor ^[1] 在2003年证明了包含两两不重叠的单位圆的最小大圆半径为, 且小圆的最优摆放有如下两种方案, 两种方案大圆的半径是一致的.

方案A

方案B

下面我们来介绍方案B的摆放方式, 并求出此时的大圆的半径.

首先将个小圆两两外切围成一圈, 然后将余下个小圆置入圈内, 我们看到个小圆位置可以在一定范围内自由活动.

要得到大圆半径, 只要考虑外围个小圆即可.

连结个小圆的圆心可得一个边长为的正边形, 其与大圆具有相同的几何中心, 大圆半径等于中心到小圆圆心(正变形的顶点)的距离加小圆半径. 所以只需要再求出正边形顶点到中心的距离即可.

连结圆点与相邻两个顶点, 过中心做边上的高, 由等腰三角形三线合一, 通过直角三角形, 可求出顶点到中心的距离为, 故可得大圆半径为.

思考题

能否通过计算得到以下摆放时大圆的半径呢？

推而广之, 如果将个小圆推广到个小圆, 那么这就是经典的等圆包装问题了.

定义 ( 平面圆内等圆包装问题 )

找到半径最小的圆, 使个半径为且两两不相交的圆都在其内部或与其内切.

这个问题最早于1960年代提出并在当时解决了较小()情况, 直到2000年左右, 随着计算机算力的大幅提升, 很多优化算法得以实现, 包装问题自此得到了极大的发展.

2020年, 任何一台个人计算机跑一段小程序就可以轻松得到圆内等圆包装的最优解 ^[2].

由其衍生的一大批更复杂的问题借助计算机得到了解决, 比如方形容器的等圆包装问题, 网上已经有一个数据库提供查询时的最优结果 ^[3].

另外还有不相等圆的包装问题 ^[4].

脚注

F. Fodor, The Densest Packing of 13 Congruent Circles in a Circle, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry 44 (2003) 2, 431–440. ⬅
stackoverflow-controlled-circle-packing-with-python ⬅
The best known packings of equal circles in a square (up to N = 10000) ⬅
Controlled Circle Packing with Processing ⬅
本文最早于2020年10月发布于橘子数学公众号.