Hoy me ha sucedido algo bastante curioso. A petición de un familiar he desarrollado un programa súper sencillo para realizar online el sorteo del Amigo Invisible para Navidad ya que no tenemos posibilidad de quedar físicamente para hacerlo.
Como me daba pereza pensar, he tirado por lo fácil: tenemos una lista ordenada de jugadores y otra de boletos, que al principio es igual que la de jugadores. Reordeno aleatoriamente (shuffle) la lista de boletos como quien mezcla unas cartas y compruebo que el jugador i-ésimo es distinto al boleto i-ésimo. Si para todo i se cumple esta condición, entonces sabré que todos los jugadores tienen asociado otro jugador que no es él mismo (indispensable para el Amigo Invisible) sin embargo, si no se cumple, vuelvo al inicio y hago un nuevo shuffle. Así hasta que se cumpla.
Programar eso ha sido bastante rápido, así que me he plantaeado: ¿cómo de eficiente será este programa? O dicho de otra forma: ¿cuántas veces, de media, tendrá el programa que hacer shuffle hasta dar con una combinación en la que a cada jugador le toque otro distinto de sí mismo? Dedícale un par de segundos a pensarlo considerando que hay bastantes jugadores (del orden de 100). Mi intuición me decía que, a más jugadores, más veces habrá que hacer shuffle hasta cumplir la condición. Aún así, he decidido realizar algunas simulaciones repitiendo muchas veces el experimento y calculando la media de shuffles necesarios…
…y el resultado ha sido sorprendente. Para 100 repeticiones la media me daba 2.6. He probado a aumentar el número de jugadores y el de repeticiones y tenía 2.7… Sospechando, he repetido el experimento un millón de veces (le ha llevado su tiempo) y… voilà! El número medio de shuffles que hay que hacer hasta que a todo el mundo le toque un boleto en el que no está escrito su nombre es… ¡2.718, el número e! O lo que es lo mismo, la probabilidad de que al hacer shuffle de un conjunto ordenado arbitrariamente grande ningún elemento caiga en su posición anterior parece tender a 1/e (y por tanto necesitaremos de media repetir e veces el experimento para que se cumpla la condición).
Por supuesto, esto es solo una suposición. Mediante simulación sólo podré llegar a sospechar que el número medio de veces tiende a e, pero para tener la certeza, necesito demostrarlo matemáticamente. Si tienes tiempo te animo a que lo intentes tú mismo, aunque aviso que te puedes marear un poco. Lo que nos interesa saber es, de todas las posibles reordenaciones (N!), en cuántas habrá por lo menos un elemento en la misma posición al original (llamemos a este resultado K). Entonces tendremos que (N!-K)/N! es la probabilidad de que tras un reordenamiento al azar todos los elementos estén en posiciones distintas. Esta probabilidad, con N->infinito, deberá tender a 1/e para confirmar nuestras sospechas (efectivamente pasa).
Yo intentando demostrarlo me he mareado y finalmente he tirado por Google… Si te pasa igual, el término que tienes que buscar es “derangements combinatorics”.
Es la primera vez que me encuentro con el número e de casualidad y la verdad es que me ha sorprendido.