Solving the Hat Color Problem: Infinite Prisoners, 2 Colors

In summary: So if I pick heads, you see that I picked heads, and if I pick tails, you see that I picked tails.In summary, this problem is very hard.
  • #1
Focus
286
3
My apologies if this has been posted before.

n prisoners are wearing three different coloured hats. They are in a line so that they can see the people in front of them but not behind. They will each try to guess their own hat colour and if they get it wrong they will be shot, otherwise they will be freed. The calling will begin from the back (the one who can see all the other people) and the others can also hear what the ones before them called. What is the optimal strategy that the prisoners can develop that will deterministically save the greatest number of them?

If you are feeling brave try this one.

The same scenario with infinite number of prisoners (countable of course) and two hat colours. They can't hear what the others call but I claim I can save all but finitely many of them using the axiom of choice.
 
Physics news on Phys.org
  • #2
I think the premise is the same as the 2-hat problem, just with 3 instead of 2. In fact, here's the general case for N colors of hats:

Assign each color of hat to a sequential integer value, starting at 0. So you have 0 through N-1 values. Each person adds the total numerical value of the hats they see in front of them. Let's call this total T for each participant. The last person in line does the calculation of T modulus N, and gives the color corresponding to that value. They have a 1/N chance of being correct.

Going up the chain, each subsequent person does their value of T modulus N, and takes the difference between the numerical value of the number that the last person used and their own result, noting the 'wrap-around' for the 0 value. They can use this result to determine the corresponding hat that they're obviously wearing, and declare their hat's color accurately with perfect accuracy.

Of course, that's way more math than most people could handle-- I don't realistically think you could pull it off unless N<=2, but it works if all your prisoners are mathematically inclined and not error-prone.

DaveE
 
  • #3
Very nice Dave. The second problem is much harder, give that a go :biggrin:
 
  • #4
Focus said:
n prisoners are wearing three different coloured hats. They are in a line so that they can see the people in front of them but not behind. They will each try to guess their own hat colour and if they get it wrong they will be shot, otherwise they will be freed. The calling will begin from the back (the one who can see all the other people) and the others can also hear what the ones before them called. What is the optimal strategy that the prisoners can develop that will deterministically save the greatest number of them?

If you are feeling brave try this one.

The same scenario with infinite number of prisoners (countable of course) and two hat colours. They can't hear what the others call but I claim I can save all but finitely many of them using the axiom of choice.
Emphasis mine.
An issue with the infinite number of prisoners is that there is no 'back' to begin from.
 
  • #5
Focus said:
The same scenario with infinite number of prisoners (countable of course) and two hat colours. They can't hear what the others call but I claim I can save all but finitely many of them using the axiom of choice.

By the definition of the problem, it seems you can save 50% of them. Because each prisoner can't hear the prisoners behind them make their decisions, effectively each one of them is the last prisoner in line. They only have access to the colors of hats in front of them, which does them no good. Hence, just guess, and you have a 50% chance of being correct.

DaveE
 
  • #6
jimmysnyder said:
Emphasis mine.
An issue with the infinite number of prisoners is that there is no 'back' to begin from.

Take the naturals.

davee123 said:
By the definition of the problem, it seems you can save 50% of them. Because each prisoner can't hear the prisoners behind them make their decisions, effectively each one of them is the last prisoner in line. They only have access to the colors of hats in front of them, which does them no good. Hence, just guess, and you have a 50% chance of being correct.

DaveE

Yes but the information they have (the hat colours in front of them) can help to save them. A little hint
Take sequence of hats x and y then consider x~y iff they agree after a finite amount of people
 
  • #7
Focus said:
Yes but the information they have (the hat colours in front of them) can help to save them.

So, it sounds like you're implying that the hats are likely to appear in a given pattern? That is, that the assignment of hats is a memory-based probability?

I mean, sure, if I saw that the next zillion people in line all have red hats, I'll assume that yes, I've got a red hat too, but mathematically speaking, I still have a 50/50 shot.

DaveE
 
Last edited:
  • #8
davee123 said:
So, it sounds like you're implying that the hats are likely to appear in a given pattern? That is, that the assignment of hats is a memory-based probability?

I mean, sure, if I saw that the next zillion people in line all have red hats, I'll assume that yes, I've got a red hat too, but mathematically speaking, I still have a 50/50 shot.

DaveE

I'll give it away.
Suppose the hats form a sequence of 0-1s. The prisoners a night before make equivalence classes from the relation x~y iff they agree after a finite amount of hats. They then pick a representative from each class using AC and memorize it. On the day each prisoner can see all but finitely many hats in the sequence, so each one knows which equivalence class they are in. So they each use the representative to "guess" their hat colour. By the construction, after finitely many of them, the others will get it right.

Hard problem :devil:
 
  • #9
Hmmm. I guess I don't really understand equivalence classes (I've never been exposed to them, I don't think). It seems kinda sketchy to me, though, that each person is presented with some arbitrarily large number of random information that somehow relates back to guaranteeing at least once instance of a particular separate random outcome.

Perhaps this is a similar example?

You have an infinite number of people. One at a time, each person picks heads or tails, and then flips a coin. Each person in line gets to see the flip (but not the guess) made by those in front of them, and you're somehow guaranteeing that at least 1 person will successfully guess the outcome of their flip.

It seems likely to me, but I'm not sure I see how it's guaranteed, short of the fact that you have an infinite number of opportunities. ... Say, speaking of that, you said that you'd guarantee a finite number of them would get their hat colors correct-- wouldn't 0 be a finite number?

DaveE
 
Last edited:
  • #10
So, a better, exactly equivalent example would be:

Each of the infinite people in line is given a red or blue hat, but immediately after a person makes their guess, their hat is switched with a new random hat color, which is the one they were attempting to guess.

That doesn't change the information that each guesser has, so nobody can tell that it's even going on until it's their turn. And it doesn't change the chances or distribution given that we don't have any information about the random method being used. However, it would seem that you're suggesting that you can predict the random event accurately after some finite number?

DaveE
 
Last edited:

1. What is the "Hat Color Problem"?

The "Hat Color Problem" is a thought experiment that involves a group of prisoners who are given a challenge to solve in order to be set free. The problem requires the prisoners to use logic and deduction to determine the color of their own hat based on the hats worn by others in the group.

2. How many prisoners are involved in the "Hat Color Problem"?

In the standard version of the problem, there are an infinite number of prisoners. However, the problem can also be modified to involve a specific number of prisoners, such as 100 or 1000.

3. What are the two colors of hats used in the "Hat Color Problem"?

In the standard version of the problem, the hats are either black or white. However, the problem can be modified to use any two distinguishable colors.

4. What is the solution to the "Hat Color Problem"?

The solution to the problem is for the prisoners to use a predetermined code to communicate the color of their own hat to the rest of the group. This allows the majority of prisoners to correctly guess the color of their own hat, while some may still get it wrong.

5. Can the "Hat Color Problem" be solved with more than two colors of hats?

Yes, the problem can be modified to involve more than two colors of hats. However, the more colors that are added, the more complex the solution becomes and the less likely it is for the majority of prisoners to correctly guess their own hat color.

Similar threads

Replies
35
Views
4K
Replies
10
Views
3K
  • General Discussion
Replies
8
Views
804
  • General Discussion
Replies
2
Views
3K
  • General Math
Replies
8
Views
4K
  • General Discussion
Replies
14
Views
6K
  • General Discussion
Replies
6
Views
14K
  • General Discussion
Replies
20
Views
3K
  • Math Proof Training and Practice
3
Replies
83
Views
17K
Replies
16
Views
1K
Back
Top