Cartones de Bingo.

Antes de ayer participé en el Bingo Interclubes (http://www.bingointerclubes.com.ar/), no gané nada, pero la pasé muy bien. Participaron más de 40.000 personas, todas con la misma ilusión que yo: ganar alguno de los 21 premios que se sorteaban.

Una de las preguntas que me hice fué: ¿Cuántos cartones se pueden emitir sin que se repita ninguno de ellos?.

Aquí la respuesta, o al menos una aproximación. Ya que no conozco con exactitud las restricciones que tiene que cumplir un cartón, supongo algunas cosas...

Un cartón de bingo consiste en quince números, del 1 al 90. Pero no cualquier conjunto de 15 números es un cartón válido, por ejemplo: no es un cartón válido aquel que tenga los números: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,11 ,12 ,13 ,14 ,15}.

Cada cartón, está formado por 9 columnas de 3 casilleros cada una, la primer columna corresponde a números del 1 al 9, la segunda del 10 al 19, la tercera del 20 al 29,...etc, finalmente la última del 80 al 90. Cada columna puede estar rellena con 1, 2 o 3 números.
En la siguiente imagen vemos un ejemplo.



Luego de la breve introducción de lo que es un cartón vamos a tratar de contar cuantos cartones distintos se pueden emitir.

En la primer columna los número pertenecen al conjunto {1,2,3,4,5,6,7,8,9}, por lo tanto,

1. La cantidad de columnas distintas con un solo casillero lleno es: 9
2. La cantidad de columnas distintas con dos casilleros llenos es: 9*8/2!=36.
3. La cantidad de columnas distintas con tres casilleros llenos es: 9*8*7/3!=84.

Las siguientes 7 columnas, tienen un conjunto de 10 números, por lo tanto.

1. La cantidad de columnas distintas con un solo casillero lleno es: 10
2. La cantidad de columnas distintas con dos casilleros llenos es: 10*9/2!=45.
3. La cantidad de columnas distintas con tres casilleros llenos es: 10*9*8/3!=120.

Finalmente, la última columna tiene un conjunto de 11 números validos, por lo tanto.

1. La cantidad de columnas distintas con un solo casillero lleno es: 11
2. La cantidad de columnas distintas con dos casilleros llenos es: 11*10/2!=55.
3. La cantidad de columnas distintas con tres casilleros llenos es: 11*10*9/3!=165.

Ahora que tenemos las columnas contadas, falta ver cómo combinarlas, ya que la suma de números rellenos es 15.
Para contarlos hice un programa. (Lo hice en Prolog, porque es lo que últimamente estoy usando).

La cantidad de cartones me dió: 6.080.082.602.343.750 (seis mil billones).
Está mal? no lo se, me gustaría leer comentarios. Lo que si sé es que si relajamos el problema (llamémoslo:Bingo Relajado) permitiendo que el cartón este formado por cualquier conjunto de 15 números del 1 al 90. Entonces la cantidad de cartones serian: 90!/(75!*15!)= 45.795.673.964.460.816 (cuarenta y cinco mil billones). Algo está bien: la cantidad de cartones del Bingo es menor que la cantidad de cartones del Bingo Relajado.

Les dejo el programa.

% Suma los elementos de una lista
sum([], 0).
sum([H|T], Result) :- sum(T, Rest), Result is H + Rest.

:- C1 = [[1,9],[2,36],[3,84]],
C2 = [[1,10],[2,45],[3,120]],
C3 = [[1,10],[2,45],[3,120]],
C4 = [[1,10],[2,45],[3,120]],
C5 = [[1,10],[2,45],[3,120]],
C6 = [[1,10],[2,45],[3,120]],
C7 = [[1,10],[2,45],[3,120]],
C8 = [[1,10],[2,45],[3,120]],
C9 = [[1,11],[2,55],[3,165]],
findall(Z,(
member([X1|Y1],C1),
member([X2|Y2],C2),
member([X3|Y3],C3),
member([X4|Y4],C4),
member([X5|Y5],C5),
member([X6|Y6],C6),
member([X7|Y7],C7),
member([X8|Y8],C8),
member([X9|Y9],C9),
15 is X1+X2+X3+X4+X5+X6+X7+X8+X9,Z is Y1*Y2*Y3*Y4*Y5*Y6*Y7*Y8*Y9),L),
sum(L,CARTONES),
write(CARTONES).