Coloured Hats. (1 Viewer)

[seanieg89]

One hundred mathematicians are in a line facing the same direction, each of them wearing a hat that is coloured either red or blue. Each mathematician can only see the colour of the hats of the mathematicians in front of him.

Starting from the back of the line, each mathematician announces a colour.

For each mathematician that names the colour of his own hat, every mathematician receives $1.

What is the best possible strategy for the mathematicians in order to maximise their winnings? What if there are k > 2 hat colours?


Note: A perfect solution has three parts:
1. The statement of an optimal strategy.
2. A proof that it is optimal.
3. A calculation of the expected winnings using this strategy.

If you cannot complete all three parts, feel free to propose the best strategy you can think of and calculate it's expected winnings.

Eg/ the most basic strategy is every mathematician saying "red", which will win $50 on average, but this is certainly not optimal.

 

[RealiseNothing]

Just my quick first thought. The mathematicians count how many red hats and blue hats there are.

Whichever is the least they say.

i.e. If the first person sees 50 red hats and 49 blue hats, he should say blue. Then the next guy will see 49 red hats and 49 blue hats, and know that he must have a red hat since the person behind him said blue and so including himself there must be more red hats. But he sees equal red and blue hats, so his hat must be red.

 

[Carrotsticks]

Just my quick first thought. The mathematicians count how many red hats and blue hats there are.

Whichever is the least they say.

i.e. If the first person sees 50 red hats and 49 blue hats, he should say blue. Then the next guy will see 49 red hats and 49 blue hats, and know that he must have a red hat since the person behind him said blue and so including himself there must be more red hats. But he sees equal red and blue hats, so his hat must be red.

But that's assuming there are an equal amount of blue and red hats.

 

[RealiseNothing]

But that's assuming there are an equal amount of blue and red hats.

That was an example.

Works with 75 red and 25 blue.

 

[RealiseNothing]

Wait wtf am I thinking.

Nevermind, I think the HSC and chem has gotten to my head.

 

[seanieg89]

I won't ruin the puzzle (and I don't know the answer yet myself, nor have I tried to prove optimality of my current best solution which I doubt is optimal), but the first three strategies I have come up with have expected profit:

$75
~$83
~$87.5

respectively.

Will be interesting to see how high we can go.

 

[shongaponga]

I'm not sure if there's a flaw in this or not, but here's my attempt:

The person who can see 99 hats (ie the 100th person) should inspect all the hats in front of them. If there is an even number of red hats, they should say "red". If there is an odd number of red hats, they should say "blue". The person who can see 98 hats knows exactly how many red and blue hats there is in front of them (as does the person who see's 97, 96 etc). Say for instance if the 100th guy said "red", indicating an even number of red hats in front of him, and the 99th guy see's an odd amount of red hats in front of himself, then he knows he must have a red hat to make the even amount seen by the 100th person.

Continuing this method all the way through 99 people should get the colour of their hat correct and hence a $99 profit can be ensured. The 100th person has a 50/50 chance of getting the colour of their hat correct, so a $100 profit can potentially be made.

 

[seanieg89]

I'm not sure if there's a flaw in this or not, but here's my attempt:

The person who can see 99 hats (ie the 100th person) should inspect all the hats in front of them. If there is an even number of red hats, they should say "red". If there is an odd number of red hats, they should say "blue". The person who can see 98 hats knows exactly how many red and blue hats there is in front of them (as does the person who see's 97, 96 etc). Say for instance if the 100th guy said "red", indicating an even number of red hats in front of him, and the 99th guy see's an odd amount of red hats in front of himself, then he knows he must have a red hat to make the even amount seen by the 100th person.

Continuing this method all the way through 99 people should get the colour of their hat correct and hence a $99 profit can be ensured. The 100th person has a 50/50 chance of getting the colour of their hat correct, so a $100 profit can potentially be made.

Great! I missed this!

So the expected profit of this strategy is $99.5. I am quite sure this is optimal, as there is no "information passed forward" to #100 he cannot do better than 50%.

 

[braintic]

I'm not sure if there's a flaw in this or not, but here's my attempt:

The person who can see 99 hats (ie the 100th person) should inspect all the hats in front of them. If there is an even number of red hats, they should say "red". If there is an odd number of red hats, they should say "blue". The person who can see 98 hats knows exactly how many red and blue hats there is in front of them (as does the person who see's 97, 96 etc). Say for instance if the 100th guy said "red", indicating an even number of red hats in front of him, and the 99th guy see's an odd amount of red hats in front of himself, then he knows he must have a red hat to make the even amount seen by the 100th person.

Continuing this method all the way through 99 people should get the colour of their hat correct and hence a $99 profit can be ensured. The 100th person has a 50/50 chance of getting the colour of their hat correct, so a $100 profit can potentially be made.

Yep, straight from Khan Academy.

 

[anomalousdecay]

Can you give us a few more of these types of question seanieg?

They are interesting.