The 1,000th prisoner-hat riddle
For years now, the evil mathematician wizard has been capturing and lining up groups of prisoners to let them guess the colors of the hats he put on them in exchange for their freedom. But since everybody nowadays already knows how to solve this problem, almost everybody escapes, prompting the wizard to come up with something more difficult. What if he used numbers instead of colors?
The next time he captures 1,000 prisoners, he lines them up in a row and gives everyone a hat with a positive integer written on it, subject to the following condition: The number of the first prisoner is at most 1, the number of the second one is at most 2, the number of the third one is at most 3, all the way to the 1,000th prisoner, whose number is at most 1,000.
Everything else is as usual:
- The prisoners are asked to guess the number of their hat in the order they are standing in.
- Every prisoner can only guess a number that is in the set of possible numbers for that prisoner.
- Every prisoner can only see the numbers of the prisoners that come after them, but they can hear the guesses of everyone.
- After everyone has guessed, the wizard frees those who guessed correctly and imprisons forever those who did not.
- The prisoners know the rules of this "game" and are allowed to agree on a strategy in advance.
What is the maximal number of prisoners that can be guaranteed to be freed?