Hat Trick
Moderator: Michael Wallace
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Hat Trick
Here's another problem for you:
10 Countdowners are captured by merciless Crab people They are placed in a queue all facing forward so that each Countdowner can only see the Countdowners in front of him (ie the one at the back sees the other nine, the one at the front sees no one at all and so may as well have their eyes shut) A hat is placed on each Countdowner's head, either black or white (each colour is equally likely and independent of other hats) To gain their freedom a countdowner must correctly state the colour of their hat. If the Countdowner is incorrect he/she will be turned into a crab person! Countdowners cannot see their own hats and are not allowed to communicate once hats are on heads. However they were allowed a strategy discussion session before the ordeal took place. What is the maximum number of Countdowners that can be saved from a crabby fate? (You cant just say all 10 have a lucky guess) You have to find the best strategy. Good luck!
Dinos
10 Countdowners are captured by merciless Crab people They are placed in a queue all facing forward so that each Countdowner can only see the Countdowners in front of him (ie the one at the back sees the other nine, the one at the front sees no one at all and so may as well have their eyes shut) A hat is placed on each Countdowner's head, either black or white (each colour is equally likely and independent of other hats) To gain their freedom a countdowner must correctly state the colour of their hat. If the Countdowner is incorrect he/she will be turned into a crab person! Countdowners cannot see their own hats and are not allowed to communicate once hats are on heads. However they were allowed a strategy discussion session before the ordeal took place. What is the maximum number of Countdowners that can be saved from a crabby fate? (You cant just say all 10 have a lucky guess) You have to find the best strategy. Good luck!
Dinos
Re: Hat Trick
I think I've got it, but it's sort-of cheating as a smaller scenario has appeared on an Oxford admissions test paper.
Edit: Wait, there isn't a fixed number of hats of each colour. That rather changes it (and now I can't see how it can be done).
Edit: Wait, there isn't a fixed number of hats of each colour. That rather changes it (and now I can't see how it can be done).
- Joseph Bolas
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Hat Trick
The puzzle you may be thinking of is where there are 4 people and 2 black and 2 white hats. I know thats the one I have on a Perplex City card.Conor wrote:I think I've got it, but it's sort-of cheating as a smaller scenario has appeared on an Oxford admissions test paper. Edit: Wait, there isn't a fixed number of hats of each colour. That rather changes it (and now I can't see how it can be done).
I assume that because there is 10 people, there will 5 of each colour, but if not, then surely theres no way to work it out, unless you guess, so you may have to sacrifice someone in this puzzle?
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Hat Trick
I'm going to assume that 1) they can declare in any order 2) they can hear each other's declarations. Otherwise the problem does appear to be insoluble (or rather there's no better strategy than guessing.)
The naive strategy has an average of 5 people saved, and a minimum of 0. (I'm not sure if we're supposed to be maximising the worst-case scenario or the average-case scenario.)
If we divide the people into 5 pairs, and the back person in each pair says the colour of the person in front (which they can see), then we save at least 5 of them (the front ones in each pair) and 7.5 on average (half the back ones will happen to say the right colour.)
I came up with an optimal solution but I'm not sure if it's what's intended. I can't think of anything better though, so here goes:
The person at the back says the colour of person in front of him, so he survives with probability 1/2 (which is as good as can be done, given that you can't know anything about him.) Hence everyone knows the colour of the second guy from the back.
The second guy from the back says his own colour, but only if the person in front of him also has the same hat. Otherwise he stays silent.
Hence one way or the other, everyone knows the colour of the guy two from the back. He does the same, saying his colour if it matches, or keeping silent if it doesn't.
This proceeds all the way to the guy at the front, who just says his colour. Anyone left who hasn't said his colour can now say it.
This saves at least 9 and on average 9.5, which is optimal in both respects.
The naive strategy has an average of 5 people saved, and a minimum of 0. (I'm not sure if we're supposed to be maximising the worst-case scenario or the average-case scenario.)
If we divide the people into 5 pairs, and the back person in each pair says the colour of the person in front (which they can see), then we save at least 5 of them (the front ones in each pair) and 7.5 on average (half the back ones will happen to say the right colour.)
I came up with an optimal solution but I'm not sure if it's what's intended. I can't think of anything better though, so here goes:
The person at the back says the colour of person in front of him, so he survives with probability 1/2 (which is as good as can be done, given that you can't know anything about him.) Hence everyone knows the colour of the second guy from the back.
The second guy from the back says his own colour, but only if the person in front of him also has the same hat. Otherwise he stays silent.
Hence one way or the other, everyone knows the colour of the guy two from the back. He does the same, saying his colour if it matches, or keeping silent if it doesn't.
This proceeds all the way to the guy at the front, who just says his colour. Anyone left who hasn't said his colour can now say it.
This saves at least 9 and on average 9.5, which is optimal in both respects.
-
- Series 80 Champion
- Posts: 2707
- Joined: Mon Jan 21, 2008 10:07 am
- Location: Sheffield
Re: Hat Trick
Correct Soo thats the best strategy (there are probably a few others with slight variations). I think I know the 4 people scenario you mean, Joseph (there's also a wall behind the front person right?) but I chose this one as its probably a bit more obscure (If not a bit ambiguously explained by yours truly!)
D
D
Re: Hat Trick
Nice one Soo, I had a think about this last night while I dozed off, and I couldn't get past splitting them into pairs as you first said, which only guarantees 5 survivors.
- Joseph Bolas
- Fanatic
- Posts: 2446
- Joined: Mon Jan 21, 2008 9:19 am
- Location: Liverpool, UK
Re: Hat Trick
Yes Dinos . This is what the card looks like: http://i89.photobucket.com/albums/k210/jpbolas/080.jpgdinos_the_chemist wrote:Correct Soo thats the best strategy (there are probably a few others with slight variations). I think I know the 4 people scenario you mean, Joseph (there's also a wall behind the front person right?) but I chose this one as its probably a bit more obscure (If not a bit ambiguously explained by yours truly!)
D
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Hat Trick
Cheers
-
- Series 48 Champion
- Posts: 481
- Joined: Mon Jan 21, 2008 7:08 pm
Re: Hat Trick
You're applying to do maths at Oxford Conor?Conor wrote:I think I've got it, but it's sort-of cheating as a smaller scenario has appeared on an Oxford admissions test paper.
Edit: Wait, there isn't a fixed number of hats of each colour. That rather changes it (and now I can't see how it can be done).
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Hat Trick
Cambridge Maths last I heard, but the admission papers are similar. It's a year or two yet though, I think.
-
- Post-apocalypse
- Posts: 13312
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Hat Trick
Just clicked on this. So Charlie knows that if he is wearing a white hat then Dave would know his own hat to be black. Dave remains silent Charlie announces that he himself is wearing a black hat.Joseph Bolas wrote:Yes Dinos . This is what the card looks like: http://i89.photobucket.com/albums/k210/jpbolas/080.jpgdinos_the_chemist wrote:Correct Soo thats the best strategy (there are probably a few others with slight variations). I think I know the 4 people scenario you mean, Joseph (there's also a wall behind the front person right?) but I chose this one as its probably a bit more obscure (If not a bit ambiguously explained by yours truly!)
D
-
- Series 48 Champion
- Posts: 481
- Joined: Mon Jan 21, 2008 7:08 pm
Re: Hat Trick
That's pretty hardcore Conor! Especially if you have to do problems like that for the entrance exam... good luck with applying though. even if it's a while away yetCharlie Reams wrote:Cambridge Maths last I heard, but the admission papers are similar. It's a year or two yet though, I think.