Dos problemas de lógica por el precio de uno

En el libro «In Code» de Sarah Flannery y David Flannery se cuenta la siguiente historia que, dejando aparte sus visos de leyenda, plantea un bonito problema de lógica cuya solución se conoce (teoría de la información, comunicaciones, criptografía) con el nombre de protocolo de conocimiento cero, para indicar que no implica revelar el secreto de ningún dato particular.

En una fiesta que reunía a un grupo de matemáticos se planteó el problema de averiguar el promedio de sus ingresos con la condición de que no revelar ningún dato particular. Mientras los sesudos implicados consideraban el problema, se dice que la hija de uno de ellos levantó la mano a la vez que exclamaba “Ya sé cómo”, y explicaba seguidamente el método.

Se supone que los matemáticos no mienten nunca, acostumbrados como están en perseguir siempre la verdad estricta, y que además todos están verdaderamente interesados en conocer la respuesta cierta. Para la solución (o quizá sería mejor decir para una solución) acuda a la página xxx.

La niña sugirió soplar un número elevado elegido al azar a uno de los matemáticos. Este debía sumar la cifra de sus ingresos a dicho número, escribir el resultado en un trozo de papel y pasarlo al siguiente colega. Este debía escribir una nueva nota con la suma del anterior resultado y sus ingresos y pasarla al compañero siguiente, guardando la nota recibida (o devolviéndola al que se la entregó, o incluso destruyéndola, si se quiere). Cuando todos los matemáticos presentes han participado en el procedimiento, el último de ellos entrega su nota a la niña, la cual resta su número secreto del total y divide el resto por el número de matemáticos.

Y ahora viene el segundo problema, porque vengo yo y hago notar que la niña de la historia puede muy bien mentir, dado que no es matemática. Es posible que quiera quedarse para sí con la cifra real pero que tenga interés en confundir a los reunidos comunicando un valor menor, por ejemplo. ¿Qué procedimiento podría establecerse para certificar que el resultado es seguro, en el supuesto de que ninguno de los matemáticos haya mentido, y que respete la condición de que ninguno de ellos pueda conocer la cifra de ingresos de otro de sus colegas?

Para una solución, vaya a la página yyy.

Ojo, no vale hacer público el número pensado por la niña, pues el matemático número dos conocería enseguida los ingresos del número uno. Una solución podría consistir en que la niña escribiera su número en un papel que se guardara aparte. El matemático que comienza tiene acceso a dicho papel, y él mismo es el encargado de efectuar los cálculos finales y comunicar el resultado. Para inspirar mayor confianza, puede acompañarlo a verificar el número el último de los que intervinieron en el procedimiento.

Pedro Crespo, julio 2006