Soluciones (segunda parte)

Diego Uribe

Soluciones (segunda parte)
por Diego Uribe

Los propios límites

Muchas veces uno se plantea límites inexistentes. Mis propios límites me impidieron resolver con elegancia el siguiente acertijo.

En un país donde todo objeto enviado por correo que no está dentro de una caja cerrada con candado es invariablemente robado, Adán desea enviarle a Eva un regalo. Tanto Adán como Eva disponen de una gran variedad de candados. Lamentablemente, Adán no tiene llave de ninguno de los candados de Eva y viceversa. El cuestión es: ¿cómo hace Adán para que Eva reciba el regalo? Algunas aclaraciones. Los protagonistas están impedidos de encontrarse. Todo envío debe hacerse exclusivamente por correo (no personalmente) con candado cerrado con llave (en este país no hay candados con combinación). Eva debe poder usar el regalo; no basta con que reciba una caja que no puede abrir con el regalo adentro. Además, si se envía una caja con un candado sin cerrar o que en el correo puedan abrir, se robarán el candado más lo que la caja contenga.

solución

Markelo encontró una elegante solución al acertijo: «Adán coloca su regalo dentro de una caja, la cierra con candado y la envía por correo. Eva recibe la caja, le agrega un candado propio y se la devuelve a Adán por correo. Adán la recibe, quita su candado y vuelve a enviársela a Eva. Eva la recibe, abre su candado, mira el regalo y le envía una carta a Adán diciéndole que ella lo hubiera preferido de color rojo.» Lamentablemente, como la carta no iba en caja cerrada con candado, en el correo se la roban. Eva nunca entenderá por qué Adán persiste en enviarle regalos color patito.

Markelo cuenta que llegó a la solución al detectar una asimetría en el problema: si el que debía enviar el regalo era Adán, ¿para qué necesitaba Eva candados? Esto lo llevó a superar el límite que me detuvo a mí: una caja puede estar cerrada por más de un candado. Si se hace simétrico al acertijo, de manera que Adán y Eva deseen enviarse regalos mutuamente, el procedimiento de Markelo resulta similar al inventado por Diffie-Hellman para enviar un número secreto a través de un medio público; por ejemplo, el correo del acertijo.

Para entenderlo se requiere el concepto de módulo. El valor de x módulo y (x mod y) se obtiene restando y de x tantas veces como se pueda. El resto que queda es el valor buscado. Por ejemplo, 23 mod 5 = 3, porque 5 entra 4 veces en 23 y queda un resto de 3. Entonces:

• Adán, Eva o un tercero eligen un número primo p un número g al que llamaremos base. Estos números son públicos y podrán comunicarse por el medio que se desee. Supongamos que p = 19 y g = 2.

• Adán elige un número a y no se lo dice a nadie. En el acertijo, esto equivale a meter el regalo en la caja.

• Adán eleva a la base g a la potencia a; luego calcula el valor de ese resultado módulo p. Supongamos que Adán elige a = 6. Entonces, 2^6 = 64 (2^6 significa 2 elevado a la sexta potencia); 64 mod 19 = 7. Esto equivale a poner un candado en la caja.

• Adán comunica públicamente su resultado 7. En el acertijo, Adán envía por correo a Eva la caja.

• Eva elige un número b y realiza con él las mismas operaciones que Adán. Supongamos que Eva elige b = 5. Entonces, 25 = 32; 32 mod 19 = 13. Eva envía a Adán su resultado 13 por el medio público. Es decir, Eva envía a Adán su regalo en otra caja cerrada con un candado.

• Adán toma el resultado de Eva (13) y lo eleva al número que había elegido (6). Luego vuelve a sacar el valor módulo 19. 136 = 4826809; 4826809 mod 19 = 11. En el acertijo, Adán aplica su propio candado a la caja con candado de Eva y la devuelve.

• Eva hace lo mismo que Adán con sus propios valores: 75 = 16807; 16807 mod 19 = 11. Eva aplica su candado a la caja con candado de Adán y se la envía.

• Ahora ambos conocen el número secreto 11 y pueden usarlo como clave. En el acertijo, Adán y Eva tienen las cajas con doble candado; ahora pueden retirar los candados propios y enviarlas nuevamente, cerradas solamente con los candados de los receptores.

1 comentario Hacer un comentario

  • 1. yuliana  |  Sep 29 2006, 1:27 pm

    es un libro muy bueno que me gustaria leer y conocer al que lo fabrico.

    yuliana mgaly sandoval robles

Hacer un comentario

(no se publica)

Es posible que su comentario deba ser aprobado antes de la publicación. Sea paciente. Si lo desea puede usar un poco de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> , pero si todo esto no tiene sentido actúe normalmente. Evite escribir todo con mayúsculas. Sea amable.


Esta es una anotación de juegosdeingenio.org, un weblog dedicado a los juegos de ingenio, los acertijos y todo lo demás. Debajo de algunas notaciones aparecen comentarios de otros lectores; usted puede dejar el suyo o bien escribirle directamente al responsable. Las anotaciones más recientes se pueden ver en la página inicial.