The gnomes

[PompOmp]

This riddle stumped me.

There are 10 gnomes, all of different heights. They are told they are going to be blindfolded and a hat of either red or blue will be placed on their head. They will then be placed in a room and they won't be able to talk to each other. They will be put in a line in order of height, tallest in back, all facing forward. Once they are in line, the blindfolds will be removed. No gnome can see the hat on top of his head. The tallest gnome will be able to see all of the other gnomes hats. The second tallest will see the 8 in front of him. The 8th gnome will see 7 hats, etc.... The gnomes will be asked, one at a time, starting with the tallest, to indicate the color of their own hat. If they are wrong, they will be killed. To determine the gnome's choice, the person administrating this evil riddle will stand in front of the line of gnomes (facing them all) and hold up 2 cards, a red one and a blue one, one in each hand. The gnome in the back will raise his hand that corresponds to the color of his hat guess. The administrator will then announce the choice the gnome made, and kill him if he is wrong.

It can be guaranteed that 9 will survive if a certain strategy is followed. When this strategy is employed, the chance that all 10 will survive is 50%. What is the strategy?

Bill

Clarifications: The reason I don't let the gnomes speak aloud is that they might try to indicate something in the tone of their voice or through speaking quickly if the person in front of them has a blue hat, etc. Thus, I attempted to remove the declaration of hat choice from the gnomes and give it to an impartial administrator who won't know their strategy. Thus, assume that the only piece of information gathered in the act of a gnome making a hat choice is the hat color indicated (i.e. the gnome can't pat the head of the gnome in front of him twice if he has a blue hat, and once if he has a red or anything like that. All the communication of information passes through the administrator who is not privy to their strategy).

[PompOmp]

I gave this to a friend today and he was confused about this, so I'll clarify. There is NO guarantee about the distribution of the hats. It is possible that every gnome will be given a blue hat, and it's possible they will all have red hats, or any combination in between.

Ask questions if you want something else clarified. Let me know if you want the answer. I'll give a small hint: the answer has applications to computer engineering/computer science.

Bill

[sajid]

hmm i give up

cant work it out :S

[PompOmp]

Originally posted by sajid
hmm i give up

cant work it out :S

If there are no objections, I'll post the answer in 1 days time. I've been out of town since Thursday morning and couldn't assist sajid earlier. As it is, speak up if you want more than one day's time to think. Or I could pm sajid with the answer.

Bill

[peace2u]

Originally posted by PompOmp
If there are no objections, I'll post the answer in 1 days time. I've been out of town since Thursday morning and couldn't assist sajid earlier. As it is, speak up if you want more than one day's time to think. Or I could pm sajid with the answer.

Bill


I would definately like the answer!! but to not spoil every brainy person's fun, please pm the answer to me:)

Thanks

[PompOmp]

Don't read below if you don't want the answer.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
To ensure that 9/10 gnomes survive and give gnome #10 a 50/50 shot, gnome 10 should be a "dummy". He will not attempt to reveal the color of his hat. Instead he will look at the 9 hats in front of him, and indicate "red" if the number of red hats is odd, and "blue" if the number of red hats is even. This way, the #9 gnome will look at the 8 hats in front of him and see either an even number of reds or an odd number, and by remembering the information the #10 gnome gave, correctly determine if his hat is red or blue. Consider this example:

1 2 3 4 5 6 7 8 9 10
R B R R R B B R R R

10 would indicate "blue" because 9,8,5,4,3 and 1 are red, an even number (and would pay with his life since he is actually wearing a red hat, and indicated blue). 9 would then see 8,5,4,3 and 1 are red, and since 10 told him the global total is even, and he sees an odd amount, he must also have a red hat. 8 would see 5,4,3 and 1 are red, knowing that 9 is red, and thus know that the 5 known reds are not the even global amount as 10 testified, so he also must have a red hat. 7 would see, 5,4,3 and 1 are red, knowing that 9 and 8 are red, which is an even number as 10 said, so 7 must have a blue hat. The process continues with each gnome keeping track of the evenness or oddness of the group until the last 9 correctly determine their hat color. If 10 happens to see be wearing a blue hat when the sum is even, he too lives.

The key to understanding this riddle is that the last gnome actually incorporates 9 pieces of information into his statement of either red or blue. Any attempt to just indicate the color of the hat directly in front of you, or the relationship between the 2 hats in front of you, or so on will fail, because there is no liberty to convey anything but your hat color after the first gnome goes if you are to guarantee a 9/10 success rate.

This concept is used in computer science when sending data over a network. A "parity bit" is a way of checking to see if data has been sent accurately. The bit at the end of the packet sent is derived from the preceeding bits of the packet and at the other end of the connection, the bits are examined. If the parity bit doesn't match the information, the information is considered garbled during transfer and a request for a resend is made. However, when just a bit is used (a bit is a piece of data than can only have 2 values like true/false, off/on, or, in this case, red/blue), when information becomes garbled, there's a 50/50 chance the parity bit won't catch the garble (because it's just as likely to look correct as incorrect). Rather than just using a bit, a larger value is often used in what's called a "checksum."

Spread the good news,
Bill

[kaphirgoyim]

I'm just glad I aint one of those ten gnomes......:banghead: