Home > Riddles > The modular oracle
One hundred people see almost all the information, except just what they need. The way out is not to guess better, but to distribute the possible errors in such an orderly manner that one of them has to disappear.
There are 100 people numbered from 0 to 99. An integer between 0 and 99 is written on the forehead of each one.
There may be repetitions. Each person sees everyone else's 99 numbers, but not their own.
Before the numbers are written, the 100 people can agree on a strategy. Then, without communicating, each must write a single prediction for their own number.
The group wins if at least one person gets it right. Is there a strategy that guarantees victory, regardless of the 100 numbers written?
Answer: yes. There is a strategy that guarantees that exactly one person gets it right. We number people from 0 to 99 and work module 100. The person $i$ adds the 99 numbers he sees. Let's call that sum $s_i$. Then write the number as a prediction $$
g_i\equiv i-s_i\pmod{100}.
$$ Let's see why it works. Let $S$ be the real sum of the 100 numbers, taken modulo 100. If the real number of person $i$ is $x_i$, then the sum of the numbers he sees is $$
s_i\equiv S-x_i\pmod{100}.
$$ His prediction is therefore $$
g_i\equiv i-s_i\equiv i-(S-x_i)\equiv x_i+i-S\pmod{100}.
$$ Person $i$ is correct exactly when $$
g_i\equiv x_i\pmod{100},
$$ which happens exactly when $$
i\equiv S\pmod{100}.
$$ Since among the people numbered 0 to 99 there is only one person whose index matches $S$ modulo 100, exactly one person is correct. So the group has a guaranteed winning strategy.
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.