Problema 2, regiones 2008 (La cola del teatro)

La cola tiene que simbolizarse de alguna manera. Una forma de hacerlo es pensarla como una cadena de ceros y unos: un 1 si billete de 50, y un 0 si billete de 100. Con esta codificación, el problema se transforma en este otro: ¿cuántas cadenas de 3 ceros y 4 unos son tales que en cada posición el número de ceros nunca excede al de unos?

El problema así planteado se puede resolver por enumeración exhaustiva:

(los billetes de 50 primero: 1)

(las ordenaciones que inician con 3 billetes de 50: 3)

(las que inician con 2 billetes de 50: 5)

(las que inician con un billete de 50: 5)

Y ya. Porque las cadenas que empiezan con cero atoran la cola al empezar. En resumen, la respuesta es: 14 ordenaciones de las personas en la cola, no se detienen a ésta por falta de cambio.

b) Con la misma codificación en ceros y unos, el número de ordenaciones de la cola –considerando solamente personas de dos tipos según su billete—se calcula eligiendo el lugar de los 3 ceros (tres personas con billete de 50) de entre los 7 lugares posibles. Y ya sabemos que esto se calcula como . La respuesta es entonces: hay 35 ordenaciones posibles de las 7 personas en la fila.

Método de diagrama de árbol (a=50 pesos, b=100 pesos) –aportado por David: