怪兽分裂

iseemu2009

      在一个三维坐标网格中，位于格点 (x, y, z) 的一只怪兽，在目标格点 (x+1, y, z), (x, y+1, z) 和 (x, y, z+1)都是空位的情况下，可以将自身分裂成三只怪兽占据它们，并且使 (x, y, z) 恢复空位。若三个目标点中任何一个被占位时它不能分裂。
      开始时只有一只怪兽位于原点 (0, 0, 0), 经过 n 次分裂之后（任何 1 只发生分裂就记为 1 次)，格阵中将会分布有 2n+1 只怪兽, 对应一个 2n+1 点的占位点集。记 `S_n` 为经过 n 次分裂后所有可能的占位点集之集，记D(n)=|`S_n`|。
      例1、`S_1`={{(1,0,0), (0,1,0), (0,0,1)}},   D(1)=1.
      例2、`S_2`={{(0,1,0), (0,0,1), (2,0,0), (1,1,0), (1,0,1)},
                      {(1,0,0), (0,0,1), (1,1,0), (0,2,0), (0,1,1)},
                      {(1,0,0), (0,1,0), (1,0,1), (0,1,1), (0,0,2)}}
                D(2)=3.
       已知 D(10) =44499，D(20) =9204559704，而D (100) 的末尾九位是780166455，求D(1000) 的末尾九位。  

hujunhua

可以重新定义“次”而提出另外一个问题。假定每秒发生一次分裂，每次都有最多的怪兽同时发生分裂，规则如下：
1、当两只怪兽有一个公共目标点时，当前最多只能有其中一只发生分裂。
2、发生分裂的怪兽，恢复的空位可以立即被本秒发生的分裂占据。（快速规则）
2'、发生分裂的怪兽，恢复的空位只能被下一秒发生的分裂占据。（慢速规则）
记 a(n)、a'(n)分别为快速规则和慢速规则第 n 秒发生分裂的怪兽数，求这个序列。

iseemu2009

问题加上计时规则后会变得更复杂了。到后面怪兽越来越多时，考虑哪些能分裂，哪些不能，很费脑力。

hujunhua

可以先降到二维来研究。试了一下，快速规则似乎唯一性更好，慢速规则歧路多。