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!