Todo el mundo a su silla

Concurso de El Pais, julio de 2011

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). Observad que las esquinas sólo tienen dos movimientos posibles en vez de tres.

El desafío es: ¿De cuántas formas distintas pueden sentarse la segunda vez las 35 personas en estas 35 sillas siguiendo esta condición?

NOTA IMPORTANTE: No se trata de decir de cuántas maneras se pueden sentar 35 personas en 35 sillas, sino de cuántas maneras pueden volver a sentarse, con las reglas dadas, las 35 personas que estaban ya sentadas.

Hay que tener en cuenta que ni al principio ni al final queda ninguna silla vacía; es decir, cada silla está ocupada por una persona (y solo una).

Si la forma de calcular el número es muy complicada o larga, se puede indicar.

Solución