Desafío 111

El crucero (Rubenman)

Los cinco hijos se han puesto de acuerdo y con el dinero de la cuenta de la vieja se han ido a disfrutar de un crucero de 4 noches, con sus respectivas parejas.

El maître les prepara una mesa redonda con 10 sillas y los hermanos toman la decisión de cambiar cada noche de vecinos inmediatos de mesa prescindiendo de cualquier cuestión de género (sexo), de manera que tod@s coincidan con tod@s y así se puede hablar mejor del reparto de la herencia.

El camarero les oye hablar y les apunta que, al tratarse de 4 cenas, les faltará una persona para completar el total. Por ello les propone que, por una simple cuestión de protocolo, sería aconsejable que tod@s concluyesen el crucero sin haber compartido vecindad con su propia pareja.

¿Es posible llevar a cabo una distribución diaria en la que se cumplan esos requisitos? En caso afirmativo deberás proponer un modelo y en caso negativo tendremos que razonar la respuesta.

¿Y si hubieran sido 10 parejas y 9 noches?

1Soluciones hasta el lunes 6 octubre a solucionesclubpitagoricos@gmail.com

Soluciones Desafío 110

Pardillano dice:

Estoy muy agradecido con la variedad de propuestas recibidas, muy originales y algunas con detalles geniales.

El problema del desafío se engloba en lo que se llama compartición de secretos (secret sharing). Dentro de estos, corresponde a un caso específico: esquemas de umbral, donde con N datos se recupera el secreto, y con N-1 es imposible.

Un modo, no el único, de encontrar soluciones es encontrar un problema que sea resoluble con N datos, pero no con N-1, y de modo que los datos se puedan elegir independientemente. Rubenman ha sido el primero en dar con una solución muy general: guardar el secreto en N variables (para el caso del desafío serían tres: X, Y, Z) y proporcionar a cada hijo una ecuación con N incógnitas. Aquí el dato proporcionado a cada hijo no es un número, sino una ecuación. Con tres ecuaciones se resuelve el sistema, se averiguan X, Y, Z y se recompone el secreto (la clave bancaria). Con menos es un problema indeterminado.

Muchas de las soluciones “oficiales”, corresponden en el fondo a eso. El “Esquema de Shamir”, que es lo que hemos llamado “solución oficial”, consiste en elegir un polinomio de grado N-1, tal que su término independiente sea el secreto, y proporcionar a cada hijo un punto de ese polinomio. Cuando tres hijos se junten, verán que al intentar resolverlo lo que les queda es un sistema lineal de tres ecuaciones con tres incógnitas, que en este caso son los coeficientes del polinomio de segundo grado. En mi solución comento otra “solución oficial”, que es el esquema de Blakley, y que en el fondo es algo parecido.

La solución de Sebas tiene cosas en común. Aunque Sebas no intenta ocultar el valor de las incógnitas (de hecho se las proporciona a los primeros hijos) sino una clave compuesta con estas y con el resultado de las ecuaciones que proporciona al resto. En el ejemplo que incluye (para 7 hijos con 4 necesarios) se ve muy bien.

También dentro del esquema “problema resoluble con N datos pero no con N-1”, tanto Rubenman como SPZ han dado como solución particular la de la circunferencia. Se esconde la clave en las coordenadas del centro de una circunferencia, y se proporcionan a los hijos puntos de la misma. Con tres puntos, la circunferencia está determinada, por lo que podremos averiguar su centro y recomponer la clave. Con solo dos puntos no es posible. También entiendo que las propuestas como “Alternativas particulares” en la solución de SPZ van por ahí.

Hay otras soluciones que se salen de ese esquema, como las dos de Dospew, la última de Rubenman y la de Suschus. La primera de Dospew consiste en dar a cada hijo un número acabado en una cifra diferente, de 1 a 5, y a todos ellos una tabla. Al juntarse tres de ellos, la tabla les indica que cálculo han de realizar para obtener la clave. La versión que incluye Dospew en su solución es más segura que la me envió inicialmente, que conseguí “reventar”. El proceso para hacerlo, al menos el que yo encontré, es divertido, aunque algo laborioso y requiere alguna ocurrencia. Propongo reservarlo para un posible desafío secuela de este. Por ello, si os parece bien, nos abstendremos de dar pistas sobre como reventarlo.

La otra solución de Dospew, la tercera de Rubenman y la de Suschus guardan muchas similitudes. Todas proporcionan a dos hijos muchas partes de la clave, pero mantienen ocultas otras. Realmente Suschus en su solución habla de 10 claves, pero si las encadena todas en una sola clave larga, le queda un procedimiento parecido a los de Dospew y Rubenman.

A mi me parece que Rubenman introduce una idea genial que hace su propuesta más segura: para reconstruir la clave, tres hijos deben elegir el mayor de los números que encuentren en cada posición. De este modo, dos de ellos no pueden estar seguros del valor concreto de ninguna parte de la clave.

Todos los métodos, incluidos los oficiales, tienen problema para cumplir un requisito que apuntó SPZ: la información de dos hijos no debe dar ninguna pista sobre la clave. Comento brevemente esto en mi solución al hablar del esquema de Shamir, y cuento donde encontrar el método que han pensado los matemáticos para evitarlo, que utiliza un número primo. Pero no olvidemos que ese es un requisito que se suele pedir a los sistemas de compartición de secretos, pero que no es exigible para este desafío.

Para terminar dejo una coletilla misteriosa: todos los métodos (incluido el oficial de Shamir con su truquito del número primo) tienen un problema MUY GRAVE, que los puede hacer INVÁLIDOS para los propósitos de la abuela. Si no lo habéis comentado en ninguna solución, es que no os habéis percatado. Lo reservo para una segunda secuela.

D110_imagen

El jueves nuevo Desafío de Rubenman

D110_Dospew

D110_Pardillano

D110_Rubenman

D110_Sebas

D110_SPZ

D110_Suschus

Pardillano

Desafío 110

Una abuela aventurera (Pardillano)

Ahora que se acerca el verano en el hemisferio sur, una abuela viuda planea embarcarse en una fascinante aventura: atravesar la Antártida en solitario a bordo de un trineo. Antes de marchar tiene atados todos los detalles, incluido el procedimiento para ser rescatada en helicóptero en caso de que algo se tuerza. A la abuela le bastará con llamar a sus cinco hijos con un teléfono por satélite, darles sus coordenadas GPS, y que estos contacten con una empresa especializada a la que tendrán que transferir anticipadamente el coste del rescate (una pequeña fortuna). Como los hijos no tienen suficiente dinero, la abuela ha depositado la cantidad necesaria en una cuenta bancaria.

Los hijos no están muy contentos con esta idea, por los riesgos para la abuela pero también porque consideran la aventurita como un despilfarro a costa de la futura herencia. La abuela, que confía o desconfía por igual de sus cinco hijos, lo sabe. Por eso se le plantea el dilema de a quién debe dar la clave de acceso a la cuenta bancaria, que supondremos numérica.

Si les da la clave completa a los cinco hijos, cualquiera de ellos podría sacar todo el dinero y fugarse con la pasta. También ha pensado en dividir los dígitos de la clave en cinco partes y darle una a cada hijo, de modo que tengan que juntarse para recomponerla. Pero entonces bastaría con que uno de ellos se niegue a proporcionar su parte, o mienta al hacerlo, para hacer imposible la transferencia a la empresa de rescates en caso necesario. El ahorro de ese gasto iría a engrosar la herencia.

La abuela tampoco descarta que dos de sus hijos se puedan poner de acuerdo para sacar y repartirse todo el dinero si tienen la ocasión, o bien mentir u ocultar información para evitar el rescate en caso necesario.

Sin embargo, está convencida de que tres de ellos no le fallarán simultáneamente (confía en tener más hijos “buenos” que “malos”). Por eso lo que necesita es algún sistema ingenioso para repartir cierta información a cada uno de los cinco hijos, de modo que, para reconstruir la clave de acceso a la cuenta bancaria, sea necesario y suficiente que tres de ellos, cualesquiera, se junten y aporten la información que tienen. Es decir

  • Que si solo dos de los hijos (cualesquiera) se ponen de acuerdo, sean incapaces de recomponer la clave con la información que tienen.
  • Que si son tres de los hijos (cualesquiera) los que se juntan, puedan con total seguridad recomponer la clave, aun cuando los otros dos hijos se nieguen a aportar la información que tienen.

El desafío consiste en encontrar un sistema para dar solución a ese problema, indicando:

  • El modo en que la abuela calcula, a partir de la clave numérica bancaria, que información proporciona a cada uno de los cinco hijos (que no tiene por qué ser parte de la clave ni estrictamente numérica). Como la abuela puede elegir la clave, podéis poner a esta las restricciones que queráis (longitud, dígitos permitidos…)
  • Las instrucciones que debe dar a los hijos para aplicarlo (se les puede suponer suficientes conocimientos matemáticos para realizar los cálculos que la abuela les indique).

Si alguno tiene ganas de ir más allá, intentad que vuestro sistema sea generalizable para una abuela con H hijos de modo que sea necesario y suficiente que N de ellos proporcionen la información que tienen para reconstruir la clave, y que además valga para cualquier tipo de clave numérica, sin restricciones.

D110_Imagen_blogSoluciones hasta el lunes 22 a solucionesclubpitagoricos@gmail.com

Soluciones Desafío 109

Dospew dice:

Con este podemos dar por acabado el periodo vacacional. El próximo será de Pardillano, lo que asegura que durará más que este de las varas, que habéis ventilado en un plis-plas. Gracias por participar pese a las fechas poco adecuadas. Rubenman se disculpó, pese a enviar solución por estar aun “muy ocupado” y Super, “en la edad de piedra”, ha enviado una muy buena edición, como siempre, que mejora cualquier desafío por pobre que sea. Sebas envió enseguida una respuesta algo distinta y Pardillano nos alegró, además, con su carita feliz.

vareo

El jueves nuevo Desafío de Pardillano

D109_Dospew

D109_pardillano

D109_Rubenman

D109_Sebas

D109_SPZ