Solving the Hat Color Problem: Infinite Prisoners, 2 Colors

[Focus]

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.

 

[davee123]

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:

Spoiler

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

 

[Focus]

Very nice Dave. The second problem is much harder, give that a go

 

[Jimmy Snyder]

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.

 

[davee123]

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

 

[Focus]

Emphasis mine.
An issue with the infinite number of prisoners is that there is no 'back' to begin from.

Take the naturals.

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

Spoiler

Take sequence of hats x and y then consider x~y iff they agree after a finite amount of people

 

[davee123]

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

 

[Focus]

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.

Spoiler

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

 

[davee123]

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

 

[davee123]

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