Solución Desafío 20: Más de catorce millones de formas distintas de sentarse


Pulsar aquí.

La solución propuesta por Eva Primo, Juan Miguel Ribera y Jaime Sánchez es la siguiente:

La idea es empezar por un caso en el cual haya menos personas. Obviamente, si tenemos una persona y una silla, la única posibilidad es que se quede como está. Observemos qué pasa, por ejemplo, si tenemos 2 sillas y 2 personas. En ese caso se ve claramente que sólo hay dos posibilidades: que las dos personas se queden quietas, o que las dos se muevan.

Ahora miramos qué pasaría con 3 sillas y 3 personas. En ese caso, vemos que si la persona del extremo no se mueve entonces estamos en el caso anterior de 2 personas y 2 sillas; mientras que, si la persona del extremo se mueve, necesariamente, obliga a la persona de al lado a ocupar su silla vacía; por tanto, al último sólo le queda la posibilidad de quedarse quieto. Luego hay 3 posibilidades.

A continuación razonamos qué pasaría con 4 sillas y 4 personas. Veremos que se parece bastante a los casos anteriores. Si la persona de la primera silla no se mueve, el problema se reduce al caso anterior (al igual que nos había pasado antes). Por otro lado, si dicha persona se mueve, entonces obliga a la persona de al lado a ocupar su lugar, y con ello el problema se reduce a la situación que había cuando teníamos 2 sillas y 2 personas. Por tanto, habrán 5 posibilidades; es decir, 3 más 2.

Así, inductivamente, llegamos a la conclusión de que las distintas formas en las que pueden sentarse “n” personas en “n” sillas vienen dadas por la suma de los dos casos anteriores, es decir, el “n-1” y el “n-2”. Por ejemplo, el caso de 4 sillas y 4 personas se resolvía sumando las formas posibles del caso 3 y el caso 2.

Por lo tanto, para nuestro caso con 35 sillas la solución vendría dada por la suma de las formas posibles en los casos de 33 y 34 sillas.

Y, si somos más perspicaces aún, nos podemos dar cuenta de que los famosos números de Fibonacci han surgido en la solución del mismo; cómo podemos observar: 1, 2, 3, 5,… Lo cual es evidente, ya que el hecho de que un término venga dado por la suma de los dos anteriores es precisamente la definición de la sucesión de Fibonacci. Y en el caso de 35 personas y 35 sillas la solución sería el número de la serie de Fibonacci, 14.930.352 es decir, el que ocupa el lugar 36º.

La sucesión de Fibonacci fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos. También aparece en configuraciones biológicas, como, por ejemplo, en las ramas de los árboles, en la disposición de las hojas en el tallo, en la flora de la alcachofa o en el arreglo de un cono.

Se han recibido bastantes respuestas con este mismo razonamiento y distintas maneras de presentarlo, la mayoría observando que era el 36º término de la serie de Fibonacci. Algunos, por ejemplo, lo han programado recursivamente mediante una hoja de cálculo, mientras que otros han utilizado algunas fórmulas conocidas al comprobar que se trataba de la sucesión de Fibonacci.

Pero hay más demostraciones posibles. Entre las respuestas correctas que utilizan otro tipo de argumentos, queremos destacar las que razonan utilizando métodos combinatorios, es decir, sumando las combinaciones posibles en caso de que se muevan una pareja, dos parejas,…

Otro método utilizado en la resolución, ha sido ver la relación de Fibonacci (obtener un término como suma de los dos anteriores) con el uso de ecuaciones en diferencias finitas, resolviendo el problema mediante la búsqueda del término general de las mismas.

Cabe señalar que, del 30% de respuestas incorrectas, la mitad tenían problemas con el cálculo del 36º término de la sucesión de Fibonacci, aportándonos el valor anterior o posterior de dicha sucesión. Otros, sin embargo, se olvidaron de incluir el caso en el que nadie se movía de su silla (todos se volvían a sentar en su posición inicial).

Deja un comentario

Archivado bajo OTROS

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s