UN PROBLEMA DE GARAJES
Francisco Ayuso Selgas inaugura su
pertenencia al CARROLLSIG con un
bonito problema:
¿De cuántos modos pueden entrar n coches en n
jaulas alineadas en un garaje? Con la condición de que no quede una jaula vacía
entre alguna llena.
SOLUCIÓN AL PROBLEMA DE LOS GARAJES
Supongamos que el primer coche entre en la plaza k-sima. Quedan a su izquierda k-1 plazas, y a su derecha n-k. Cualquiera de los coches que entren a continuación hará uno de estos movimientos:
·
Situarse correlativamente a la izquierda. Lo llamaremos “movimiento I”
·
Situarse correlativamente a la derecha. Lo llamaremos “movimiento D”.
Cuando el garaje esté lleno se habrán
realizado k-1 movimientos I, y n-k movimientos D. Cada posible manera
de realizar uno u otro dará lugar a una posible forma de llenado del garaje.
El problema es isomórfico con el de disponer k-1 letras I, y n-k letras D. Por ejemplo: DDIDIIIID...IID. Esto se puede realizar
de 
formas distintas.
Por tanto, ya que el primer coche puede
ocupar cualquiera de las n
posiciones, el número total de formas posibles vale:
Observemos que esto no es más que el desarrollo de (1+1)n según la fórmula del binomio de Newton, por lo que el resultado final es:
N = 2n.
Se puede razonart de una forma más simple
aunque menos intuitiva: cada posible grupo DDIDIIIID...IID se corresponde biunívocamente
con una posible forma de ordenar los coches (observemos que conocido el grupo, a fortiori aparece incluso la colocación
del coche inicial). Es claro que el número total de posibles ordenaciones es 