Question

一个 $7 \times 1$ 的板完全由 $m \times 1$ 的砖覆盖且不重叠；每块砖可以覆盖任意数量的连续小方格，并且每块砖都完全位于板上。每块砖要么是红色、蓝色，要么是绿色。设 $N$ 为铺满 $7 \times 1$ 的板且三种颜色都至少使用一次的铺法数。例如，一块 $1 \times 1$ 的红砖后接一块 $2 \times 1$ 的绿砖、一块 $1 \times 1$ 的绿砖、一块 $2 \times 1$ 的蓝砖、以及一块 $1 \times 1$ 的绿砖，是一种合法铺法。注意，如果那块 $2 \times 1$ 的蓝砖换成两块 $1 \times 1$ 的蓝砖，会得到一种不同的铺法。求 $N$ 除以 $1000$ 的余数。

A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7 \times 1$ board in which all three colors are used at least once. For example, a $1 \times 1$ red tile followed by a $2 \times 1$ green tile, a $1 \times 1$ green tile, a $2 \times 1$ blue tile, and a $1 \times 1$ green tile is a valid tiling. Note that if the $2 \times 1$ blue tile is replaced by two $1 \times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000.$

答案

答案：106

知识点：铺砖容斥原理乘法原理

难度评级：2610

解答：

先数有 $k$ 种颜色可用时的彩色铺法。第一个方格所在的砖有 $k$ 种颜色可选；之后的 $6$ 个方格中，每个方格要么延续当前砖，要么以 $k$ 种颜色之一开始一块新砖，所以每个方格有 $k + 1$ 种选择。因此共有 $k(k+1)^6$ 种铺法。

三种颜色时共有 $3 \cdot 4^6 = 12288$ 种铺法。对未使用的颜色做容斥，使用全部三种颜色的铺法数为 $\begin{aligned} N &= 3 \cdot 4^6 - 3 \cdot (2 \cdot 3^6) \\ &\quad {}+ 3 \cdot (1 \cdot 2^6) \\ &= 12288 - 4374 + 192 \\ &= 8106. \end{aligned}$

$N$ 除以 $1000$ 的余数是 $106$ 。

First count colored tilings when $k$ colors are available. The first square's tile can be colored in $k$ ways, and each of the remaining $6$ squares either extends the current tile or starts a new tile in one of the $k$ colors, giving $k + 1$ choices per square. So there are $k(k+1)^6$ tilings.

With three colors that is $3 \cdot 4^6 = 12288$ tilings. By inclusion-exclusion over the unused colors, the number using all three colors is $\begin{aligned} N &= 3 \cdot 4^6 - 3 \cdot (2 \cdot 3^6) \\ &\quad {}+ 3 \cdot (1 \cdot 2^6) \\ &= 12288 - 4374 + 192 \\ &= 8106. \end{aligned}$

The remainder when $N$ is divided by $1000$ is $106.$

2013 AIME II 第 9 题

答案：106

难度评级：2610

解答：

其他年份的第 9 题