Question

Una colección de $8$ cubos consta de un cubo de arista $k$ para cada entero $k,$ $1 \le k \le 8.$ Se va a construir una torre usando los $8$ cubos según las reglas:

• Cualquier cubo puede ser el cubo de la base de la torre.

• El cubo que se coloca inmediatamente encima de un cubo de arista $k$ debe tener arista a lo sumo $k + 2.$

Sea $T$ el número de torres diferentes que se pueden construir. ¿Cuál es el residuo cuando $T$ se divide entre $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?$

Respuesta

Respuesta: 458

Conceptos:conteo recursivo biyección

Nivel de dificultad: 2760

Solución:

Sea $S(n)$ el número de torres legales que usan los cubos de aristas $1, \ldots, n.$ Dada una torre legal de $n \ge 2$ cubos, el cubo $n + 1$ puede insertarse en exactamente tres lugares: en la base, inmediatamente encima del cubo $n,$ o inmediatamente encima del cubo $n - 1$ (en cualquier otro lugar quedaría apoyado sobre un cubo de arista a lo sumo $n - 2,$ violando la regla). Cada inserción sigue siendo legal, porque el cubo que termina encima del cubo $n + 1$ tiene arista a lo sumo $n \lt (n+1) + 2.$ Recíprocamente, borrar el cubo $n + 1$ de una torre legal de $n + 1$ cubos deja una torre legal: el cubo que estaba encima de él, de arista a lo sumo $n,$ cae sobre un cubo de arista al menos $n - 1.$

Por lo tanto $S(n + 1) = 3 S(n)$ para $n \ge 2.$ Como $S(2) = 2$ (cualquiera de los dos cubos puede quedar arriba), obtenemos $T = S(8) = 2 \cdot 3^6 = 1458,$ y el residuo es $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 Problema 11

Respuesta: 458

Nivel de dificultad: 2760

Solución:

El Problema 11 en otros años