Comments:

Flat Nested Threaded Embedded

Oldest First Newest First

This is what I think By sudipta_cht on Saturday, September 09, 2006 (UMST)

Since there is no bound or relation between the number of red or blue hats, everyone taking a random guess is not assured to save at least half of them: it will certainly vary. However, if every guy at an even position (100, 98, etc) says the color of the hat of the person right in front of him, then the odd guys (i.e. people at 99, 97, etc) are assured to be saved. Also, in the best case, all 100 of them survive (i.e. if all the hat colors are in pairs) and in the worst case, at least 50 live. P.S. - Why are programmers so dumb? 100 of them can beat the crap out of one assasin any day! :D Reply to this Comment

Another solution By sudipta_cht on Saturday, September 09, 2006 (UMST)

Or else, the 100th guy can count the number of blue or red hats and shout out the color that has the maximum number. Everyone else shouts the same color no matter what. That way, even though guy #100 is doomed, at least the max number of people will be saved. However, again, in the worst case, only 50 people will live and all else die. In the best case, again, all 100 may live. Reply to this Comment

Count the hats! By davee123 on Tuesday, September 19, 2006 (UMST)

Sadly, the LAST programmer (first to be asked) has a 50/50 shot of living. But on the plus side, if you trust him, everyone else can live! Here's how it works: The last programmer counts the number of red hats in front of him. If it's odd, he says "red". If it's even, he says "blue". The next programmer in line then looks at the number of red hats in front of him. If the person behind him called out "red", and he sees an odd number of red hats, he *knows* his hat is blue, and can call it out. And if he sees an even number of red hats, he *knows* his hat is red. Etc. This proceeds all the way up the line-- and assuming nobody makes a mistake, you're all set! DaveE Reply to this Comment

Play a trick-funny answer By richa on Thursday, October 12, 2006 (UMST)

The programmers can see the reflection of the hat on the glass of his watch and say the correct answer... Reply to this Comment

Analogy By Hydrogen on Thursday, November 30, 2006 (UMST)

This looks to me like a question related to data compression, Blues and Reds being 1s and 0s. I was thinking whether we can have some martyrs (say first 10 of them, who would die for the sake of the programming community) that would contain the compressed information about the rest of the guys. It can be sort of a header information that the others can easily understand. However I couldn't find an algorithm for that. I am not a comp. science guy  anyway. Please reply if the above approach makes sense and if yes, what would be a suitable algorithm? If this works, then we definitely have more than 50% of survival rate... Reply to this Comment

Dave123 got it By Celton on Thursday, December 07, 2006 (UMST)

Dave123 already figured it out (above) with a 99.5% minimum survival rate. Reply to this Comment

Hats By bobewalton on Wednesday, December 13, 2006 (UMST)

You all are taking something for granted, no where in this does it say that the hat colors will be evenly split. Reply to this Comment

At least a 99% survival rate By Guild on Friday, December 15, 2006 (UMST)

This is the strategy I would suggest. As the first programmer asked is at the back of the line, he will state the color of the hat in front of him, therefore communicating to the next in line what their hat color is. Proceeding like this, 99 are guaranteed to survive, while only the first has a 50% chance. Reply to this Comment

Leaving a lot to chance By Guild on Friday, December 15, 2006 (UMST)

If we approach this situation under somewhat realistic conditions, there is no way of guaranteeing that the programmer at the back would actually clearly see all 99 in front of him to clearly identify and count their hats. Smaller people might be obscured by taller, bigger ones behind them. If he gets one wrong, then the strategy, and potentially everyone in front of him, is doomed. Since they can't know if the ones before them have died, there is no way to correct the potential error. Check out my solution. With the exception of the 50% chance of the first asked, it's foolproof. Reply to this Comment

Yes, Dave got it... here's another sol. By Hydrogen on Sunday, December 17, 2006 (UMST)

I agree with Dave's solution. This is another probable solution based on the assumption that the programmers always get to "hear" what the person behind him said. They can think of a strategy to spell the words hardly or softly and thus encoding the information about the person infront of him. For example, if the person infront is wearing a Red hat then the first pro will say "RReDD" else "red". For Blue it can be "BLUEEE" and "blue". The advantage of this solution is that each programmer need only see the person right infront of him, and this works fine in Guild's scenario as well. Disadvantage: well, what if the assassin ask the pros to write their hat color on a piece of paper and then hands it over to the next person? i.e, no voice encoding.. phew! Reply to this Comment

clarification for the above By Hydrogen on Sunday, December 17, 2006 (UMST)

I actually meant, for a Red hat infront the current programmer would pronounce his hat color very hardly (could be "RReDD"/"BLUee")  and for a Blue hat in front he would say "red"/"blue"... hope it clarifies. waiting for more comments :-) Reply to this Comment

My solution By danielny on Friday, December 22, 2006 (UMST)

There are a couple of flaws in some of your solutions. The problem states that the only thing the programmers are allowed to say is "red" or "blue". So shouting out the number of red or blue hats is out of the question. Also never does the problem state what the distribution of color is. My strategy would be for the programmers in the back row to say the color of the hat of the programmer in front of them. That would give a minimum of 50% survival rate, probably higher because it is very likely that at least 1 set of back and front row programmers will have the same colore hat. Reply to this Comment

I disagree... By Hydrogen on Tuesday, December 26, 2006 (UMST)

1. There is only one row and they are all lined up. i.e, no front row or back row.. ok, that was just a clarification. So in that case you may actually be reducing the chance of survival.   2. No one shouts out the count in Dave's solution. Instead, the last person says just Red or Blue by checking if the number of Red hats is odd or even based on their discussion before neing lined up...so that the others in front can deduce the color of their hat based on the hats that they see infront, what the others behind have said and also on the first person's response.     Reply to this Comment

Mistake in Guild's solution By kayesq on Saturday, January 27, 2007 (UMST)

Guild's solution cannot guarantee a 99% survival rate by having each programmer state the color of the hat in front of him, because the programmer must also state his own hat color in order to survive.  If 100, behind me, sees that my hat is blue and tells me so, and I see that 98, ahead of me, is wearing red, I cannot save myself and warn 98 at the same time, because it would require me to state both "red" and "blue."           I like Dave's solution because the prompt does, in fact, tell us the programmers can see the hats of those in front, so they should be able to count the hats of those ahead.  Good work! Reply to this Comment

Solution By bobewalton on Monday, March 05, 2007 (UMST)

I had another thought on this... When they are in line, have the rear most person change the volume of their voice by the hat on the programmer in front of them. That way that person can say their color and save the person in front of them. It provides for a 99.5% survival rate. (.5 because the first person has a 50/50 shot at guessing his/her color. Reply to this Comment

Hat trick. By sdenhartog on Monday, April 23, 2007 (UMST)

Each programmer would just say the color of the hat in front of him.  Since the assasin starts in the back and each can the hat in front, only the person in the back would have a 50/50 chance of dying regardless of the hat distribution.     Reply to this Comment

Guild already stated the right solution By sdenhartog on Monday, April 23, 2007 (UMST)

Having reread the comments. Reply to this Comment

dave is right 99.5 - here is the KISS method By msftpfessd on Wednesday, May 30, 2007 (UMST)

Dave's probability is right.  The first person "tells" the next guy his color.  Red or Blue.  If # 2 is red and #3 is red then 2 enthusiastically states "RED!!!" If 2 is red and #3 is blue, then 2 sadly states "red... :("  Sad red = blue, happy red = red, sad blue = red, happy blue = blue.  Of course you need to do "extra credit" in MS interviews so always ask if there isn't a Darth Vader mask on each person where their voices sound the same.  Reply to this Comment

no solution yet By markz on Wednesday, June 06, 2007 (UMST)

Dave's solution doesnt work. His solution implies possibility of 2 answers. One is for assasin and one for the person in front. That is not how problem describes it. For the same reason name the color of the hat in front doesnt work. In fact that one could get all of them but one killed. If hats go red-blue-red-blue... then only the first one in line will live. Reply to this Comment

Just guessing By microhard on Saturday, October 13, 2007 (UMST)

it's a vertical row, not a horizontal row. you see who is in front of you. so no matter what strategy you employ everyone is still at a 50 50 risk because you don't know if it started properly as a "thread" because you don't get to know if he was wrong and died. everyone is relying on the first guy being right. so if he was, everything changes. everyone gets to live. Reply to this Comment

Just think about it By buphoff on Wednesday, November 14, 2007 (UMST)

Ok so it seems simple to me if you don't over think it. If the n-1 person always says the color of the n person's hat then 99/100 are saved. The first guy...too bad for him he is sitting with a 50/50 chance. So on average this method saves 99.5% Reply to this Comment

only one person has to die By m_love on Thursday, November 15, 2007 (UMST)

if a person says the color of the person in front in a low voice, the person in front has a blue hat, if its a high voice, the person in front has a red hat. assuming everyone understands pitch, the first person is the only person at risk of dying, because he/she has to guess at his/her color, but if he and everyone else use the high/low voice technique, no one else has to die. Reply to this Comment

LISTEN TO ALL THE SHOUTS By MikeH on Thursday, December 06, 2007 (UMST)

Dave's solution doesn't work.  A person can't both save himself and signal to the person in front of him whether he sees an even number or odd number of red hats.  The way this can work is as follows.  Again the first person may be sacrificed, but all the others are bound to survive provided they don't make a mistake. The first person signals whether he sees an odd or even number of red hats by shouting red for odd and blue for even, (as Dave suggested).  The first person will die if his hat doesn't match the colour he shouts.  Each person then can determine if the person immediately behind them sees an odd or even number of red hats depending on whether they have heard in total an odd or even number of "red" shouts respectively when it is their turn. They can then save themselves by comparing this against the number of red hats that they see. It is not difficult to show that if a person saves themselves in this way, they will also give the correct signal to the person in front of them whether they can see an odd or even number of hats, (just consider the four permutations of what the n-th person has heard and what they can see - what will they then shout to save themselves and what does that mean that the (n+1)th person will then have heard - it agrees with what the n-th person could see). This works for the second person.  By induction, then the third, fourth, fifth, ... hundredth person is saved. Reply to this Comment

Good idea-but wont always worl By michael999 on Wednesday, February 13, 2008 (UMST)

What if all hates are red? When he announces red (for odd) the person in front (99) will see even (98 pepole in front) and go with blue.Following this process will give you only 50% survival Reply to this Comment

To Giuild By michael999 on Wednesday, February 13, 2008 (UMST)

That makes no sense. You would only save every other person for a guaranteed 50% survival rate.If person 100 says red (because 99 is ted). However 98 is blue. Person 99 will say red to save himself. He will not say blue to help 98. 98 will start again, so we are back to 50% not 99% as you dsuugested Reply to this Comment

Ambiguious Question By sonalp on Thursday, March 13, 2008 (UMST)

Here lots of ambiguity is there in question in question they have mentioned that programmers are lined in a row. and then its specified that programmer can see hat of programmers in their front. how???????????? row and infront? Reply to this Comment

My solution By meenu on Thursday, March 13, 2008 (UMST)

Strategy they have to employ is when someone is Red, shout loudly "Red" to indicate to other person in front of him that his hat  is "Black' else shout in slow voice to indicate to other person in from of him that his hat is "Red". Assume all can talk and hear properly. In this way, 99 people will be saved worst case, except the first person from the back else best case is 100, all saying correctly. Reply to this Comment

It works By rennyn on Thursday, April 24, 2008 (UMST)

That's the one I came up with as well.   To clarify...   Rules agreed upon beforehand: If the hat in front of you matches your hat, softly speak your hat color. If the hat in front of you is the other color, yell your color.   Person #1 has a 50/50 shot of dying, but everyone else will live if they can follow the instructions. Reply to this Comment

p(survive) = .66 mathematically By stanbca on Thursday, May 01, 2008 (UMST)

Vocal inflection aside, from a strictly numerical procedure, I bumped p(survive) to 0.66 by eliminating self-interest and taking advantage of strings: Guy 1 states Guy 2's Hat. if Guy 3 Hat = Guy 4 Hat, Guy 2 states Guy 3 Hat if Guy 3 Hat <> Guy 4 Hat, Guy 2 repeats Guy 1's statement. for 500 iterations, min survive = 59, max = 74 E(p)= .664 ====== The counting-ahead and saving-self by probability is less successful, but > 50%: for 500 iterations, min survive = 51, max = 67 E(p)= .574 Reply to this Comment

what does that accomplish? By insidi0us on Monday, May 19, 2008 (UMST)

you never know if the guy before you was right, or if he was killed, so how can you rely on him? lets set up a scenario: 1st = red 2nd = red = me 3rd = blue 4th = red we can stop there. first of all, IF the first guy knew his color, he would then say red, softly, to imply that mine was the same color. i wouldn't know to believe him, because i dont know if he died, so i have a 50/50 chance, so i'll just choose to trust him because it doesnt matter which one i pick, its 50/50. plus that was the strategy we decided on, so i'll stick to it. i say RED!!! to imply that #3 hat is blue. everyone abides by the rules, and so it continues. #3 guy will say BLUE!! to imply that #4 is red, and so on. but as stated, it all depends on the first guy, and you are never told if he was right, and no one is ever told if the previous person was killed, therefore you cant know what color your hat is, therefore you can't inform the guy in front of you of his hat color through the use of any communication method. i say 50/50, no matter what strategy you employ. Reply to this Comment

DAVEE123 IS right. By indrajit_p on Saturday, May 24, 2008 (UMST)

Don't make it a congregression of 100 dumb-as-the-seventh-hell people here. If you poeple don't understand why I am saying,this go take a IQ test to know why before attempting the Microsoft puzzles.   Dave is RIGHT as the seventh hell. And it's plain as water to figure it out why.   There has been no better solution yet, and I don't think it's possible to guarantee the survival of the programmer who is first from the end anyway because there is no-one to give him any clue about anything.   But as soon as he gives splits the 99 in front of him into red=even, blue = odd or red = odd, blue = even, then everyone following him (up the line) can keep a track of the evenness or oddness of the colors including their own hat, see the evenness and odness of the hats in front (excluding their own) and just say the color that does not match the evenness or oddness of the two sets (1. including, 2. excluding their own hat). Note that ALL programmers in front can hear what ALL of the programmers behind them said. So all of them will know the even/odd ness of red/blue hats in the set of 99 as soon as the last guy pronounces it. AND, all of them can keep track of it as and when each and everyone UP the line keeps saying correctly the color of their own hat.   for those who can't figure it out still, not only Microsoft, the entire field of software programming and design is NOT FOR YOU.   sadly Indrajit Reply to this Comment

Just an Idea By ShadClaiborne on Friday, May 30, 2008 (UMST)

I was analyzing the requirements and it said that once in line, the programmers can not communicate in any way other than what was already specified. Communicate to whom? That doesn't necessarily mean the just to Assain, does it?   The idea; Potentially could allow 99-100% of the programmers to live, with the potential sacrafice of just one programmer-therefore yielding 99%. What if they agreed that if a color is said in a certain way, it notifies the guy in front of them what color their hat is. Starting at the end of the line the guy says "red" with a shrill-the shill representing red, and the absense of a shrill could, for example, represent blue. You could even agree on a standard of indicators that represent either color, so that it isn't too obvious.   Just an idea. Reply to this Comment

Just an Idea By ShadClaiborne on Friday, May 30, 2008 (UMST)

I was analyzing the requirements and it said that once in line, the programmers can not communicate in any way other than what was already specified. Communicate to whom? That doesn't necessarily mean just to Assain, does it?   The idea; Potentially could allow 99-100% of the programmers to live, with the potential sacrafice of just one programmer-therefore yielding 99%. What if they agreed that if a color is said in a certain way, it notifies the guy in front of them what color their hat is. Starting at the end of the line the guy says "red" with a shrill-the shill representing red, and the absense of a shrill could, for example, represent blue. You could even agree on a standard of indicators that represent either color, so that it isn't too obvious.   Just an idea. Reply to this Comment

My solution By vrp12 on Friday, July 11, 2008 (UMST)

I didnt read all the comments, so dont know if someone already had this or similar idea.. Before standing in the line the 100 programmers come up with this strategy: - Whoever is the last in the line (to answer first) will call out the color of hat on the guy just in front of him. So, 50% chance this guy could live or may be die. - Now the next guy knows the color of his hat - lets say its Red. The group strategy could be to "voice code" the color of hat of the guy in front of you. For example, This second guy says "REEEEEEEEEED" if the color of hat in front of him is Blue and a shorter version "Red" if the color of hat in front of him is Red. Thus the second guy survives and passes the info to the next guy and so on. Does this work?? Reply to this Comment