sábado, 27 de agosto de 2011

Todo el mundo a su silla

Enunciado

Cuando se trata de calcular un número muy grande, lo primero que debemos hacer es reducirlo a situaciones más controlables (dos sillas, tres sillas, y cosas así).

Si sólo tenemos dos sillas, únicamente tenemos dos formas de sentarse.

Con tres sillas, si dejamos fijo uno de los de la esquina, hay dos formas de sentarse. Si se desplaza a la silla de al lado, sólo hay una forma de sentarse. en total, tres.

Con cuatro sillas, de nuevo tenemos la posibilidad de fijar el de la esquina, y entonces reducimos el problema a tres sillas (3) y si lo movemos, eso obliga al siguiente a sentarse en la silla vacía, con lo que quedan dos posibilidades para las dos sillas restantes (5 en total).

Tras darle muchas vueltas, me he dado cuenta de que una forma de reducir el problema a una situación inferior (quitar una o dos sillas) es tener en cuenta que, si el último de la fila (el que ocupa la posición número 35) no se mueve, tendremos que contar con las formas que tiene de sentarse 34 personas en 34 sillas siguiendo esas condiciones, y si cambia de silla, como sólo se puede poner en la 34, el de la silla 34 es el único que puede situarse en la silla 35, ya que no hay otro que la tenga al lado, y el número de situaciones posibles serán las formas de sentarse las restantes 33 personas en las restantes 33 sillas.

Dicho de otra manera, si llamamos S(N) al número de formas que existen de sentarse N personas en N sillas de la forma indicada, entonces S(N+1) = S(N) + S(N-1). Esta famosa fórmula es la de las sucesiones tipo Fibonacci, y como podemos suponer que S(0) = 1 (por convenio) y es fácil ver que S(1) = 1 y que S(2) = 2 (con lo que el convenio está justificado), en realidad esta sucesión es la de Fibonacci adelantada en uno (la de fibonacci empieza por 0, 1, etc.).

Ahora, calcular esta sucesión es otro problema distinto, si disponemos de una calculadora, podemos incluso utilizar la fórmula explícita exponencial, pero creo que estaréis esperando únicamente el resultado, es decir S(35), que es, si no me equivoco, 14930352.

Nota: he tenido que corregir la estimación inicial, pues me había equivocado en un término de la sucesión de fibonacci.

No hay comentarios: