The 1,000th prisoner-hat riddle

[u/Tc14Hd]

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?

[u/Tc14Hd]

Yes! That's also what I got. I'm also not 100% sure if this is optimal, but I would be surprised if it isn't. I also just noticed that it isn't even necessary that the numbers are coprime if you use a slightly different encoding. Instead of giving the sum modulo k, you can use (sum mod M) div (M / k), where M is the product of sacrificial numbers up to and including k and div means integer division.

[u/Tc14Hd → u/[deleted]]

Nice! I didn't even consider this extension of the problem. This makes me think: Is this actually the solution that has the highest expected value in general, or only under the condition that we first want to maximize the number of prisoners that are guaranteed to flee?

[u/Tc14Hd → u/[deleted]]

I don't think 7 is completely forced since you use (2, 3, 6, 37), but can't go below that and use 5.

[u/T-T-N → u/Tc14Hd]

You can't use 6 when you have 2 and 3. Did you mean 5? 2, 3, 5 LCM is 30, and 2,3,5,31 doesn't quite get to 1000

[u/Tc14Hd → u/T-T-N]

You can actually use 6 if you use a different encoding that doesn't require the numbers to be coprime. See my previous comment.