Beneficios y costos de la abstracción matemática

Se tienen 7 bolas blancas y 5 negras. ¿De cuántas formas se pueden colocar las 12 en hilera sin que haya dos negras juntas?

Solución

Coloco las 5 negras. Utilizo 4 blancas para separarlas. Me quedan 3 blancas. ¿Dónde las pongo? Es decir ¿cuántas formas hay de colocarlas en la hilera de las ya colocadas? Este problema es difícil a pesar de su aparente simplicidad. Una forma de responder a la pregunta es separar en casos: coloco las tres en lugares diferentes, coloco dos juntas en un lugar y la otra en otro lugar y, finalmente, las coloco las tres en un solo lugar.

Caso 1 (las tres en lugares diferentes): puesto que las bolas son indistinguibles, los lugares disponibles son 6 (4 entre dos negras y 2 en los extremos); de esos 6 lugares escojo 3 para las 3 bolas blancas; son entonces C(6,3)=20 maneras de colocar las tres blancas en este caso.

Caso 2 (dos juntas y la otra separada): en este caso, escojo los dos lugares de C(6,2)=15 formas y después permuto de dos formas (en el primer lugar elegido puede quedar la bola separada y en el segundo las dos que van juntas, pero también puede ser al revés); en total hay 30 posibilidades para este caso.

Caso 3 (las tres juntas): en este caso, elijo el lugar de 6 maneras (cualquiera de los 6 disponibles).

La respuesta es entonces: hay 56 formas de colocar en hilera 7 bolas blancas y 5 negras sin dos negras juntas.

(Ejercicio: evaluar el siguiente argumento en cuanto a su validez "Con las 4 blancas y 5 negras ya colocadas, hay 8 espacios para colocar las 3 blancas que quedan. Por tanto, son C(8,3) maneras de colocarlas".)

Solución alternativa

Pongo las 7 blancas en línea. Las 5 negras las coloco en los 6 espacios intermedios entre blancas (uso las blancas como separadores) o en los 2 extremos. Tengo entonces 8 lugares para colocar las 5 negras. Es decir, hay C(8,5)=C(8,3)=56 formas de acomodar 7 blancas y 5 negras, sin dos negras juntas.

Comentario (sobre los dos métodos de solución)

Este último argumento (poner primero las que no tienen restricción) es más natural que el primero (en que se colocan primero las bolas restringidas a no estar dos juntas). En el primer argumento, las bolas irrestrictas juegan el papel de separadores para evitar que dos restringidas no estén juntas. Pero entonces surge el problema de qué hacer con las que sobran. Si, en cambio, coloco las irrestrictas primero, entonces las restrigidas se colocan en los espacios intermedios o en los extremos, y basta con escoger los lugares para colocarlas. (Nota: claramente el número de bolas blancas debe ser al menos el mismo que el de negras --o una unidad menor--; de otra manera, no habría suficientes lugares para colocar las negras y estarían obligadas dos negras juntas.)

Otra forma de resolver el problema de qué hacer con las tres blancas restantes es pensarlo como la distribución de r bolas indistinguibles en n cajas etiquetadas. Pero hay que saber la fórmula (combinaciones con repetición): C(n+r-1,r). Para el caso de r=3 y n=6, se tiene que el número de formas de colocar las tres bolas blancas en los 6 espacios disponibles es C(6+3-1,3)=C(8,3)=56.

Modelo conjuntista abstracto

Si codificamos 1=negra, 0=blanca, el problema se transforma a "número de 12-cadenas de 5 unos y 7 ceros". Pero éste es también el problema de encontrar cuántos subconjuntos de tamaño 5 tomados de S={1,2,...,12} carecen de consecutivos. (Hay que recordar la biyección entre n-cadenas de r unos y n-r ceros y los subconjuntos de tamaño r de un conjunto de tamaño n.)

En general, si S={1,2,...,n} y se quieren contar los subconjuntos de tamaño r sin consecutivos, el modelo de cadenas de ceros y unos permite argumentar como en el problema particular con el que empezamos: coloco los n-r ceros en hilera de una única forma, y los r unos los coloco en r lugares elegidos de entre los n-r+1. Es decir, hay C(n-r+1,r) formas de elegir un subconjunto de tamaño r sin consecutivos del conjunto S={1,2,...,n}.

Nota: El problema de las 7 blancas y 5 negras es el problema 1 de la II OMM (1988).

Los saluda
jmd

PD: Como quizá se pueda ver en el discurso de este post, el costo de la abstracción es el tiempo y esfuerzo dedicado al aprendizaje de un lenguaje; el beneficio, es un razonamiento claro y una simplificación del problema.

PD2: Visita la dokuwiki y explora los temas de combinatoria, para ello cliquea el coyote o bien entra directamente aquí

También puedes estudiar los problemas de combinatoria de la dokuwiki, cliqueando en este otro link.