2009 AMC 12B Problema 21

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.