Fog Creek Software
Discussion Board




Solution: Fogcreek programmers

100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can't see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says "what color is your hat?" the fogcreek programmer can only answer "red" or "blue." the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can't communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?


Answer:

It seems really simple.

The last person in the queue says the colour of the hat in front. The person in front then says the colour he/she hears. This would of course result in 50% scenario as the worst case scenario of (B,R,B,R type pattern).

I would recommend a slightly sneaky strategy.

The last person in the queue says the colour of the hat in front, The 2nd person will hear it and would normally say the colour he hears. But how about he says the colour of the hat normally "Blue" or "Red" (that he heard) only if the person in front has the same coloured hat. But if he finds that his hat is Red but the guy in front has Blue he should say "Achooo Red" which could be interpreted by the guy in front as NotRed. This is at least 99% survival. The guy to answer first has a 50% chance of course.

Tell me if im right with the original answer, anyone. Any corrections and nitpicking welcom.

Mohammed Saiyad
Wednesday, July 14, 2004

That's one solution, but not the best... If the assassin knows they are going to use it, then he can alternate the hats on their heads and make 99 of them die.

What's a good solution even if the assassin knows their plan?

Michael H. Pryor
Fog Creek Software
Wednesday, July 14, 2004

Acceptable losses?

Every odd programmer says the color of the person in fronts hat, every even repeats the previous.
Minimal 50%. ( alternating colors )
Possbible 100% ( same color )
Expect ~75%

Where is DHS when you need em?

B
Wednesday, July 14, 2004

D'oh the 'solution' is much better than mine.

B
Wednesday, July 14, 2004

Michael if the assassin has the power to alternate things during the course of the game, then hearing what the guy behind you says would mean absolutely nothing which would probably ruin the whole meaning of the game.

Im sure you cant allow the assassin to do change something after someone's heard the guy behind them shouting out the colour.

Do you have any ideas to overcome the problem of the assassin adapting to the game.

Mohammed Saiyad
Sunday, July 25, 2004

I think if the assassin is allowed to change the hat colours during the game, the the programmers are essentially stuffed. Anything said can only convey information about the state when it was said - if the state can then change, all previous information is meaningless and each programmer is reduced to blind guesswork.

David Clayworth
Monday, July 26, 2004

The answer: think parity. That saves 99 (in general, n-1) people. (e.g., last person says Blue if he sees an odd number of blue hats, and red otherwise. So next one can already figure out what hat he has, and so can every other one).

DEBEDb
Wednesday, August 11, 2004

I came out with an idea as the following:

First let's label the programmers as p1 to p100.

p1 can see all the colors, if the color of p2 and the color of p100 is the same, he says blue, otherwise he says red. Now, p2 knows the color of his hat, he'll be saved, and p100 will know his color too after p2 says his color. So p100 is saved too. Then p3 needs to sacrifice himself to save p4 and p99, and so on...

Finlly, all programmer with odd label before and including 67 will have a half chance to die. All other odd number programmers and all even number programmers are saved.
The total number of programmer saved = 50 + 17 + 33/2 = 83.5

Please let me know if anything goes wrong here. Thanks.

Li Chen
Sunday, September 26, 2004

I think you can save all but the last programmer.

There is noone who sees the hat of the last programmer (p100) so no information about him is available. The best he can do is guess and survive with 50% probability.

Given that, the programmers agree to the following rule:

If the number of red hats p100 sees is odd he answers red, if this number is even, he answers blue.

All the others can then deduce the color of their individual hats as follows:

p99 knows how many red hats are in front of him. if this number is even and p100 said blue (meaning even), his hat must be blue. if the number is odd, and p100 said blue (even) he must wear a red hat. the remaining 2 cases can be handeled the same way. p99 survives.

the same argument applies to any pn: he knows the 'oddness' of the number of red hats behind him (except the hat of p100) because he hears them and the 'oddness' of the programmers in front of him (he sees them). given this 2 numbers he can deduce the color of his own hat.

Is this working - or did i make an error ?

Who will be p100 ? Joel ?

Thomas
Tuesday, September 28, 2004

Oops - I am really sorry about the confusion caused by numbering the programmers in another way than Li Chen did...

Thomas
Tuesday, September 28, 2004

An another side-note: If p100 is cheating, he will cause all others to die and will still survive with 50% probability.

If two programmers agree to get rid of some others, they must agree and take care that those colleagues they want to get rid of are positioned between them.

Unless some other two want to get rid of one of them and agree to the same...

This gets pretty interesting and the schema requires a good amount of trust in the ability of all the others. so get the weaklings who cannot count and hence do not deserve to work at fogcreek.com positioned at the places p1...

Thomas
Tuesday, September 28, 2004

If the number of red hats p100 sees is odd he answers red, if this number is even, he answers blue.

p99 knows how many red hats are in front of him. if this number is even and p100 said red (meaning odd), his hat must be red.

So p99 determined the color of his hat. Therefore to survive he must say red. However this will tell p98 that the number of red hats is odd while we know it is even!

Jad
Friday, October 01, 2004

The easiest would be that they all call out the color of the hat in front of them. That would save 99 programmers for sure. Only The first would have to hope he has the same coloured hat as the 1 in front of him

Patrick
Tuesday, October 05, 2004

doh never mind, brain fart.

Patrick
Tuesday, October 05, 2004

hmm ok

I see 98 of them surviving.

no 100 sees the color of the hat infornt of him and tell / whispers it to the person in front ( or pokes him and says red or blue )

Now people numbered 1 to 99 have some one behind them so they would bet a corect answer. ( assuming no one lies )

The last person is in a spot he cant get any help, he could try and could all of the hats and work out hwat is left but yo uare assuming the colours are 50 / 50 , what if they were 25/75 or 90/10

maybe one of the gratefull infront of him released may turn around and quietly tell him what he has.

So we have 99 successfull, and Mr 100 has a 50/50 of getting it right.

Nikky
Wednesday, October 06, 2004

*  Recent Topics

*  Fog Creek Home