趣题:在指定形状的棋盘内放置n个相同的图形

上个月Erich Friedman的Math Magic提出了这样的问题:
给定一个指定形状的棋盘,给定一个大于2的整数n,找出一个面积最大的图形S使得n个S能够不重叠地装进这个棋盘里。
问题提出之后得到了不少有趣的构造,这些构造是否为最优解还有待进一步证明。

 
由三个格子组成的棋盘共有两种本质不同的形状。“长条形”已经不用多考虑,“拐角形”中n=2, 3, 6时的最优解也是非常显然的。拐角形棋盘是可以分成四等分的。但是,在这个棋盘中放置5个相同的图形就没那么容易了。已知的最优方案占据了整个棋盘约0.959的面积。放置7个相同的图形研究起来更困难一些。已知最优解为0.956。

      

 
由四个格子组成的棋盘中,L形和T字形在n=2时各有一个15/16的解;

   

Károly Hajba找到了n=5的L形棋盘目前已知的最优解,它占据棋盘约0.972的面积。

 
五个格子组成的棋盘变化更多,构造也更有趣。
n=2时有一些非常巧妙的构造,它们都是由Dick Hess发现的,面积分别为棋盘的0.928、9/10、9/10、0.871和0.864:

   

   

 
Károly Hajba找到了拐角形在n=3时目前已知的最优解0.917。

 
大家可以到这里查看一些更复杂的情况。

4 条评论

发表评论

89  +    =  99