Coloured Hats. (1 Viewer)

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
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

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
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

Retired
Joined
Jun 29, 2009
Messages
9,494
Gender
Undisclosed
HSC
N/A
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

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Wait wtf am I thinking.

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

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
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

Member
Joined
Feb 15, 2012
Messages
125
Gender
Male
HSC
2012
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.
 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
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

Well-Known Member
Joined
Jan 20, 2011
Messages
2,137
Gender
Undisclosed
HSC
N/A
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

Premium Member
Joined
Jan 26, 2013
Messages
5,766
Gender
Male
HSC
2013
Can you give us a few more of these types of question seanieg?

They are interesting.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top