Question

Diez mujeres se sientan en $10$ asientos en fila. Las $10$ se levantan y luego se vuelven a sentar usando los $10$ asientos, cada una en el asiento en el que estaba antes o en un asiento contiguo al que ocupaba antes. ¿De cuántas maneras pueden volver a sentarse las mujeres?

Ten women sit in $10$ seats in a line. All of the $10$ get up and then reseat themselves using all $10$ seats, each sitting in the seat she was in before or a seat next to the one she occupied before. In how many ways can the women be reseated?

$89$

$90$

$120$

$210$

$2^{38}$

Respuesta: A

Conceptos:recursión Fibonacci

Nivel de dificultad: 2160

Pista pequeña:

Sea $S_n$ el número de reacomodos válidos de $n$ mujeres; considera la elección de la mujer más a la derecha.

Let $S_n$ count the valid reseatings of $n$ women; consider the rightmost woman’s choice

Pista grande:

Si se queda, deja $S_{n-1}$ maneras; si se mueve a la izquierda se fuerza un intercambio, y quedan $S_{n-2}$ maneras, así que $S_n = S_{n-1} + S_{n-2}$ .

If she stays she leaves $S_{n-1}$ ways; if she moves left a swap is forced, leaving $S_{n-2}$ — so $S_n = S_{n-1} + S_{n-2}$

Solución:

Sea $S_n$ el número de reacomodos válidos de $n$ mujeres. La mujer más a la derecha o bien conserva su asiento, dejando $S_{n-1}$ maneras para las demás, o bien intercambia con su vecina de la izquierda, la única otra forma de ocupar el asiento del extremo, dejando $S_{n-2}$ maneras.

Así $S_n = S_{n-1} + S_{n-2}$ con $S_1 = 1$ y $S_2 = 2,$ lo que da los valores de Fibonacci $1, 2, 3, 5, 8, 13, 21, 34, 55, 89.$ Por lo tanto $S_{10} = 89.$

Por lo tanto, la respuesta correcta es A.

Let $S_n$ be the number of valid reseatings of $n$ women. The rightmost woman either keeps her seat, leaving $S_{n-1}$ ways for the rest, or swaps with her left neighbor — the only other way to fill the end seat — leaving $S_{n-2}$ ways.

Thus $S_n = S_{n-1} + S_{n-2}$ with $S_1 = 1$ and $S_2 = 2,$ giving the Fibonacci values $1, 2, 3, 5, 8, 13, 21, 34, 55, 89.$ So $S_{10} = 89.$

Thus, the correct answer is A.

2009 AMC 12B Problema 21

Respuesta: A

Nivel de dificultad: 2160

Pista pequeña:

Pista grande:

Solución:

El Problema 21 en otros años