Como se sabe, el número de subconjuntos de tamaño $k$ tomados del conjunto $\{1,2,\ldots,n\}$ se calcula con la fórmula $$C(n,k)=\frac{n!}{k!(n-k)!}$$
Puesto que este post es sobre argumentos combinatorios, empezaremos con la derivación de la fórmula de las combinaciones.
Dos modelos generales de razonamiento combinatorio
Modelo de la urna: los n objetos están dentro de una urna y se eligen k en sucesión y sin reemplazo.
Modelo de clasificación: se supone que ya se tienen todas las posibilidades --en una lista, por ejemplo-- y se procede a clasificarlas en categorías (adecuadas al objetivo de contarlas).
La definición misma de combinación refleja estos dos modelos: número de posibles elecciones de k objetos de un conjunto de n; y número de subconjuntos de tamaño k tomados de un conjunto de tamaño n.
Ambos modelos de razonamiento son experimentos imaginarios. En el modelo de la urna hay que pensar que a ésta solamente se puede meter la mano (pero no ver su interior) y los k objetos son todos de la misma forma (indistinguibles al tacto, por ejemplo esferas del mismo tamaño); se eligen al tacto los k objetos, se extraen en sucesión y sin reemplazo y se registra el resultado visual.
En el modelo de clasificación uno tiene que imaginarse que las posibilidades ya están enlistadas.
Según el modelo de la urna, los $k$ objetos se eligen en sucesión y sin reemplazo de la urna. El resultado son todas las posibles ordenaciones de $k$ elementos del conjunto $\{1,2,\ldots,n\}$ y son $n(n-1)\ldots(n-k+1)$ en número. Pero, en este conteo, cada uno de los subconjuntos de tamaño $k$ corresponde a $k!$ de esas ordenaciones (cada subconjunto de tamaño $k$ se ha contado $k!$ veces). Por tanto $k!C(n,k)= n(n-1)\ldots(n-k+1)$. De ahí el resultado.
En el modelo de clasificación, se supone que se tiene la lista de todas las ordenaciones de $k$ elementos de $\{1,2,\ldots,n\}$ y se procede a clasificarlas según sus elementos. Las ordenaciones que contienen los mismos elementos se ponen en la misma clase. Por tanto, hay $C(n,k)$ clases, una para cada subconjunto de tamaño $k$. Pero cada clase contiene $k!$ ordenaciones. De ahí que $k!C(n,k)= n(n-1)\ldots(n-k+1)$. (Notemos, de paso, que en el modelo de la urna queda ímplícito el modelo de clasificación.)
Argumentos combinatorios con fichas de dominó
En el concurso estatal de la OMM Tamaulipas 2013 se planteó el siguiente problema de combinatoria, el cual voy a tomar como pretexto para comentar sobre problemas de combinatoria con restricciones.
1C. ¿De cuántas formas se pueden elegir dos fichas, de las 28 de un juego de dominó, de tal manera que las fichas tengan un número en común? Por ejemplo, [0|2] y [2|6] tienen en común al 2. Y también, [1|2] y [1|4] tienen en común al 1.
Nota: Las 28 fichas del juego de dominó son [0|0], [0|1], [0|2], [0|3], [0|4], [0|5], [0|6]; [1|1], [1|2], [1|3], [1|4], [1|5], [1|6]; etc.
Consideraciones previas
El problema se ubica en el tema de combinaciones con restricciones. Combinaciones, es decir, el número de posibilidades de elegir k objetos de un conjunto de n objetos (en este caso k=2 y n=28). Pero, en ese problema, la elección de los dos objetos del conjunto de 28 no es irrestricta, sino que se exige que los dos objetos elegidos satisfagan una restricción: tienen que acoplarse en el sentido del juego del dominó.
Los problemas de combinatoria elementales como éste se consideran fáciles, dado que no requieren ninguna teoría para su solución (con excepción de la habilidad de enumeración de posibilidades, la de clasificación de éstas y la generalización a partir de casos). Es por esa razón que se puso en primer lugar en el concurso.
Y, sin embargo, la enumeración de posibilidades no parece ser una habilidad natural en el aprendiz y tampoco lo es la capacidad de generalización ni la de clasificación. Es decir, posiblemente esas habilidades requieran un cierto entrenamiento para que los alumnos las adquieran.
Solución vía clasificación
Supongamos que ya tenemos la lista de pares de fichas acoplables y supongamos que son A en número. Esos pares de fichas se pueden clasificar por el número a través del cual se acoplan. Son entonces 7 categorías o clases: la del cero, la del 1, etc.
Calculemos ahora cuántos pares tiene cada clase. Por ejemplo, la clase del cero tendría los siguientes elementos:
00 01
00 02
00 03
00 04
00 05
00 06
01 02
01 03
01 04
01 05
01 06
$\vdots$
04 05
04 06
05 06
En resumen, son 1+2+3+4+5+6=21 parejas.
Es fácil darse cuenta que cualquiera de las clases tiene 21 parejas. (El lector incrédulo puede continuar con la clase del 1 y si todavía no lo cree, continuar con la del 2, etc.) Así pues, cada clase tiene 21 parejas y son 7 clases. Por lo tanto, la respuesta es A=7x21=147.
Notemos las estrategias de abordaje: clasificar las posibilidades, enumerar los miembros de una clase, y generalizar. (Aparte del experimento mental de imaginar la lista de posibilidades.)
Solución vía extracción de urna
Las fichas con un cero son 7: 00 01 02 03 04 05 06 ¿De cuántas formas se pueden elegir dos de ellas? Respuesta: de 21 formas (C(7,2)). Pero lo mismo es cierto de las fichas con el uno, con el dos, etc. Por tanto, la respuesta es 7x21=147. Notemos que no se ponen todas las fichas en la urna sino solamente las que son acoplables según un número. Y con uno basta, pues la generalización se hace evidente.
(De hecho, en el modelo de la urna, uno tiene que pensar que se extrae la primera de 7 formas --cualquiera de las 7-- y después sin regresar la ya extraída, se extrae la segunda --de 6 formas. Pero estas 42 posibilidades toman en cuenta el orden de las fichas. Por lo tanto, la respuesta es la mitad de 42, es decir, 21.)
Notemos que esta solución es básicamente la misma que la de clasificación sólo que se está ahorrando la enumeración. En este sentido es más avanzada. (El aprendiz tiene que haber pasado por ejercicios de enumeración y ya está en la etapa en que se los puede imaginar y se ahorra la enumeración.)
Solución alternativa vía extracción de urna
Si tuviésemos las 28 fichas en una urna, se pueden hacer dos extracciones: saco una ficha, veo cuál es (registro el resultado visual), después saco otra (sin regresar la primera a la urna) y registro el resultado visual. Claramente el resultado de las dos extracciones puede ser favorable (las dos fichas se acoplan) o bien es desfavorable. En total las posibilidades son 28(27). Pero estaríamos contando en exceso, pues el orden en que se extaigan las dos fichas es irrelevante. Por tanto, el número de pares de fichas es realmente 14(27).
Ahora bien, no queremos todos los posibles pares de fichas sino solamente los pares que se acoplan. Para salvar esta dificultad hay que pensar en una forma de extracción de la urna que facilite el conteo.
Para ello la clave está en que una "mula" (número repetido en la ficha) se acopla según un solo número, mientras que una no mula se acopla según dos. Más precisamente, una mula se acopla con 6 fichas mientras que una no mula se acopla con 12. Considerando esto, el razonamiento con conteo excesivo sería como sigue.
Caso 1: Mula en la primera extracción
Hay 7 posibilides de extraer mula en la primera extracción y, para la segunda, hay 6 posibilidades de extraer una ficha acoplable con la mula. Por tanto, con mula en la primera, las dos extracciones son acoplables en 42 casos.
Caso 2: No mula en la primera extracción
Hay 21 posibilidades de extraer no mula en la primera extracción y, para cada una de ellas, hay 12 posibilidades de extraer una ficha acoplable en la segunada extracción. Por tanto, con no mula en la primera extracción, las dos extracciones son acoplables en 21(12) casos.
Pero estamos contando en exceso pues el orden de la extracción es irrelevante. De aquí que la respuesta sea 21+126=147 pares de fichas acoplables.
Notemos que esta solución recurre a una clasificación dicotómica (mula o no mula) para organizar el argumento (y la elección de fichas de la urna). Pero esta clasificación es más bien un "golpe de genio" que difícilmente se puede generar bajo la presión del tiempo de un examen. La emergencia de esta idea clave en el examen sería un indicio de que el alumno ya tiene entrenamiento en problemas combinatorios.
Solución mediante una ordenación ad hoc de las fichas
Si disponemos las fichas como se ve abajo, debería ser claro que un par de fichas acoplables según el número i (=0,1,2,3,4,5,6) se tienen que elegir de entre las 7 de la línea quebrada que va desde la columna i hasta la diagonal y continuando en la fila correspondiente. Por ejemplo, si i=5 el conjunto de 7 fichas son las de la columna del 5, desde la 05 hasta la 55 más la 56. Por tanto, son 7C(7,2)=147 pares de fichas acoplables en total.
00 01 02 03 04 05 06
11 12 13 14 15 16
22 23 24 25 26
33 34 35 36
44 45 46
55 56
66
Claramente esta idea de arreglar las fichas de dominó en una tabla de doble entrada sin los elementos abajo de la diagonal no es algo que se le pueda ocurrir fácilmente a un concursante. Pero si ya ha resuelto problemas parecidos, este procedimeinto es de rutina.
Otros problemas de elección restringida
1. Siete artistas han logrado un espacio en un museo de arte para exponer su obra. Siete semanas para exponer, una semana para que cada uno exponga su obra individual. Pero de última hora el museo restringe el tiempo de exposición a tres semanas para que todos expongan su obra. Los artistas forman grupos de dos o de tres y tratan así de ajustarse a la restricción de tiempo del museo y a la vez todos expongan su obra. ¿De cuántas formas se pueden formar los grupos de tal manera que dos de los artistas expongan su obra juntos?
Solución
Los dos artistas que desean estar juntos pueden estar en un grupo de dos miembros o bien en el de tres.
Si están en uno de dos miembros, la elección de posibilidades sería como sigue: se incluyen en uno de los dos de dos de dos formas y, para cada una de ellas, el equipo de tres se puede formar de C(5,3)=10 formas --los restantes dos formarán el otro equipo de dos. Por tanto, el número de posibilidades para este caso es 2(10)=20.
Por otro lado, si estuvieran en el equipo de tres miembros, el tercer integrante se elige de 5 formas (cualquiera de los 5 restantes) y, para cada una de esas cinco posibilidades, uno de los equipos de dos se forma de C(4,2)=6 formas --y los dos que quedan forman el otro equipo de dos. Por tanto, para este caso hay 5(6)=30 posibilidades.
En total hay 50 posibilidades de que los dos artistas queden juntos en un equipo. Pero con fines de exposición es importante el orden en que expongan los equipos: 223,232,322.
Así que hay 150 posibilidades de que los dos artistas expongan juntos bajo las restricciones de tiempo del museo.
2. De cuántas formas se puede elegir una mano de pokar de una baraja de 52 cartas? (Una mano de pokar es un subconjunto de 5 cartas elegidas de una baraja de 52.)
Respuesta C(52,5)
Solución
Elijo en sucesión y sin reemplazo las 5 cartas de 52(51)(50)(49)(48) formas. Pero esto toma en cuenta el orden; cada mano corresponde a 5! de ese total de posibilidades. Por tanto, 5!C(52,5)=52(51)(50)(49)(48)
3. ¿Cuántas manos de pokar tienen 4 barajas del mismo valor (pokar)?
Elijo el valor: 13 formas
Elijo las 4 del mismo valor: 1 forma
Elijo la carta restante: 48 formas
Por tanto, las posibilidades de pokar son:13(48)=624
4. Cuántas manos tienen 3 cartas de un mismo valor y dos cartas de otro valor (full house)?
Elijo el valor para las tres cartas: 13 formas
Elijo las tres del mismo valor: C(4,3)=4
Elijo el valor para las dos restantes: 12
Elijo las dos cartas del otro mismo valor: C(4,2)=6
Por tanto la respuesta es 13(4)(12)(6)=3744
5. Cuatro matrimonios han comprado boletos en la misma fila para un concierto. ¿De cuántas formas diferentes pueden sentarse en la fila
a) de manera irrestricta?
$8!=40320$
b) cada quien con su pareja?
$2^4(4!)$
c) los varones juntos a la derecha de todas las damas?
$4!4!$
6. Se tienen 10 bolsas de monedas. Todas las bolsas contienen monedas de 10gr. excepto una de ellas en que todas sus monedas son de 9 gramos. Cómo se puede identificar la bolsa de monedas de 9 gr. haciendo una sola pesada?
Solución
Tomamos una moneda de la primera bolsa, dos de la segunda, tres de la tercera,etc. y...
Los saluda
jmd
PD: En el problema 5 los matrimonios son heterosexuales.
PD2: Una pregunta adicional después de los problemas 3 y 4 sería ¿por qué el pokar le gana al full?