General Discussion => Other Discussions => Math and Science => Topic started by: Builderboy on July 21, 2012, 12:49:42 am
Title: Red and Blue hats
Post by: Builderboy on July 21, 2012, 12:49:42 am
So a large village of people lives by a forest that is terrorized by a goblin. Occasionally when a large group of villagers go out to hunt, the goblin takes kidnaps them and plays a cruel game with them. The goblin first forces the villagers to stand in a single file line with each villager facing the one in front of him, and then places either a red or a blue hat on each villager such that they do not know what color hat they have on. If any villagers move or make any sort of signal, the goblin kills all of the villagers immediately. The goblin then starts from the back of the line (starting with the villager with nobody behind him that is) and asks them which color hat they are wearing. The villagers must either answer red or blue, and any variation or movement once again gets all the villagers killed. If the villager is wrong, he gets his head bitten off, and if he is correct, he is permitted to live, but must stand in his location without moving until the goblin is finished. After the goblin is finished asking each villager, all the ones still alive are permitted to leave safely.
The villagers (or at least the survivors) over time have come to learn the goblins game very well, and so set out to determine if there is a best strategy they can use to ensure the highest survival rate on average. They keep in mind that all villagers can hear the responses of all villagers before them, and a villager will know when a fellow villager answers incorrectly based on the sound of their head being eaten. All villagers can also see the hat color of all villagers in front of them.
So the question stands, if all of the villagers can come up with a strategy beforehand, what would the most optimal strategy be?
Title: Re: Red and Blue hats
Post by: Hayleia on July 21, 2012, 02:57:29 am
PMed my answer :) I can save at least N-2 villagers (considering N>2)
Title: Re: Red and Blue hats
Post by: Builderboy on July 21, 2012, 05:07:31 am
You can save N-1 villagers with just a slight modification of your logic :)
Title: Re: Red and Blue hats
Post by: Scipi on July 21, 2012, 06:41:07 am
Well, if any of the villagers in the line have ADHD, they're all screwed :P jk
Is there an even number of red and blue hats or are the numbers arbitrary?
Title: Re: Red and Blue hats
Post by: cyanophycean314 on July 21, 2012, 10:02:21 am
Hmmm.... maybe this has something to do with sacrificing to let other people know in front of you what they're wearing? ???
Title: Re: Red and Blue hats
Post by: Hayleia on July 21, 2012, 10:07:56 am
You can save N-1 villagers with just a slight modification of your logic :)
PMed you my update :P
Title: Re: Red and Blue hats
Post by: thepenguin77 on July 21, 2012, 03:39:23 pm
Perhaps I'm misunderstanding the rules. But I'm fairly certain I can save all but the first villager.
Spoiler For Spoiler:
If the person in front of you has a red hat, you respond with a high pitch voice.
If the person in front of you has a blue hat, you respond with a low pitch voice.
Title: Re: Red and Blue hats
Post by: parserp on July 21, 2012, 03:44:12 pm
But are they asking from the front person to the back person? If so, thep's answer wouldn't work. :-\
EDIT: didn't read the whole post :P Looks like thep's answer saves all but .5 of the first person. (He has a 50% chance of guessing what hat he has on) :P
Title: Re: Red and Blue hats
Post by: thepenguin77 on July 21, 2012, 04:03:23 pm
Mine would work, but I'm fairly certain it's cheating.
Title: Re: Red and Blue hats
Post by: Builderboy on July 21, 2012, 04:31:11 pm
Lol yeah that is cheating
Title: Re: Red and Blue hats
Post by: Scipi on July 22, 2012, 10:41:57 am
Sent in my answer. It assumes the villagers know how many red and blue hats there are though :P