Más de 14 millones de formas distintas de sentarse

Ya hay solución para el vigésimo desafío matemático con el que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española (ver el vídeo conmemorativo).

Jaime Sánchez y Eva Primo, estudiantes de Matemáticas en la Universitat de València, propusieron el problema, basado en una idea de Juan Miguel Ribera, (ver vídeo de la izquierda) y lo resuelven ahora (vídeo de la derecha). Recordemos el enunciado: se consideran 35 sillas colocadas en fila y en las que están sentadas 35 personas. En un momento dado, las 35 personas se levantan y se vuelven a sentar donde estaban o en la silla de al lado (derecha o izquierda). ¿De cuántas formas distintas pueden sentarse la segunda vez las 35 personas en estas 35 sillas siguiendo esta condición?

Para este desafío, el primero del mes de agosto, hemos recibido en torno a 600 respuestas, de las cuales aproximadamente un 70% eran correctas. Efectuado el sorteo entre los acertantes, el ganador de una biblioteca matemática como la que entrega cada semana EL PAÍS ha sido en esta ocasión Valentín Echevarría Santamaría, de Salamanca. Este domingo, en el quiosco, por 9,95 euros con el periódico, Ideas fugaces, teoremos eternos, de Joaquín Navarro.

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).

El jueves plantearemos un nuevo reto.

Miles de maneras de sentarse en sillas

¡Todo el mundo a su silla!