One hundred people know almost everything: they see other people's numbers, but not their own. Without communicating after knowing the numbers, each one must predict theirs. The group wins if at least one guesses correctly.
Can the group guarantee victory, regardless of the number assignment?
The modular oracle
Riddle statement
There are 100 people numbered from 0 to 99. An integer between 0 and 99 is written on each person's forehead. There may be repetitions.
Each person sees the others' 99 numbers, but not their own.
Before the numbers are written, the 100 people can agree on a strategy. Then, without communicating, each person must write a single prediction for their own number.
The group wins if at least one person is correct.
Is there a strategy that guarantees victory, regardless of the 100 numbers written?
Show solution
Solution
Answer: Yes. The group can guarantee that exactly one person is correct.
Number the people from 0 to 99 and work modulo 100.
The key is to divide the 100 possible values of the total sum among the 100 people. Person $i$ acts as though the sum of all 100 numbers were congruent to $i$ modulo 100.
If the sum of the 99 numbers they see is $s_i$, then under that assumption their own number would have to be
That is the number they predict.
Now let $S$ be the actual sum of all 100 numbers, modulo 100, and let $x_i$ be person $i$'s actual number. Since $s_i$ is the sum of every number except $x_i$,
Therefore,
Person $i$ is correct exactly when $g_i\equiv x_i$, which is equivalent to
Among the indices from 0 to 99, exactly one is congruent to the actual total $S$ modulo 100.
Thus exactly one person is correct, whatever numbers were assigned: together, the 100 people cover all 100 possible values of the total sum.