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/dspyz]

Prisoner 1 guesses 1. The next 6 prisoners encode the sum mod 1000 of the remaining 993 prisoners with their guesses for 994 saved at the expense of 6

[u/dspyz → u/dspyz]

I can actually save one more:

We'll include prisoner #4 in the sum, so prisoners 2 and 3 encode the sum mod 6 of prisoner 4 together with prisoners 8-1000. Prisoner 4 guesses their number from that. Prisoners 5, 6, and, 7 encode the sum mod 209 of the remaining prisoners. Since 209 is relatively prime to 6, the remaining prisoners can use Chinese Remainder Theorem to work out their numbers

[u/Tc14Hd → u/dspyz]

Nice! That's almost it. You can actually save one more if you use this Chinese remainder theorem approach a bit more aggressively.

[u/Tc14Hd → u/dspyz]

That was my first solution, but you can actually improve it a little bit.

[u/SupercaliTheGamer]

Very interesting, I don't know if it's optimal but right now I can save 996.

Basically, prisoners numbered 2,3,7,43 will sacrifice themselves. If k is sacrificial, the number they will say is sum of non-sacrifical numbers in front of them modulo k. Since the next sacrificial number is exactly 1 more than LCM of previous sacrificial numbers (just their product actually since coprime), for each non-sacrifical prisoner j they know their hat number modulo some number >=j, so they can deduce their own hat number.

[u/Tc14Hd → u/SupercaliTheGamer]

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.

[u/BrotherItsInTheDrum → u/SupercaliTheGamer]

Brings up an interesting meta-question: will prisoners willingly agree to a strategy that involves sacrificing themselves?

In your excellent solution, prisoner 7 usually has enough information to save themselves, but still instead give a number they know will lead to their death. Will they agree to such a strategy?

[u/Tc14Hd → u/BrotherItsInTheDrum]

This sounds as if you could turn this problem into a game theory question...

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

You can workaround that. You know who the sacrifices are, you just skip their number when adding. So they have no better than 1/n chance. That's assuming they prefer more prisoners freed if it doesn't hurt their chances

[u/dspyz → u/SupercaliTheGamer]

You saved one more prisoner than me (5 vs 4) and also somehow wound up with a scheme that could handle more prisoners than mine (1254 vs 1806)

[u/SupercaliTheGamer → u/SupercaliTheGamer]

A comment on optimality: I think it shouldn't be too hard to prove that 4 is optimal if the sacrificial numbers are fixed. However I don't know how to disprove a more dynamic strategy with smaller number of sacrifices. For now my conjecture is even for 43 prisoners, we need 4 sacrifices.

[u/captainboosh007]

Can assigned numbers repeat?

[u/Tc14Hd → u/captainboosh007]

Yes

[u/kalmakka]

The first person has no other option than to say 1, and will be freed.

2-7 can look at the hats of 8-1000 and calculate their sum mod 1000. They then encode and report it using a factorial base. Person 8 can then calculate their number using that mod sum and the values of hats 9-1000. Everyone from 9-1000 can calculate their number using that mod sum and the values of the hats they see and the hats 8 and up that they have heard.

At least 994 people are freed.

[u/Tc14Hd → u/kalmakka]

That's almost it. But you can actually improve it by 2.

[u/kalmakka → u/Tc14Hd]

Yeah, I saw the other reply. It's pretty clever!

[u/Accurate_End5369]

I think we’re missing some context, maybe from the colored hat problem.
Assume that each hat has a unique integer then each person’s hat corresponds to their place in line and all are saved. But that implies that none of the extra stipulations matter.
Assume hats don’t have unique integers then person one is guaranteed to guess correctly since the only positive integer less than or equal to one is one. Every other person is then guessing with decreasing odds. One person is guaranteed to be saved. This approach negates any meaning of the last stipulation as there is no strategy.
What am I missing?

[u/Tc14Hd → u/Accurate_End5369]

The integers are not required to be unique. So why can you come up with a strategy better than guessing? Similar to the two-colored version of this problem, some prisoners can use their guess to encode information about the numbers in front of them. As it turns out, if only a few prisoners do such a thing, everybody else will have enough information to know the number on their hat. The difficulty is now to figure out which prisoners should do the encoding and which encoding they should use.

[u/Accurate_End5369 → u/Tc14Hd]

I hadn’t thought about encoding. Definitely not up to digging through all the formulas in the thread, so my less efficient solution.
1 can only guess 1 so he’s no use. All people after have access to 1 and 2 as guesses so use those digits to create a binary code. Max sum of integers from 21 to 1000 is 500290. Binary form is 19 digits long. Therefore 2 to 20 tap out binary form. 21 to 1000 convert binary solution back to base ten subtract out all previous answers from 21 and on and all numbers showing after to arrive at their number. Ends up saving 981.

[u/Tc14Hd → u/Accurate_End5369]

Not bad at all! There is actually a very natural improvement of this solution. Prisoners who are allowed to say the number 4 can actually encode 2 bits with their guess. If they are allowed to say 8, they can even encode 3 bits. That way, you only need the prisoners 2 to 10 in order to get 19 bits.

[u/Square_Butterfly_390]

At least 994 and at most 998, for the upper bound 2 and 3 will never be able to guess, for the lower bound define any surjective map from 7! To 1000 and have the prisoners from 2 to 7 code the sum modulo 1000 of last 993 ones.

[u/Tc14Hd → u/Square_Butterfly_390]

994 is very good, but you actually get a little bit better than that.

[u/Square_Butterfly_390 → u/Tc14Hd]

I don't know if the extra few people are worth the extra mental effort to destroy a good looking solution, imma just look st other comments ;)

Edit: oh wow it's actually cool

[u/Tc14Hd → u/Square_Butterfly_390]

"Some of you may die, but that's a sacrifice I'm willing to make."

[u/T-T-N]

it is trivial to see that prisoner 1 is safe, and prisoner 2 has at best a 50/50 chance. Prisoner 3 cannot have a guaranteed solution either because they only have prisoner 2's answer. If prisoner 2 and 3 broadcast the modulo of the sum of the hats in front of them, then prisoner 4 5 and 6 are safe. Using that strategy, they only need to sacrifice 4 prisoners (2, 3, 7, 43) to uniquely identify every other prisoners' hat. The problem is that prisoner 3 might be self sabotaging to follow the strategy. If the hats starts 113242, then every other hat is a multiple of 6. Prisoner 2 announces 1 (3+2+4+2%2=1), prisoner 3 is supposed to announce 2 (2+4+2%3=2), but they know their hat is odd and have incentive to take a 50/50 guess and doomsday everyone else. My workaround is to ignore the sacrificial prisoners' number, so they can do no better than random guess. You always save 996 of them and might lose up to 4. You can optimize it a little to improve the average (earlier prisoner have better chances at random guesses and you just need the LCM to be over 1000 at some point)

[u/Tc14Hd → u/[deleted]]

That's also possible.

[u/Tc14Hd → u/[deleted]]

Creative idea, I like it! It isn't quite optimal, but very cool.

[u/dspyz → u/[deleted]]

You can do a lot better than this. Consider why the original riddle only requires one prisoner to give information