Provincial 1997 - Nivel 2 - Problema 2

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 231
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 7
Nivel: Ñandú

Provincial 1997 - Nivel 2 - Problema 2

Mensaje sin leer por Monazo » Sab 16 May, 2020 6:30 pm

En un campamento participan $15$ chicos, todos de diferentes alturas. El último día, los $15$ deben formarse en una fila de manera tal que al comienzo de la fila estén ordenados de más bajo a más alto y, a partir de un punto, los restantes estén ordenados de más alto a más bajo. ¿De cuántas maneras se puede formar la fila?

Aclaración: El primero de la fila no es necesariamente el más bajo de los $15$ chicos.

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 231
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 7
Nivel: Ñandú

Re: Provincial 1997 - Nivel 2 - Problema 2

Mensaje sin leer por Monazo » Sab 16 May, 2020 6:42 pm

Solución
Spoiler: mostrar
Notemos que el punto de quiebre, es decir, el punto donde deja de ser creciente y pasa a ser decreciente, es en la persona más alta. Entonces pensemos que esta persona más alta se ubica en un posición fija y nos concentramos en los otros $14$. Podemos ver que cada persona tiene $2$ posibilidades, ir antes de la persona más alta, en la parte creciente, o ir después de la persona más alta, en la parte decreciente. Una vez que le determinamos a que lado tiene que ir cada persona, podemos observar que se van a distribuir de una única manera, para que se cumpla la condición de crecimiento y decrecimiento. Es por eso que el resultado final es $2^14=16384$, porque cada tipito de los $14$ tiene justamente las dos posibilidades previamente mencionadas.

PD: Habría que considerar también los casos donde todos que ubicados a la izquierda o queden ubicados todos a la derecha, obteniendo así un secuencia siempre creciente o siempre decreciente. Entonces, si estos casos no debería ser considerados, el resultado final sería $2^14-2=16382$.

Responder