Puzzle time- Numbers on foreheads
-
wrote on 4 Apr 2022, 08:28 last edited by
Each of 10 prisoners will have a digit between 0 and 9 painted on his forehead (they could be all 2's and 3's, for example). At the appointed time, each prisoner will be exposed to all the others, then taken aside and asked to guess his own digit.
All the prisoners will be freed, provided at least one prisoner guesses correctly.
The prisoners have an opportunity to conspire beforehand; how can they maximize their probability of success?
-
wrote on 4 Apr 2022, 12:12 last edited by
There are so many puzzles involving prisoners with things painted on their forehead. I'm sure there is a UN declaration which says that this is a human rights violation.
-
wrote on 4 Apr 2022, 12:30 last edited by Axtremus 4 Apr 2022, 12:31
When any prisoner is exposed to the others, they tell the prisoner what number they sees on the prisoner’s forehead.
-
wrote on 4 Apr 2022, 13:41 last edited by jon-nyc 4 Apr 2022, 13:50
My initial thoughts are for everyone to calculate the median or mean number that they see and guess the number they see that is closest to it. But I haven't begun to think of what the probabilities would be, in order to compare it to other methods
-
wrote on 4 Apr 2022, 13:52 last edited by
My intuition is that choosing the number closest to the mean of those you see is the best solution but I can't back it up. Maybe tomorrow's hint will help.
-
My intuition is that choosing the number closest to the mean of those you see is the best solution but I can't back it up. Maybe tomorrow's hint will help.
wrote on 4 Apr 2022, 14:01 last edited by@jon-nyc said in Puzzle time- Numbers on foreheads:
My intuition is that choosing the number closest to the mean of those you see is the best solution but I can't back it up.
Although it leads to a lot of situations where everyone can agree on what number should be chosen except the guy who has it
-
wrote on 4 Apr 2022, 14:41 last edited by Horace 4 Apr 2022, 14:42
In the case of a billion prisoners, you would guess the mode, similar to jon's intuition. If from your perspective there were two equally common numbers, you could choose the lowest, or second lowest, etc, based on an agreed upon assignment beforehand. Such as, you could be given a number between zero and (number of prisoners) which would, when modded by the number of equal modes, tell you which mode to choose. That should be guaranteed to work in most cases. More than the 75% chance that random guessing will work. Essentially you are betting on the existence of collisions.
-
My intuition is that choosing the number closest to the mean of those you see is the best solution but I can't back it up. Maybe tomorrow's hint will help.
wrote on 4 Apr 2022, 19:45 last edited by@jon-nyc said in Puzzle time- Numbers on foreheads:
My intuition is that choosing the number closest to the mean of those you see is the best solution but I can't back it up. Maybe tomorrow's hint will help.
I don't quite get the logic behind that.
Why should the median of the other numbers influence the distribution of your number?
-
wrote on 4 Apr 2022, 19:54 last edited by jon-nyc 4 Apr 2022, 19:57
The idea is that the median is only slightly affected by your number, less so if your number is close to it.
Imagine if there were 1,000 people doing that. Clearly the differences in median that each would calculate would be a tiny rounding error, thus they would all converge on the same number, including at least one person who had that number.
-
wrote on 4 Apr 2022, 19:56 last edited by
You can also improve over the random probability by doing something with modes like Horace suggested. Even with just 10.
I still haven't been bothered to work out probabilities. I'm hoping the hints reveal a more clever intuitive approach.
-
wrote on 4 Apr 2022, 20:00 last edited by
A lot would hinge on whether the median was a single-occupancy number or multi-occupancy. In the case of a single-occupancy median, that strategy is a guaranteed loss. It's a guaranteed win for multi-occupancy median when it's still the median after removing one of them. It begins to be similar to the mode idea from that perspective.
-
wrote on 4 Apr 2022, 20:14 last edited by Klaus 4 Apr 2022, 21:29
I think I got a solution that works with probability 1. Good old pigeonhole principle.
click to show -
wrote on 4 Apr 2022, 20:25 last edited by
That's clever.
-
The idea is that the median is only slightly affected by your number, less so if your number is close to it.
Imagine if there were 1,000 people doing that. Clearly the differences in median that each would calculate would be a tiny rounding error, thus they would all converge on the same number, including at least one person who had that number.
wrote on 4 Apr 2022, 20:36 last edited by@jon-nyc said in Puzzle time- Numbers on foreheads:
The idea is that the median is only slightly affected by your number, less so if your number is close to it.
Imagine if there were 1,000 people doing that. Clearly the differences in median that each would calculate would be a tiny rounding error, thus they would all converge on the same number, including at least one person who had that number.
I don't think so.
Let's consider a uniform distribution of the numbers. Then the median of the 1000 would very likely be 4 or 5. But that number is not more likely to show up than any other number.
-
wrote on 4 Apr 2022, 20:40 last edited by
You choose the visible number closest to the median.
-
wrote on 4 Apr 2022, 20:51 last edited by jon-nyc 4 Apr 2022, 20:53
I think your solution isn't right. They each (potentially) have a different value of t.
-
wrote on 4 Apr 2022, 21:30 last edited by
@jon-nyc said in Puzzle time- Numbers on foreheads:
I think your solution isn't right. They each (potentially) have a different value of t.
I made a small correction and elaboration on why this is correct.
-
Each of 10 prisoners will have a digit between 0 and 9 painted on his forehead (they could be all 2's and 3's, for example). At the appointed time, each prisoner will be exposed to all the others, then taken aside and asked to guess his own digit.
All the prisoners will be freed, provided at least one prisoner guesses correctly.
The prisoners have an opportunity to conspire beforehand; how can they maximize their probability of success?
wrote on 4 Apr 2022, 22:30 last edited by@jon-nyc said in Puzzle time- Numbers on foreheads:
The prisoners have an opportunity to conspire beforehand; how can they maximize their probability of success?
If prisoners get to choose their own number, then in the “conspire” phase all prisoners agree to one number (e.g., every prisoner chooses to paint himself with the number 0), then every one knows that his own number is 0.
-
wrote on 5 Apr 2022, 00:28 last edited by
Not sure if I understand, but to me, there is no way to make a guess any more accurate. If it is a true random number on the forhead, then there is a 10% chance of guessing correctly.
It doesnt matter if every other number is "8", your number could still be anything from 0-9. etc
What am i missing?