Ask HN: What's your favorite math/logic puzzle?
I personally am a fan of "hat" problems, such as the following: there are 100 inmates in a prison. Tomorrow the warden will assign each a number, from 1 to 100, that will be written on their hat. The numbers won't necessarily be different, and each prisoner will be able to see the numbers of all the other prisoners, but not their own number. The warden will free all the prisoners if one of them will correctly guess their own number. Of course, tomorrow they will not be allowed to communicate in any way, and each prisoner will be given only one chance to guess. How can they strategize today so as to be free tomorrow?
4 comments
This one: https://puzzling.stackexchange.com/q/74037/34791
A rather complicated setup, admittedly, but it's super satisfying if you manage to solve it on your own without having it spoiled.
A rather complicated setup, admittedly, but it's super satisfying if you manage to solve it on your own without having it spoiled.
I really like the Josephus Problem ([Numberphile‘s Video on YT](https://youtu.be/uCsD3ZGzMgE)) because of the binary twist, really enjoyed Veritasium‘s [3x+1](https://youtu.be/094y1Z2wpJg) and my favorite is your described [100 Prisoners Riddle](https://youtu.be/iSNsgj1OCLA) too
OP, if I understood your puzzle, then 99 prisoners can answer correctly. Is that right?
No, only one. Think about it this way - if the warden randomly generates their numbers, each prisoner has a 1/100 chance of guessing it right. So best case scenario is exactly one gets it right, which is actually possible.
Ooooh. The prisoners can't hear other prisoners' guesses then. Ok! But in your example, isn't the probability of winning 1-(99/100)*100?
I don't think your "best case scenario" comment is actually true
I don't think your "best case scenario" comment is actually true
They just need one prisoner to guess correctly - then they all win.
Regarding the base case scenario - if each prisoner guesses randomly, each has a 1/100 chance of guessing correctly, and hence they have an expected number of exactly one correct guess. So no deterministic approach can give 2 correct guesses, since no prisoner actually has any real information about their number.