构造最难聚合的板块

KeyTo9_Fans

在n*n的方格阵里放置一些方块■，其余地方为空地。 把一个方块■向上、下、左、右移动到与它相邻的空地称为一步。 把所有方块以四连通的形式连在一起称为聚合。 聚合这些方块所需的最少移动步数称为聚合难度。 问： 如何放置这些方块■，使得聚合难度最大？ 建议从n=1开始做，能做多大算多大。 /* 如果觉得上面的描述不够清楚，可以在这里 http://tieba.baidu.com/f?kz=664200910 阅读具体细节。 */

〇〇

这种游戏在数学那个子学科

KeyTo9_Fans

大概是算法设计与分析方面的吧。 如果要归类的话，我承认这不太属于数学类问题，应该归为计算机类比较好。 但是我希望能从这些问题的结果中找出一些规律，然后用数学方法证明它。 这才是我要研究这些问题的最终目的。

jiaon

直观的感觉是尽量把这些方块均匀的分到方格里聚合难度最大

mathe

应该是尽量放在4个角上。只是每个角上的数目需要研究一下

mathe

比如n=4可以做到8步，如 ■□□■ □□□□ □□□□ ■□□■ 以及 ■■■■ □□□□ □□□□ ■■■■ 都是8步

mathe

我们如果先考虑对于较大的2n边形。考虑一个特殊的初始状态：4个角上都有d*d个黑方块，其它地方都没有。 那么如果最后将所有方块合并成一个2d*2d的大方块，需要移动$4d^2*2(n-d)$,这个表达式在d=2n/3的时候取到最大值。我估计这个方案很可能就是最好的方案了，而2n/3不是整数时分别检查上取整和下取整两个结果。 同样对于奇数边也应该有类似的结果。

mathe

错了，最终结果是不需要合并成大方块的

jiaon

■■■■ □□□□ □□□□ ■■■■ 不用8步，6步就可以 ■■■■ □□■□ □□■□ □■■□

KeyTo9_Fans

■■■■ □□□□ □□□□ ■■■■ 只需4步: □■■■ □■□□ □■□□ □■■■ 目前发现n=3到n=5都是直接在四个角各放一个方块就可以了，步数为4(n-2)。 但n=5有并列的最优解，同为12步: ■■□□■ □□□□■ □□□□□ ■□□□□ ■□□■■ 而且聚合难度似乎不是线性增长的，应该是平方级的。 所以估计4(n-2)的形式会在n=6的时候被打破，升级为O(n^2)的级别。