El problema de las cartas extraviadas es una de las joyas clásicas de la probabilidad. A partir de una pregunta elemental sobre asignaciones incorrectas, descubrimos una elegante recurrencia, una inesperada relación con el número e y aplicaciones que van mucho más allá de los juegos de azar.
Como ocurre con aquellos deportistas que alcanzan la categoría de leyenda, en las matemáticas también existen personajes que brillan con luz propia y problemas que, por su origen, su belleza o su trascendencia, terminan convirtiéndose en auténticos íconos. Detrás de ellos se esconden valiosas enseñanzas, pero para apreciarlas es necesario conocerlos y hacer un pequeño esfuerzo por comprenderlos. La recompensa bien vale la pena. Precisamente ese es el caso del problema que quiero compartirles hoy, un problema que, a mi juicio, reúne todas las cualidades que distinguen a las verdaderas estrellas.
Se trata del problema conocido como «el problema de las cartas extraviadas», aunque también recibe otros nombres, como «el problema del guardarropa», «el problema de los sombreros», «el problema de las parejas equivocadas» o «el problema de Bernoulli-Euler». Estas denominaciones corresponden a las distintas versiones utilizadas para explicarlo. Aquí usaré la de las cartas extraviadas, pero antes de plantearlo, y para comprender mejor su formulación, pensemos en un juego con dos listas de cinco palabras cada una. En la lista de la izquierda aparecen palabras en alemán, como muestra la tabla siguiente, mientras que en la de la derecha aparecen palabras en español. El objetivo consiste en emparejar correctamente cada palabra alemana con su traducción al español.
A. Montag
1. Hablar
B. Hilfe
2. Ayuda
C. Zwölf
3. Negro
D. Sprechen
4. Doce
E. Schwarz
5. Lunes
La respuesta correcta de este juego está formada por cinco parejas: (A, 5), (B, 2), (C, 4), (D, 1) y (E, 3). Sin embargo, pensemos en todas las asignaciones que podrían haberse realizado. Dicho de otro modo, tratemos de calcular de cuántas maneras es posible emparejar las cinco palabras en alemán de la primera columna con las cinco palabras en español de la segunda. En otras palabras, ¿cuántas respuestas posibles tiene el juego, aunque la mayoría de ellas sean incorrectas?
Para calcular ese número, debemos determinar de cuántas maneras es posible establecer una correspondencia entre las letras del conjunto {A, B, C, D, E}, que representan las palabras en alemán, y los números del conjunto {1, 2, 3, 4, 5}, que representan las palabras en español. Como ya se indicó, la respuesta correcta del juego es la permutación (5, 2, 4, 1, 3). El problema consiste entonces en determinar cuántas permutaciones de los números 1, 2, 3, 4 y 5 existen en total.
Para determinar cuántas permutaciones son posibles, basta con contar de cuántas maneras pueden ordenarse los cinco números 1, 2, 3, 4 y 5. El primer lugar puede ocuparse de 5 formas distintas. Una vez elegido el número que ocupará esa posición, para el segundo lugar quedan 4 posibilidades. Cuando los dos primeros lugares ya han sido ocupados, el tercero puede llenarse de 3 maneras diferentes. Del mismo modo, para el cuarto lugar quedan 2 opciones y, finalmente, para el último solo queda 1.
Por consiguiente, el número total de permutaciones es
5 × 4 × 3 × 2 × 1 = 120.
En consecuencia, el juego admite 120 respuestas posibles, aunque solo una de ellas corresponde a la asignación correcta de las traducciones.
Una pregunta más difícil de responder, pero especialmente interesante, es averiguar cuántas respuestas posibles tiene este juego en las que no se acierta ninguna traducción. En términos matemáticos, se trata de contar cuántas permutaciones existen en las que ninguno de los cinco elementos aparece en su posición correcta.
Esta pregunta nos devuelve al punto de partida: el famoso problema de las cartas extraviadas, en este caso con solo cinco elementos. Su formulación tradicional es la 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 determinar de cuántas maneras pueden colocarse las cartas en sobres distintos de aquellos a los que van dirigidas, denotemos por C1, C2, C3, C4 y C5 las cartas, y por S1, S2, S3, S4 y S5 sus respectivos sobres. Nuestro objetivo es contar las permutaciones en las que ninguna carta queda dentro del sobre que le corresponde. Denotaremos por D(5) el número de tales permutaciones.
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 cartas C3, C4 y C5 deben distribuirse entre los sobres S3, S4 y S5, pero ninguna puede quedar en el que le corresponde. Por lo tanto, el número de tales permutaciones es D(3), es decir, el número de formas de distribuir esas tres cartas entre esos tres sobres de forma que ninguna quede en el sobre correcto.
Segundo caso: supongamos que, como en el caso anterior, la carta C1 está en el sobre S2, pero que ahora la carta C2 no está en el sobre S1. Debemos distribuir entonces las cartas C2, C3, C4 y C5 entre los sobres S1, S3, S4 y S5, de manera que ninguna quede en el sobre que le corresponde. El número de formas de realizar esta distribución es D(4), es decir, el número de permutaciones de cuatro cartas en las que ninguna ocupa su sobre correcto.
Los dos casos anteriores abarcan todas las posibilidades cuando la carta C1 está en el sobre S2. En efecto, una vez fijada esa condición, solo pueden ocurrir dos cosas: o bien la carta C2 está en el sobre S1, caso que aporta D(3) permutaciones, o bien C2 no está en S1, caso que aporta D(4) permutaciones. Por consiguiente, el número de permutaciones de las cinco cartas en las que ninguna queda en el sobre correcto y, además, C1 está en S2, es D(3) + D(4).
Ahora bien, el mismo razonamiento puede aplicarse cuando imponemos la condición de que la carta C1 esté en el sobre S3. Del mismo modo, puede repetirse cuando C1 está en S4 o en S5. En cada uno de estos casos, el número de permutaciones en las que ninguna carta queda en el sobre que le corresponde es también D(3) + D(4).
Como la carta C1 puede introducirse en cualquiera de los cuatro sobres que no le corresponden, se concluye que el número total de permutaciones de cinco cartas en las que ninguna queda en el sobre correcto es:
D(5) = 4 · [D(3) + D(4)].
En forma general, siguiendo este mismo razonamiento, puede demostrarse que el número de permutaciones de n cartas en las que ninguna queda en el sobre que le corresponde satisface la siguiente recurrencia:
D(n) = (n – 1) · [D(n – 2) + D(n – 1)]. (*)
Claramente, D(1) = 0, pues no es posible equivocarse al colocar una carta cuando solo hay un sobre. D(2) = 1, ya que existe una única forma de distribuir dos cartas en dos sobres de manera que ambas queden en sobres incorrectos.
Para responder la pregunta inicial sobre cuántas formas hay de colocar cinco cartas en cinco sobres de manera que todas queden en sobres incorrectos, basta aplicar sucesivamente la recurrencia (*):
A medida que aumenta el número de cartas, la cantidad de distribuciones en las que ninguna queda en el sobre correcto 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 ahora podemos responder es la siguiente:
«¿Cuál es la probabilidad de que a ninguna de las cinco palabras en alemán se le asigne al azar la traducción correcta?»
O, en la versión de las cartas:
«¿Cuál es la probabilidad de que ninguna de las cartas termine en el sobre que le corresponde?»
Teniendo en cuenta que la probabilidad de que todas las cartas terminen en sobres incorrectos es igual al número de casos favorables, que es D(5) = 44, dividido entre el número total de casos posibles, que es 5! = 120, obtenemos:
P(5) = 44/120 = 0,3666…
Es decir, la probabilidad de no acertar ni un solo sobre, o de no asignar correctamente la traducción de ninguna palabra, es del 36,67 %, un valor sorprendentemente alto.
Además, este resultado es muy cercano al que se obtiene al dividir 1 entre el número de Euler e:
1/e = 0,36787…
El problema puede generalizarse aún más. En lugar de preguntarnos cuál es la probabilidad de que ninguna carta llegue al sobre correcto, podemos preguntarnos cuál es la probabilidad de que exactamente k de las n cartas terminen en el sobre que les corresponde. De manera equivalente, en la versión de las traducciones, podemos preguntarnos cuál es la probabilidad de acertar exactamente k de las n palabras. La fórmula siguiente proporciona precisamente esa probabilidad:
No estaría de más agregar que, en este tipo de problemas, los estudiantes que acostumbran recurrir al llamado «pinochazo» para responder los exámenes corren un riesgo nada despreciable. La probabilidad de no acertar una sola correspondencia supera el 36 %, de modo que el fracaso absoluto resulta bastante más probable de lo que podría pensarse a primera vista.
Este bello problema de las cartas extraviadas posee una notable trascendencia histórica y matemática. Basta observar que en la solución propuesta por Euler aparece una sucesión definida de manera recursiva, una herramienta que, con la llegada de los computadores en el siglo XX, adquirió una enorme importancia y se convirtió en un recurso fundamental para la resolución numérica de innumerables problemas.
Más allá de su elegancia intrínseca, el problema constituye un magnífico ejemplo de la estrecha relación entre el conteo y la probabilidad, y ha encontrado aplicaciones que a primera vista resultarían insospechadas. De hecho, a raíz de la pandemia de Covid-19 conocí un trabajo en el que una idea muy similar se emplea dentro de un modelo estocástico para describir la propagación de epidemias. Más concretamente, se utilizan modelos de urna en los que los individuos vacunados desempeñan un papel análogo al de las cartas colocadas en los sobres correctos.
@MantillaIgnacio
Ignacio Mantilla Prada
Matemático
Profesor
Dr. Rer. Nat.
Rector 2012 – 2018
Universidad Nacional de Colombia
Este blog está dedicado principalmente a la divulgación matemática. Su objetivo es acercar al público general conceptos, resultados, paradojas, acertijos, curiosidades, problemas, relatos históricos, noticias e ideas matemáticas, presentándolos de forma accesible, rigurosa y clara. Aspira a tender puentes entre el conocimiento especializado y el interés del lector no experto, mostrando la belleza, la utilidad y las sorpresas que esconden las matemáticas.
Los editores de los blogs son los únicos responsables por las opiniones,
contenidos, y en general por todas las entradas de información que deposite en el mismo. Elespectador.com no
se hará responsable de ninguna acción legal producto de un mal uso de los espacios ofrecidos. Si considera
que el editor de un blog está poniendo un contenido que represente un abuso, contáctenos.