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}$

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

Solución:

El Problema 21 en otros años