一个有趣的矩形剖分问题

顾森

如果一个矩形能装进另一个矩形里（假设它们的对应边互相平行）。那么这两个矩形的长和宽需要满足什么样的条件呢？容易看出，前一个矩形的长必须小于等于后一个矩形的长，同时前一个矩形的宽也必须小于等于后一个矩形的宽，1973年，美国计算机科学家爱德华·莱因戈尔德提出了一个有趣的数学问题：能否把一个矩形分成若干个小矩形，使得任意一個小矩形都无法装进另一个小矩形里？简单试一试你就会发现，要想构造出这样的例子其实并不容易。

但是，问题的答案是肯定的，其中的一种方案如图l所示（为简洁起见，左下角的矩形的尺寸未标示，它为18×1），而且，如果每个小矩形的长和宽都必须是整数，那么图1就是这个问题的最小的解——整个大矩形的面积仅为22x13=286。

我们可以把莱因戈尔德的问题稍微修改一下：能否把一个正方形分成若干个小矩形，使得任意一个小矩形都无法装进另一个小矩形里？问题的答案也是肯定的，其中的一种方案如图2所示（最上面的矩形为27x1），这是目前已知的最小的解——整个大正方形的边长仅为27，究竟还有没有更小的解，仍然是未解之谜。