Question

一组 $8$ 个立方体中，对每个整数 $k$ $1 \le k \le 8$ 都恰有一个棱长为 $k$ 的立方体。要按照以下规则用全部 $8$ 个立方体搭成一座塔：

• 任何立方体都可以作为塔底的立方体。

• 紧放在棱长为 $k$ 的立方体上方的立方体，其棱长至多为 $k + 2$ 。

设 $T$ 为可以搭成的不同塔的数量。求 $T$ 除以 $1000$ 的余数。

A collection of $8$ cubes consists of one cube with edge-length $k$ for each integer $k,$ $1 \le k \le 8.$ A tower is to be built using all $8$ cubes according to the rules:

• Any cube may be the bottom cube in the tower.

• The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k + 2.$

Let $T$ be the number of different towers that can be constructed. What is the remainder when $T$ is divided by $1000?$

答案

答案：458

知识点：递推计数双射

难度评级：2760

解答：

令 $S(n)$ 为使用棱长 $1, \ldots, n$ 的立方体搭成合法塔的数量。给定一个由 $n \ge 2$ 个立方体组成的合法塔，立方体 $n + 1$ 恰好可以插入三个位置：塔底、紧放在立方体 $n$ 上方、或紧放在立方体 $n - 1$ 上方（若放在其他位置，它会压在棱长至多为 $n - 2$ 的立方体上，违反规则）。每种插入后仍然合法，因为最后位于立方体 $n + 1$ 上方的立方体棱长至多为 $n \lt (n+1) + 2$ 。反过来，从一个由 $n + 1$ 个立方体组成的合法塔中删去立方体 $n + 1$ 后仍是合法塔：原来在它上方的立方体棱长至多为 $n$ 会落到一个棱长至少为 $n - 1$ 的立方体上。

因此当 $n \ge 2$ 时， $S(n + 1) = 3 S(n)$ 。因为 $S(2) = 2$ （两个立方体任意一个都可以在上面），所以 $T = S(8) = 2 \cdot 3^6 = 1458$ ，余数为 $458$ 。

Let $S(n)$ be the number of legal towers using the cubes of edge-lengths $1, \ldots, n.$ Given a legal tower of $n \ge 2$ cubes, cube $n + 1$ can be inserted in exactly three places: at the bottom, immediately on top of cube $n,$ or immediately on top of cube $n - 1$ (anywhere else it would rest on a cube of edge-length at most $n - 2,$ violating the rule). Each insertion stays legal, because the cube that ends up on top of cube $n + 1$ has edge-length at most $n \lt (n+1) + 2.$ Conversely, deleting cube $n + 1$ from a legal tower of $n + 1$ cubes leaves a legal tower: the cube that was above it, of edge-length at most $n,$ lands on a cube of edge-length at least $n - 1.$

Hence $S(n + 1) = 3 S(n)$ for $n \ge 2.$ Since $S(2) = 2$ (either of the two cubes may be on top), we get $T = S(8) = 2 \cdot 3^6 = 1458,$ and the remainder is $458.$

2006 AIME I 第 11 题

答案：458

难度评级：2760

解答：

其他年份的第 11 题