这里仅指向最大化最小距离和部分装箱问题。 关于最大化最小距离的类型，我们可以提出一个上界，然后不断对其进行压缩。而证明这个上界存在的最好办法就是反证法：假设存在一个构型使每个点的距离都大于n，然后通过对容器形状等固定的基本事实证明假设不成立，所以“必有两点距离小于等于n”。但这个上界可能不是最优。证明它是最优的方法中最通用的就是找到一个构型，它的最小距离恰好为n。 但也正如开头所写，这个方法“仅指向最大化最小距离”，像P51这样的复杂题目，虽然也能用“上界”这个思想，但具体的方法是非常复杂的。这就是为什么我从近一个月前开始搞P51 n=2证明到现在仍有缺陷＞﹏＜ 而装圆的部分装箱问题是可以转化成最大化距离做的，准确说就是把这个图形的每个边向内平移相同距离后得到的新边组成的图形与原来的图形相似的图形。转化之后的每个点对应位置就是每个圆的圆心，每个边向内平移的相同距离是半径，最大化的距离是圆的直径。利用好这个可以证明很多较为简单的题目。比如我就用这个方法证明了P82 m=6 n=3。 而这个方法是不适用于装其他图形的，因为它们的中心离边的距离有长有短。比如单位正方形，它的中心离边的距离就在1/2至sqrt(2)/2之间晃荡不定。证明这种图形是没有任何通用方法的。 但还是有一种方法几乎对任何装箱问题都适用（只要能出现这种情况）。它就是：满铺法。很明显，当一个容器里已经彻底被装满了，一丁点儿缝隙都没有，那么它当然就无法改进了。（特别地，对绝大部分容器装圆，正好是无法出现这种情况的 O_o ） 这就是我对目前的关于部分问题的证明方法的总结。如果你觉得我的表述有哪里有错误，或者要补充，欢迎各位在帖子下回复。
Back to community · Conversation
关于证明方法的讨论（The Conversation about the ways to prove）
Here applies only to maximizing the minimum distance and to some packing problems. For problems of maximizing the minimum distance, we can propose an upper bound and keep tightening it. The best way to prove that such an upper bound holds is by contradiction: suppose there is a configuration in which every pair of points is more than n apart; then, using basic facts determined by the container shape, one shows that this assumption cannot hold, so there must be two points at distance at most n. However, this upper bound may not be optimal. The most general way to prove that it is optimal is to find a configuration whose minimum distance is exactly n. But as I wrote at the beginning, this method applies only to maximizing the minimum distance. For a complicated problem such as P51, although the idea of an upper bound can still be used, the specific method is very complicated. That is why my proof of P51 for n=2, which I started almost a month ago, still has flaws. >﹏< Some circle-packing problems can be transformed into a maximum-distance problem. More precisely, translate each side of the original figure inward by the same distance; the figure formed by the new sides is similar to the original figure. After this transformation, each point corresponds to the center of a circle, the common inward translation distance is the radius, and the distance being maximized is the diameter of the circles. Making good use of this, one can prove many relatively simple problems. For example, I used this method to prove P82 m=6, n=3. However, this method does not apply to packing other shapes, because the distance from their centers to the sides varies. For example, for a unit square, the distance from its center to the boundary varies between 1/2 and sqrt(2)/2. There is no general method for proving results for such shapes. Still, there is one method that applies to almost any packing problem, provided that this situation can occur: the complete tiling method. Obviously, once a container is completely filled and not even a tiny gap is left, it certainly cannot be improved. In particular, for most containers packed with circles, this situation happens to be impossible. O_o This is my summary of the current proof methods for these problems. If you think there is any mistake in my explanation, or if you have something to add, feel free to reply below.