Paradojas que no lo son: coincidencias de barajas [Colaboración]

Esta entrada es una colaboración de nuestro amigo Carlos Vinuesa, a raíz de la conferencia sobre magia y matemáticas que impartió en Sevilla a principios de junio y que pudisteis disfrutar también en vídeo.

---

Seguramente estés familiarizado con la conocida paradoja de los cumpleaños. Por si no fuera el caso, te informo de que es fácil demostrar que:

En una reunión de 23 personas la probabilidad de que al menos dos de ellas cumplan años el mismo día es superior al 50%. Si en la reunión hay más de 60 personas la probabilidad es mayor que el 99%.

En realidad lo anterior no es una paradoja porque no lleva a una contradicción lógica, sino que es algo contrario a la intuición de la mayoría de las personas. Por algún motivo, lo que la mayoría de las personas pensamos en un primer momento cuando tenemos que comprobar si habrá dos personas en un grupo de 23 con el mismo cumpleaños, es si cada una de las otras 22 personas cumplirá años el mismo día que la primera. Sin embargo, hay en realidad comparaciones posibles...
Para más detalles sobre la paradoja de los cumpleaños --entre ellos la sencilla prueba de la afirmación en negrita--, basta con que busques en Internet y encontrarás literalmente miles de entradas relacionadas.
El tema que nos ocupa hoy es uno bastante relacionado con el anterior en cierto sentido. Es un hecho conocido por la comunidad mágica que:

Si se mezclan dos barajas de cartas y a continuación se reparten simultáneamente las cartas de cada una de ellas, se observa que un gran porcentaje de las veces hay al menos una carta que ocupa la misma posición en las dos barajas.

La gracia está en determinar qué significa un gran porcentaje de las veces. En libros de magia se pueden leer cosas como: "A veces no sucede a la primera pasada de cartas y es necesario volver a barajar y empezar por segunda vez. Nunca, sin embargo, se necesitarán más de dos intentos para obtener este resultado".
¿Seguro? Vamos a ver cuál es la probabilidad de que se produzca la coincidencia planteada. Adoptaremos una aproximación de suspense y no de sorpresa, así que adelantamos que la probabilidad de que al mezclar dos mazos de cartas (da igual españolas que de póquer o que mezclemos dos paquetes iguales de 13 cartas) haya alguna carta en la misma posición en los dos mazos es muy cercana a
De hecho, es cierto el siguiente resultado.
Teorema: Dados dos mazos idénticos de cartas mezclados, la probabilidad de que alguna carta esté en la misma posición en los dos mazos es exactamente 
Observemos que   y que  , pues tenemos una serie alternada con términos que disminuyen en valor absoluto. Entonces el teorema nos dice que la probabilidad de coincidencia es con un error más pequeño que . Luego para grande (digamos a partir de 10, por ejemplo) la probabilidad de que alguna carta coincida en la misma posición es con un error pequeñísimo, no dependiendo la probabilidad apenas de (el número de cartas de cada mazo), lo cual podría ser también poco intuitivo (al menos a mí no me parece muy intuitivo). Observemos también que es curiosa la frecuencia con la que aparece el número en contextos inesperados. Vamos a demostrar el teorema.
Demostración: Una vez mezclados los dos mazos, decimos que el orden de las cartas del primero de ellos es el bueno. La primera carta es la carta 1, la segunda es la carta 2 y así sucesivamente. Entonces, considerando las cartas del otro mazo con esta numeración, es como si hubiéramos mezclado un mazo con cartas numeradas y nos preguntáramos si habrá alguna carta en la posición que coincide con su número.
Una permutación que no deja fijo ningún elemento se llama desbarajuste. Nosotros estamos interesados en la probabilidad de que una permutación de no sea (o sí sea, igual nos da) un desbarajuste. Como sabemos de sobra, el número de permutaciones de elementos es . Calcularemos el número de desbarajustes usando el principio de inclusión-exclusión.
El principio de inclusión-exclusión (abreviado con las graciosas siglas PIE) no es otra cosa que la generalización del hecho de que el número de elementos de la unión de y es el número de elementos de más el número de elementos de menos el número de elementos de la intesección de y (como la intersección se cuenta dos veces al sumar los elementos de y , hay que restarla una vez). El PIE nos dice que cuando tenemos uniones de más conjuntos, tras sumar los elementos de cada conjunto y restar los de las intersecciones de dos, hay que sumar luego las intersecciones de tres, restar las intersecciones de cuatro, sumar las de cinco...
Con eso en mente, es fácil calcular el número de desbarajustes de elementos. Si llamamos
al conjunto de las permutaciones de elementos con el número en la posición , el número de desbarajustes de elementos será 
El tamaño de cualquiera de los es , pues "el "' ya está fijo y los otros podemos ordenarlos de cualquier manera. Hay intersecciones 2 a 2 y cada una de ellas tiene tamaño y así sucesivamente. Luego, el principio de inclusión-exclusión nos dice que:

  
  
Así, la probabilidad de que una permutación sea un desbarajuste es  , que es lo que queríamos probar. 
Por lo tanto, para mazos con un número de cartas no muy pequeño, la probabilidad de que ninguna carta coincida en la misma posición es muy cercana a $$1/e = 0,367\dots$$ La probabilidad de que realizando dos veces el experimento ninguna coincida es muy cercana a $$1/e^2 = 0,135\dots$$ (que no es exactamente nunca). Y así sucesivamente.
En relación con la paradoja de los cumpleaños, este resultado también es bastante contrario a la intuición de la mayoría de las personas. Por algún motivo, todos pensaríamos que la probabilidad de que haya una coincidencia en un mazo de 52 cartas es algo así como $$1/52$$, porque al igual que nos ocurría con lo de los cumpleaños, pensamos sólo en una carta y en la probabilidad de que la carta idéntica del otro mazo coincida en esa posición. Por el mismo motivo, quizá, podríamos pensar (como ya hemos comentado) que la probabilidad de coincidencia depende fuertemente del número de cartas y también sabemos que no es así.
Por supuesto, puedes usar esta intuición generalizada en tu favor, haciendo apuestas con algún pringadillo, siempre y cuando mandes un porcentaje de las ganancias a quien esto escribe, que, dicho sea de paso, en todo momento negará haberte incitado a ello.
¡Hasta la próxima!

---

Tito Eliatron Dixit
PD: Esta entrada participa en la Edición 3.14159 del Carnaval de Matemáticas cuyo anfitrión es el blog Scientia.