Soluciones Desafío 123

Pardillano dice:

Tras este fiasco-engendro-desatino de desafío se esconde un problema que a mi me pareció bonito: el protocolo para compartir secretos de Shamir es perfecto cuando se usa aritmética modular sobre un número primo. En la última parte de mi solución explico la relación.

Se me ocurrió después del desafío de la abuela aventurera. A mi me pareció casi mágico, que las fórmulas para despejar el secreto en las ecuaciones deducidas para aritmética “normal” funcionaran directamente en aritmética “modular”. También me sorprendió lo bien que cuadraba todo: por mucho que manejáramos las relaciones con N-1 puntos, cualquier secreto era tan probable como cualquier otro.

Dediqué un tiempo en su día, por gusto, a investigar eso, y se me ocurrió que daría para un desafío. Mejor dicho, dos. Sólo acostumbrarse a operar con aritmética modular llevaba uno. Me puse a redactarlos, seguidos, y como el desafío de la abuela estaba reciente, me pareció que tenía que esconder lo que se pretendía.

Gran error. Inscribir el problema en una historia diferente me hizo dar muchas vueltas para que la historia fuera coherente. La conversación entre el meteorólogo y el presidente, las tablas de evaluación… todo paja para esconder un problema de enunciado sencillo. Y lo peor, que ha despistado pensando que esa paja eran pistas. No lo eran, solo son elementos de la historia intrascendentes para el problema matemático. Tengo que pensar seriamente participar en otro club, el del abuelo cebolleta, para descargar ahí mi afición a contar historietas y dejar Club Pitagóricos para las matemáticas.

Aun con todo, no había quedado claro lo que se pretendía (una demostración), ni la intención de la historia. Como epílogo de la misma diré que el meteorólogo esperaba que los opositores listos se dieran cuenta de que fijándose en sus dos vecinos averiguaban el número secreto.

En cuanto a las soluciones, solo veréis la de Rubenman, pero Super también ha estado ahí. Ambos han perdido mucho tiempo, y lo lamento, dando vueltas a entender lo que había que hacer (y temo que no hayan sido los únicos).

La solución de Rubenman muy interesante, aunque no haya obtenido las respuestas como yo pretendía (culpa mía, por el modo de enunciarlas). Destacan varias cosas. Una de las que me ha llamado la atención es que usa la solución de una ecuación de segundo grado con un polinomio en aritmética modular. Alucinante, porque funciona. Le sirve para averiguar los posibles P de la parte opcional cuando se usa la información de dos formularios. No lo veréis hasta el final, porque la última parte la hizo en una hoja de cálculo difícil de interpretar, y que no se incluye. Pero yo que si la he tenido he comprobado que esos 28 valores coinciden con los míos. Yo los hallé a lo bruto haciendo al ordenador realizar unos millones de iteraciones, pero Rubenman los ha obtenido con una combinación de deducciones y paciencia. Ole.

D123_imagen_blogEl proximo jueves nuevo Desafío de Rubenman

d123_pardillano

D123_Rubenman

Anuncios

14 pensamientos en “Soluciones Desafío 123

  1. No he leído aún las soluciones, pero antes de ponerme a ello e intentar descubrir qué es lo que he hecho mal, quiero comentar un par de cosas:
    A mí el enunciado me ha parecido inmejorable, y no estoy de acuerdo en que despiste demasiado. De hecho, debería haber despistado más. porque yo no vi la paja por ningún sitio.
    En mi opinión, estaba todo clarísimo desde el primer momento. Es más, estaba todo clarísimo hace ya unos cuantos meses, cuando Pardillano comentó al final del Desafío 110 que el sistema de Shamir podía tener un problema, y que ese problema estaba comentado en la Wikipedia en inglés (en el artículo español no sale). Era sólo cuestión de tiempo que ese problema reapareciera por aquí.
    La solución al problema usando aritmética modular es absolutamente genial, aunque yo pienso que el problema es un tanto artificial porque está causado por la pretensión (absolutamente artificial e innecesaria) de que todos los coeficientes del polinomio sean números naturales (o al menos enteros no negativos), y encima, acotados. Puedo equivocarme pero, en mi opinión, dejando que los coeficientes sean números reales, el supuesto problema se desvanece y no es necesario recurrir a la aritmética modular.
    Por ejemplo, usando el sistema alternativo (que varios Pitagóricos propusimos en el D110) de codificar el secreto como una de las coordenadas del centro de un círculo, es evidente que con un formulario no tendríamos nada, pero con el segundo, es seguro que la solución cae sobre la mediatriz del segmento que une los dos puntos conocidos. Esto es mucha información, pero no nos sirve de nada porque la mediatriz es infinita, y aunque estuviera muy limitada por condiciones añadidas del problema, al haber infinitos puntos en el segmento limitado seguiríamos sin saber nada útil.

    Por cierto, a mi me también me parece mágico que las fórmulas funcionen tanto en aritmética normal como en aritmética “modular”.

  2. Extremadamente bien explicada la solución de Pardillano, aunque no creo que se pueda considerar una demostración formal. Buenísima la observación de las simetrías de la parábola de Rubenman. Genial.
    Ya veo cual era mi problema al hacer los volcados. No era un fallo de programación sino uno fallo de concepto. Un fallo gordo, gordo. No estaba eliminando bien. Tengo que prestar más atención.

  3. La lectura del desafío y sobretodo lo que se comentaba acerca de aumentar la probabilidad me hizo creer que había alguna forma de hacerlo.
    En ese sentido interpretaba todo, incluso los comentarios, de ahí mi desorientación.
    Debo de ser muy ingenuo.
    En efecto, lo de las ecuaciones resultaba curioso y más me resultó que todos los conceptos de la parábola se extrapolaran al caso.
    Tuve que dar el caso por cerrado por ese despiste hacia la primera parte y porque vi que no había desafío siguiente y tenía una idea y había que trabajarla.
    Acerca del razonamiento tenía otra línea. El sistema de dos ecuaciones me permite identificar dos variables cualesquiera a partir de una tercera. Esta última puede ser cualquiera y puede tomar cada uno de los 101 valores; este hecho lleva implícito que todos los valores deban estar en las tres variables, justificando la equiprobabilidad entre ellos. Esto se comprueba si vemos las 101 ternas posibles y constatamos que tanto “c”, como “p” y como “d” completan el abanico de todos los números. Dicho de otro modo, se podía ampliar la apuesta a cualquiera de esas tres variables con idéntico resultado.
    En el caso de 1 formulario, parte opcional, comenté que era mejorable porque consideré todo el abanico de valores del 0 al 100, y luego vi que en el enunciado el a=0 había que eliminarlo; de ahí ese error que comenté.
    La tabla de descartes es relativamente sencilla de confeccionar para 2 formularios, en la parte opcional. Partimos de las 101 ternas comentadas y calculamos el valor del radical, ya sea en el caso del 0 y del 1, si es cuadrado perfecto se deshecha; previamente hay que confeccionarse esta columna de cuadrados para comparar.
    Por cierto, también fue curioso comprobar que la raiz cuadrada existe, además con doble origen, como la tradicional. Sólo que hay valores que no la tienen y que tal vez fuese más complicado calcularla.
    Todo muy curioso.

      • El Jefe no podrá decir nada hasta que no se lo mande, y ahora mismo estoy bastante perjudicado por una celebración que no viene a cuento, así que lo que tenga que ser será en otro momento. Me voy a la cama.

  4. Como desafiante me veo obligado a comentar algo del desafío.

    Estoy muy decepcionado con vuestra falta de observación.

    No habéis visto que la figura del blog es Indiana Jones formada con símbolos matemáticos (el sombrero es un PI, y el látigo una integral), haciendo honor al título del desafío.

    Y ahora, para abrir boca al siguiente desafío de Rubenman, un problema conocido (se encuentra fácilmente en Internet, pero os recomiendo que no lo busquéis y lo intentéis), y que mencioné en el anterior que podía usarse para un desafío. Pero no tiene tanta envergadura.

    Tenemos doce joyas. Once auténticas que pesan igual y una falsa, que no sabemos si pesa más o menos que las demás. Tenemos que averiguar con la ayuda de una balanza cual es la falsa, y además decir si pesa más o menos que las auténticas. ¿Cuantas pesadas son necesarias en el pero de los casos?

    • No caí en eso que comentas de Indiana Jones, pero he de decir que con un poco de imaginación se parece.
      Bien por ese de las joyas. Ya pensaremos.

      • Tengo ya una idea, no hago ningún comentario para no entorpecer el entretenimiento. Por ahora no sé cómo bajar de ahí, a la tarde le daré una vuelta más.

  5. Claro, ¡Indiana Jones!
    Y yo que pensaba que era un mimo sirviendo martinis mientras pasa la aspiradora…

    Yo ya tengo el de las joyas. Pero tengo que reconocer que lo saqué el Viernes pasado y me lo estaba guardando por si Pardillano lo colgaba. Me costó bastante.

    • Supongo que es el que se puede generalizar, que es variante del de las 10 joyas, que a su vez es una variante de las 9 joyas, que a su vez es la variante de las 9 conociendo si pesan más o menos

    • A falta de ideas te hago una propuesta “original”. El desafío que comentabas parece que tiene dos formas de ser demostrado. Muy sencillo, pregunta primera demuestra que….. Segunda pregunta demuestra lo mismo de otra manera…, y por supuesto que no falte la pregunta opcional, demuéstralo de una tercera manera..
      Venga, con el próximo tendrás tiempo para ello.
      Por otro lado veo que hay muchas joyas, 12, luego 10, luego 9; o alguien las está robando?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s