De todas formas, para paliar el estrés de estas fechas y simplificar nuestras vidas, hemos decidido como familia implementar un "Amigo Secreto". Este juego consiste en que cada uno de los participantes sólo le hace un regalo a uno de los otros participantes, sin que nadie revele información alguna de quién le regaló a quién. Entonces, en vez de tener que comprar cuatro regalos cada uno (somos una familia de 5), basta con que compremos uno cada uno. ¡De 20 regalos bajamos a 5 regalos!
Para jugar al Amigo Secreto, primero se escriben los nombres de cada uno de los participantes en papeles, luego se doblan los papeles de forma que escondan los nombres; en tercer lugar, se meten los papeles a una bolsa y, finalmente, cada uno de los participantes saca uno de los papeles en forma aleatoria de la bolsa y se entera así de quién será su beneficiario, sin comunicarle nada a nadie. Si a un participante le sale su propio nombre, todos deben volver sus papeles doblados a la bolsa y todos deben volver a sacar un papel de la bolsa. Esto debe repetirse hasta que nadie saque su propio nombre.
Algunas variaciones del juego permiten que un participante que saca su propio nombre devuelva el papel a la bolsa y saque otro, pero este tipo de variaciones no son apegadas a la regla básica del juego que dice que nadie puede recibir información respecto de quién regala a quién. En este caso los jugadores se enterarían de que el participante que sacó su propio nombre no es el beneficiario de ninguno de los anteriores participantes que ya sacaron papeles.
Mucha fue nuestra sorpresa cuando tuvimos que realizar seis intentos antes de que cada uno de nosotros sacara un nombre distinto al propio. Lo que parecía algo simple y obvio, resultó misteriosamente difícil, así que con mi hijo nos pusimos a hacer algunos cálculos. Después de varias horas de rompernos los sesos llegamos a la conclusión de que el número de combinaciones de N nombres que resultan exitosas para el juego del amigo secreto (es decir, que son tales que nadie saca su propio nombre), f(N), está dado por la fórmula recursiva:
f(N) = (N-1)! * [ 1 + sum{i: 2..N-2}( f(i) / i! ) ]
donde N es el número de jugadores, f(1) = 0, f(2) = 1, f(3) = 2 (ver nota al pie si te interesa entender cómo llegamos a esta fórmula)
Entonces, la probabilidad de un juego exitoso PE(N), es decir, de realizar un juego donde todos los jugadores sacan nombres que no son los suyos, se obtiene dividiendo la expresión anterior por el total de combinaciones N! :
PE(N) = f(N)/N! = (1/N) * [ 1 + sum{i: 2..N-2}( f(i) / i! ) ] = (1/N) * [ 1 + sum{i: 2..N-2}PE(i) ]
con PE(1) = 0, PE(2) = 1/2, PE(3) = 1/3 y, que al ser graficada, muestra una rápida convergencia a 37%:
 |
| Fig 1. La probabilidad de éxito del amigo secreto converge rápidamente a 37% a partir de N=5 |
Esto significa que en promedio un poco más de un tercio de los juegos resulta exitoso, lo cual no es tan alentador cuando tienes 20 personas esperando terminar el juego...
Bueno, después de todo esto nos enteramos de que existen aplicaciones en la internet que resuelven el problema al primer intento.
Moraleja: ¡siempre empieza por Google!
==============================
Nota:
Para calcular el Nº de combinaciones exitosas, f(N), en el juego del amigo secreto con N participantes, partimos por el primer participante, quien tiene N-1 posibilidades de éxito. Luego, el segundo participante tiene dos posibilidades: (1) saca el nombre del primer participante o (2) saca un nombre distinto al del primer participante y distinto al suyo.
El caso (1) se reduce entonces a un juego de N-2 participantes, dado que los dos primeros se seleccionaron mutuamente, es decir, en el caso (1) quedan f(N-2) combinaciones exitosas para cada uno de los posibles pares de participantes iniciales.
En el caso (2), el segundo participante tiene N-2 formas de sacar un nombre y dejará en la bolsa N-2 nombres que deberán combinarse en forma exitosa, pero uno de ellos no tiene riesgo de fracaso pues corresponde al nombre del primer participante. Este problema equivale entonces a calcular el número de combinaciones exitosas de N-2 nombres donde sólo hay N-3 que pueden fracasar. Llamemos a esta función g(N-2,N-3).
En resumen, el número de combinaciones exitosas f(N) se puede expresar como:
f(N) = (N-1) * ( f(N-2) + (N-2)*g(N-2, N-3) )
Pero, podemos mostrar que g(N-2, N-3) = (N-3)! * [ 1 + sum{i=3...N-2} ( f(N-i) / (N-i)! ) ], con lo cual llegamos fácilmente a la expresión formulada originalmente para f(N).
