Cien personas conocen casi todo: ven los números de los demás, pero no el suyo propio. Sin comunicarse tras conocer los números, cada una debe predecir el suyo. El grupo gana si al menos una acierta.
¿Puede el grupo garantizar la victoria, sea cual sea la asignación de números?
El oráculo modular
Enunciado
Hay 100 personas numeradas del 0 al 99. En la frente de cada una se escribe un número entero entre 0 y 99. Puede haber repeticiones.
Cada persona ve los 99 números de los demás, pero no el suyo.
Antes de que se escriban los números, las 100 personas pueden acordar una estrategia. Después, sin comunicarse, cada una debe escribir una única predicción para su propio número.
El grupo gana si al menos una persona acierta.
¿Existe una estrategia que garantice la victoria, sean cuales sean los 100 números escritos?
Ver solución
Solución
Respuesta: sí. Pueden garantizar que exactamente una persona acierte.
Numeran a las personas del 0 al 99 y trabajan módulo 100.
La idea es repartir entre ellas las cien posibilidades para la suma total. La persona $i$ actúa como si la suma de los 100 números fuera congruente con $i$ módulo 100.
Si la suma de los 99 números que ve es $s_i$, entonces, bajo esa hipótesis, su propio número tendría que ser
Esa es la predicción que escribe.
Ahora veamos por qué funciona. Sea $S$ la suma real de los 100 números, módulo 100, y sea $x_i$ el número real de la persona $i$. Como $s_i$ es la suma de todos los números salvo $x_i$,
Por tanto,
La persona $i$ acierta exactamente cuando $g_i\equiv x_i$, es decir, cuando
Entre los índices 0 y 99 hay exactamente uno que coincide con la suma real $S$ módulo 100.
Por eso exactamente una persona acierta, sean cuales sean los números escritos: las cien personas cubren, entre todas, las cien posibles sumas totales.