Hat Trick

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
Dinos Sfyris
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Hat Trick

Post by Dinos Sfyris »

Here's another problem for you:

10 Countdowners are captured by merciless Crab people :twisted: 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
Conor
Series 54 Champion
Posts: 541
Joined: Mon Jan 21, 2008 7:29 am
Location: Luton - UK

Re: Hat Trick

Post by Conor »

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).
User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Hat Trick

Post by Joseph Bolas »

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).
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.

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?
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Hat Trick

Post by Charlie Reams »

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.
Dinos Sfyris
Series 80 Champion
Posts: 2707
Joined: Mon Jan 21, 2008 10:07 am
Location: Sheffield

Re: Hat Trick

Post by Dinos Sfyris »

Correct Soo :D 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
User avatar
Jon Corby
Moral Hero
Posts: 8018
Joined: Mon Jan 21, 2008 8:36 am

Re: Hat Trick

Post by Jon Corby »

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.
User avatar
Joseph Bolas
Fanatic
Posts: 2446
Joined: Mon Jan 21, 2008 9:19 am
Location: Liverpool, UK

Re: Hat Trick

Post by Joseph Bolas »

dinos_the_chemist wrote:Correct Soo :D 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
Yes Dinos :D. This is what the card looks like: http://i89.photobucket.com/albums/k210/jpbolas/080.jpg
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Hat Trick

Post by Charlie Reams »

Cheers :)
Julian Fell
Series 48 Champion
Posts: 481
Joined: Mon Jan 21, 2008 7:08 pm

Re: Hat Trick

Post by Julian Fell »

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).
You're applying to do maths at Oxford Conor?
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Hat Trick

Post by Charlie Reams »

Cambridge Maths last I heard, but the admission papers are similar. It's a year or two yet though, I think.
Gavin Chipper
Post-apocalypse
Posts: 13194
Joined: Mon Jan 21, 2008 10:37 pm

Re: Hat Trick

Post by Gavin Chipper »

Joseph Bolas wrote:
dinos_the_chemist wrote:Correct Soo :D 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
Yes Dinos :D. This is what the card looks like: http://i89.photobucket.com/albums/k210/jpbolas/080.jpg
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.
Julian Fell
Series 48 Champion
Posts: 481
Joined: Mon Jan 21, 2008 7:08 pm

Re: Hat Trick

Post by Julian Fell »

Charlie Reams wrote:Cambridge Maths last I heard, but the admission papers are similar. It's a year or two yet though, I think.
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 yet
Post Reply