Question

Un tablero de $7 \times 1$ se cubre por completo con fichas de $m \times 1$ sin superposición; cada ficha puede cubrir cualquier cantidad de casillas consecutivas, y cada ficha queda completamente sobre el tablero. Cada ficha es roja, azul o verde. Sea $N$ el número de recubrimientos del tablero de $7 \times 1$ en los que los tres colores se usan al menos una vez. Por ejemplo, una ficha roja de $1 \times 1$ seguida de una ficha verde de $2 \times 1$ , una ficha verde de $1 \times 1$ , una ficha azul de $2 \times 1$ , y una ficha verde de $1 \times 1$ es un recubrimiento válido. Nota que si la ficha azul de $2 \times 1$ se reemplaza por dos fichas azules de $1 \times 1$ , esto resulta en un recubrimiento diferente. Halla el residuo cuando $N$ se divide entre $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.$

Respuesta

Solución:

Primero cuenta los recubrimientos coloreados cuando hay $k$ colores disponibles. La ficha de la primera casilla puede colorearse de $k$ maneras, y cada una de las $6$ casillas restantes o bien extiende la ficha actual o bien inicia una ficha nueva en uno de los $k$ colores, lo que da $k + 1$ opciones por casilla. Así que hay $k(k+1)^6$ recubrimientos.

Con tres colores eso son $3 \cdot 4^6 = 12288$ recubrimientos. Por inclusión-exclusión sobre los colores no usados, el número que usa los tres colores es $\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}$

El residuo cuando $N$ se divide entre $1000$ es $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 Problema 9

Solución:

El Problema 9 en otros años