|
Solución del problema de Diciembre, 2009
| El problema: |
 |
PM91: Diciembre 2009
Blancanieves se casó con el príncipe y vivieron felices. Con el tiempo la mina cerró y los enanos se jubilaron y se mudaron a diferentes ciudades, manteniéndose en contacto por email. Se siguen juntando para hacerse regalos en Navidad, pero organizar los regalos se ha convertido en un problema. Cuando vivían juntos, sacaban nombres de una bolsa para decidir quién le hacía el regalo a quién. Pero ahora ya no pueden hacerlo porque no se ven antes de Navidad. La idea natural es que uno de los enanos se encargue de hacer el sorteo, pero esto presenta dos problemas:
- el enano que hace el sorteo sabe quién le hará el regalo a él, lo que arruina la sorpresa
- no hay garantía de aleatoriedad: el que hace el sorteo podría hacer el reparto de nombres a voluntad; esto es un problema porque Doc y Gruñón tienden a protestar
Nuestro problema de diciembre consiste en diseñar un método -- vía email -- que remplace el sorteo y que deje a todos satisfechos. Es decir, diseñe un método para que los enanos y Blancanieves intercambien información por email de manera que
- No haga falta ayuda de otras personas o de software;
- Todos terminan con el nombre de una persona a la que comprar un regalo; todos reciben un regalo, y todos hacen un regalo.
- Nadie sabe el nombre de la persona que le hace el regalo, y nadie tiene la posibilidad de decidir que X le haga el regalo a Y
Tal vez se pueda lograr un método mejor que el de la bolsa: si un enano saca su propio nombre, el sorteo debe repetirse. Intente diseñar un método en el que esto no pueda suceder.
Agradecemos a Matthieu Dufour por habernos sugerido este problema, después de que él mismo tuvo personalmente la experiencia de estar en el lugar de uno de los enanos.
|
Respuestas correctas: |
|
Recibimos soluciones correctas de
| Bojan Basic (Serbia) |
Tom Fuzzesy (Regina) |
John Campbell (Alberta) |
Magnus Jakobsson (Suecia) |
Philippe Fondanaiche (Francia) |
John T. Robinson (USA) |
y la clase de Math 20 IB class, Archbishop MacDonald High School
(Edmonton, Alberta) |
|
La solución:
Las respuestas fueron interesantes e imaginativas. Presentaremos primero la solución de John Campbell, agregaremos ideas de otras respuestas, y terminaremos con la solución de Magnus Jakobsson.
La solución de Campbell. Llamemos a los ocho participantes D(1) a D(8), con Blancanieves como D(8). En el reparto tradicional, cada participante saca el nombre de una persona para comprarle un regalo; en nuestra versión, los participantes elegirán un número que representará un participante que ellos no saben quién es.
Stage one. Se crea una columna de números al azar. D(1) comienza la columna mandándole por email un número al azar a D(2). Luego, cada participante D(i), i = 2, ..., 7, mezclará la columna de números al azar recibida de D(i – 1), insertará su nuevo número aleatorio en algún lugar de la columna, y mandará la columna resultante a D(i + 1). Finalmente, Blancanieves mezcla la columna recibida de D(7), agrega su número aleatorio en algún lugar de la columna, y manda la lista a D(1).
Etapa dos. Se crea una lista de dadores. D(1) pone su nombre junto a uno de los número aleatorios distintos del suyo, cambio su número aleatorio, mezcla la columna y la manda a D(2). El procedimiento es repetido por cada participante, hasta que Blancanieves hace lo suyo y manda la lista a D(1). Si el último número de la lista es el suyo propio, deberá informar a todos que el proceso ha fallado y debe comenzarse desde el principio.
Etapa tres. Se circula la lista. Así cada participante está seguro de saber a quién dar su regalo. Cada participante tomará nota de su número aleatorio, el participante al lado de este número es quién recibe su regalo. Luego el participante cambia su número aleatorio por otro y manda la lista al siguiente. Cuando Blancanieves recibe la lista, todos saben a quién deben hacer el regalo. Pero como cuando cada uno recibe la lista todos los números aleatorios han cambiado, nadie puede deducir los pares número-persona.
La chance de fallar en la etapa dos es uno en ocho. Para evitar esta falla, Basic y los estudiantes de Archbishop MacDonald High School usaron el hecho de que 8 es par: al final de la etapa uno, antes de mandar la lista a D(1), Blancanieves escribe "grupo A'' al lado de cuatro de los números y ''grupo B'' al lado de los restantes cuatro. En la etapa dos, los participantes que quedaron en el grupo A escriben su nombre al lado de un número del grupo B, y viceversa.
La solución de Jakobsson.
Etapa uno. Se crea una lista de dadores. Blancanieves escribe a un enano al azar “¿quieres ser el dador número 1?” Luego, para i = 1, ..., 7, cuando un enano o Blancanieves recibe el mensaje “¿quieres ser el dador número i?”, esa persona puede rechazarlo – al azar, con una moneda, o más adelante por ya haber aceptado un número – y mandarlo a otro participante al azar; o puede aceptarlo y mandar el mensaje “¿quieres ser el dador número i+1?” a otro participante al azar. Cada participante puede aceptar un solo número. La etapa termina cuando alguien acepta ser el número 8.
Etapa dos. Se crea una lista secreta de receptores. El dador número 8 manda el mensaje “¿quieres ser el receptor número 1?” a un participante al azar. Luego, para i = 1, ..., 7, cuando un enano o Blancanieves recibe el mensaje “¿quieres ser el receptor número i?” esa persona puede rechazar el mensaje y mandarlo a otro participante, o aceptarlo y mandar el mensaje “¿quieres ser el receptor número i+1?” a otro participante. Cada participante debe aceptar ser receptor solamente una vez, y el dador i no puede aceptar ser el receptor i. Para evitar que el dador 8 termine siendo el receptor 8, hay una regla adicional: nadie salvo el dador 8 puede aceptar ser el receptor 7 hasta estar seguro de que todos los participantes han recibido la invitación a ser receptor 7 (habiendo recibido la invitación de cuatro de ellos y mandado la invitación a los otros tres). La etapa dos termina cuando alguien acepta ser el receptor número 8. Este envía un email diciendo a todos “soy el receptor 8”, y aquí todos circulan su número de receptor. Ahora todos saben a quién preparar el regalo..
|
