El problema de las cartas extraviadas

Como ocurre con esos deportistas que son auténticas estrellas y se convierten en leyendas de sus deportes, en las matemáticas hay también algunos personajes que brillan y problemas que se transforman en verdaderos íconos por su origen, belleza o posterior trascendencia. Estos problemas esconden grandes enseñanzas,  pero hay que conocerlos y vale la pena hacer un pequeño esfuerzo para entenderlos y así poder disfrutarlos. Justamente ese es el valor que tiene el problema que quiero compartirles hoy, y que a mi juicio tiene todas esas características que reúnen las estrellas. 

Se trata del problema conocido bajo el nombre de “problema de las cartas extraviadas”, también conocido como “problema del guardarropa”, “problema de los sombreros”, “problema de las parejas equivocadas” o como “el problema de Bernoulli-Euler”. Los nombres corresponden a las diferentes versiones que se usan para explicarlo. Usaré el de las cartas extraviadas, pero antes de plantearlo, y para entender mejor su formulación, pensemos en un juego que se realiza con dos listas de cinco palabras cada una. En la lista de la izquierda hay palabras en alemán solamente, como lo indica la tabla siguiente, y en la lista de la derecha hay únicamente palabras en español. El juego consiste en asignar correctamente la traducción al español de cada palabra que aparece en alemán.

La respuesta correcta a este juego consiste de cinco parejas: (A, 5), (B, 2), (C, 4), (D, 1) y (E, 3). Pero pensemos en las diferentes asignaciones que se podrían haber hecho, es decir, tratemos de calcular cuántas formas existen de unir las cinco palabras del alemán en la primera columna, con las cinco del español en la segunda columnas, o sea cuántas posibles respuestas tiene el juego, aunque la mayoría sean erróneas.

Para calcular ese número tenemos que determinar de cuántas formas podemos asignar a cada una de las letras del conjunto {A, B, C, D, E}, que corresponden a las palabras en alemán, los números del conjunto {1, 2, 3, 4, 5}, que representan las palabras en español. Si, como ya se dijo, la respuesta correcta del juego planteado es la permutación (5, 2, 4, 1, 3), entonces la pregunta que tratamos de resolver ahora es ¿cuántas permutaciones son posibles? 

Para encontrar el número de permutaciones posibles basta hacer el siguiente conteo: en cada permutación que hacemos, el primer elemento tiene 5 lugares para escoger, y una vez este ha ocupado el lugar elegido, al segundo elemento le quedan quedan 4 posiciones disponibles. Cuando estos dos primeros elementos han tomado sus respectivos lugares, el tercer elemento encuentra 2 posiciones ocupadas y tiene 3 lugares libres; después, al cuarto le quedan entonces 2 posibilidades y para el último, cuando ya los demás están ubicados, le queda solo 1. Es decir que el número posible de permutaciones será: 5! = 5 x 4 x 3 x 2 x 1 = 120. 

Esto significa que el juego tiene un total de 120 respuestas posibles, pero solo una de ellas es la correcta, que como ya vimos es la permutación (5, 2, 4, 1, 3). Una pregunta más difícil de responder, pero muy interesante, es saber cuántas soluciones tiene este juego en las que no se acierta ni una sola traducción correcta, es decir, cuántas permutaciones hay en las que ninguno de los 5 elementos ocupa su lugar correcto.  

Esta pregunta nos devuelve al inicio, al famoso problema de las cartas extraviadas (simplificado a 5), que es el siguiente:

Una persona ha escrito 5 cartas a 5 personas distintas y escribe las direcciones de estas en 5 sobres. ¿De cuántas formas puede colocar las 5 cartas en los 5 sobres, de forma que todas las cartas estén en sobres incorrectos?

Para saber cuántas maneras hay de colocar las cartas en sobres que no lleven la dirección que le corresponde al destinatario, vamos a denotar con C1, C2, C3, C4, C5  las cartas y con S1, S2, S3, S4, S5 los sobres correspondientes. Ahora procedemos a encontrar el número de permutaciones posibles en las cuales ninguna carta está en el sobre que le corresponde. Llamemos D(5) ese número que queremos hallar.

Primer caso: supongamos que la carta C1 está en el sobre S2 y que la carta C2 está en el sobre S1. En este caso las demás cartas C3, C4, C5 van a estar en los sobres S3, S4, S5, pero ninguna de esas 3 cartas está en el sobre correcto. Por lo tanto el número de esas permutaciones es D(3), es decir, el número de permutaciones de 3 cartas de forma que ninguna está en el sobre correcto. 

Segundo caso: supongamos que, como en el primer caso, la carta C1 está en el sobre S2, pero que ahora la carta C2 no está en el sobre S1. Hay que distribuir entonces las cartas C2, C3, C4, C5 en los sobres S1, S3, S4, S5, de forma que C2 no esté en S1, C3 no esté en S3, C4 no esté en S4 y C5 no esté en S5. Ahora el número de formas de hacer ese reparto es D(4), es decir, el número de permutaciones de 4 cartas de forma que ninguna está en el sobre que le corresponde.

Estos dos casos nos indican que el número de permutaciones de 5 cartas en las que ninguna está en el sobre correcto, pero con la condición de que C1 está en S2, es igual a D(3) + D(4).

Ahora bien, un argumento similar, considerando dos casos cada vez, se puede usar para cuando ponemos como condición que C1 está en S3, lo mismo cuando exigimos que esté en S4 y cuando la condición es que esté en S5. 

Así que en cada uno de los 4 casos posibles para colocar la carta C1, se obtiene que el número de permutaciones de las 5 cartas en las que ninguna está en el sobre que le corresponde es igual D(3) + D(4). Entonces se concluye que el número de permutaciones de 5 cartas en las que ninguna está en el sobre correcto es:

D(5) = 4 · [D(3) + D(4)]. 

En forma general se puede demostrar, siguiendo este mismo argumento, que el número de permutaciones de n cartas en las que ninguna está en su sobre correcto es:

D(n) = (n – 1) · [D(n – 2) + D(n – 1)].           (*)

Claramente D(1) = 0, pues no es posible equivocarse colocando una carta cuando sólo hay un sobre. Y D(2) = 1, pues solo hay una forma de colocar dos cartas en dos sobres de manera incorrecta. Por lo tanto la respuesta al problema inicial sobre cuántas formas hay para colocar 5 cartas en 5 sobres, de forma que todas las cartas estén en sobres incorrectos, será:

D(5) = 4 · [D(4) + D(3)]

       = 4 · { 3 · [D(3) + D(2)] + 2 · [D(2) + D(1)] }

       = 4 · { 3 · { 2 · [D(2) + D(1)] + D(2) } + 2 · [D(2) + D(1)] }      

       = 4 · { 3 · { 2 · [1 + 0] + 1 } + 2 · [1 + 0] }

       = 4 · { 3 · { 3 } + 2 }

       = 4 · { 11 }

       = 44.

El número correspondiente para más cartas crece rápidamente:  D(6) = 265 y D(7) = 1854.

El problema fue propuesto originalmente por Pierre Rémond de Montmort (1678-1719) en su libro sobre probabilidad y juegos de azar, publicado en 1708. Nicolás Bernoulli (1687-1759) y Leonhard Euler (1707-1783), independientemente analizaron y resolvieron el problema. La demostración que dio Euler es la que arroja la fórmula recursiva (*) y fue incluida en el libro “100 Great Problems of Elementary Mathematics: Their History and Solutions”.

En el juego del inicio teníamos 5 palabras en alemán para asignarles su correspondiente traducción al español, es decir, n = 5, y vimos que el número de permutaciones era 120, o sea 120 soluciones posibles del juego, de las cuales solo una era correcta. Ahora podemos afirmar entonces que hay D(5) = 44 soluciones del juego, del total de 120 posibles, para las cuales no se acierta la traducción correcta de ninguna palabra.

Una pregunta natural, que podemos responder ahora es:

¿Cuál es la probabilidad de que a ninguna de las 5 palabras en alemán se le asigne al azar la traducción correcta? O, en el caso de las cartas ¿cuál es la probabilidad de que ninguna de las cartas se coloque en el sobre correcto, es decir, con la dirección que le corresponde?

Teniendo en cuenta que la probabilidad de que todas las cartas acaben en sobres incorrectos es igual al número de casos favorables, que es D(5) = 44, dividido entre el número de casos posibles, que es 5! = 120, dicha probabilidad es:

P(5) = 44/120 = 0,3666…

es decir, la probabilidad de no acertar uno solo de los sobres o de no dar con la traducción correcta de una sola palabra, es bastante alta, del 36,37%. Este valor es muy cercano al que resulta de dividir 1 entre el número de Euler e:

1/e = 0,36787…

Y se puede demostrar que en general, el límite cuando n tiende a infinito de P(n) es igual a 1/e. 

El problema se puede también generalizar aún más y preguntarse cuál es la probabilidad de que solo k de las n cartas vayan al sobre correcto. La respuesta a esta pregunta es:

No estaría de más agregar que teniendo en cuenta la alta probabilidad de no acertar uno solo, en este tipo de problemas, aquellos estudiantes que gustan de usar lo que se llama el “pinochazo” para responder exámenes, corren un alto riesgo de reprobar. La probabilidad de no acertar una sola respuesta correcta es superior al 36%.

Este bello problema de las cartas extraviadas es de una gran trascendencia si se tiene en cuenta que en la solución que dio Euler aparece la construcción de una sucesión en forma recursiva, método que con la aparición de los computadores en el siglo XX, se vuelve sumamente potente y de uso frecuente para la solución numérica de múltiples problemas. Además del encanto que esconde el problema, ejemplifica como pocos el conteo y la probabilidad, y tiene aplicaciones insospechadas; en efecto, recientemente, a raíz de la pandemia debida al Covid-19 conocí un trabajo en el que se usa un planteamiento similar dentro de un modelo estocástico para describir la propagación de epidemias. Más exactamente con modelos de urna en los que las personas vacunadas pueden ser “asociadas” con las cartas que están en los sobres correctos.  

@MantillaIgnacio