4 ms·

Ask HN: What's your favorite math/logic puzzle?

5 points by tomachello 4y ago

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?

liberia 4y ago
x = x + 1
- deleted 4y ago
  [deleted]
josephcsible 4y ago
This one: https://puzzling.stackexchange.com/q/74037/34791 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.
hollowpython 4y ago
OP, if I understood your puzzle, then 99 prisoners can answer correctly. Is that right?
- tomachello 4y ago
  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.
  - hollowpython 4y ago
    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
    - tomachello 4y ago
      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.
hostcontroller 4y ago
I really like the Josephus Problem ([Numberphile‘s Video on YT](https://youtu.be/uCsD3ZGzMgE https://youtu.be/uCsD3ZGzMgE)) because of the binary twist, really enjoyed Veritasium‘s [3x+1](https://youtu.be/094y1Z2wpJg https://youtu.be/094y1Z2wpJg) and my favorite is your described [100 Prisoners Riddle](https://youtu.be/iSNsgj1OCLA https://youtu.be/iSNsgj1OCLA) too