有一组8个棱长为分别为1，2，…，8的立方体。现在要用这八个立方体修建一座塔（每个立方体都必须用到），并要按照以下规则
（1）塔的最低端可出现任一个立方体；
（2）在棱长为 $k$ 的立方体上面放置的立方体棱长至多为 $k+2$ 。
令 $T$ 为可建造的不同的塔的个数，试求 $T$ 被1000除的余数。
（1）塔的最低端可出现任一个立方体；
（2）在棱长为 $k$ 的立方体上面放置的立方体棱长至多为 $k+2$ 。
令 $T$ 为可建造的不同的塔的个数，试求 $T$ 被1000除的余数。
【难度】
【出处】
2006年第24届美国数学邀请赛Ⅰ（AIMEⅠ）
【标注】
【答案】
458
【解析】
设 $S\left( n \right)$ 表示可以由 $n$ 个棱长分别为1，2，…，$n$ 的立方体按期目所述规则修建而成的塔的数目，易得 $S\left( 1 \right)=1$，$S\left( 2 \right)=2$ 。当 $n\geqslant 2$ 时，一个有 $n+1$ 个立方体修建而成的塔可以通过在任意一个有 $n$ 个立方体构成的塔中的以下三个位置插入一个棱长为 $n+1$ 的立方体而得到塔的最低端，棱长为 $n$ 或 $n-1$ 的立方体的上面因而对于每个有 $n$ 个立方体构成的塔，可以修建三种不同的有 $n+1$ 个立方体构成的塔，且每个有 $n+1$ 个立方体构成的塔可以通过移掉一个棱长为 $n+1$ 的立方体而得到一个有 $n$ 个立方体构成的塔（此外需要注意到移去棱长为 $n+1$ 的立方体时，它下面若有立方体，棱长必有 $n$ 或者 $n-1$，不会导致不满足题目所述规则）。因此，当 $n\geqslant 2$ 时有 $S\left( n+1 \right)=3S\left(n \right)$ 。因为 $S\left(2 \right)=2$，所以当 $n\geqslant 2$ 时有 $S\left( n \right)=2\cdot{{3}^{a-2}}$，因此 $T=S\left(8 \right)=2\cdot {{3}^{6}}=1458$，即所求得余数为458．
答案
解析
备注
