Sunday, November 28, 2004
Math
Sometimes, you run into a math problem that is so amazingly beautiful that it knocks your socks off. Consider the following problem:
You and 99 brave Polish soldiers are captured by a mad hatter in Baghdad. He is about to turn everyone over to Iraqi militants, when he suddenly spots you wearing a pair of telltale white earbuds. "Hrrmmm," he says in a thick accent, "Bring the iPod to papa." "Not so fast," you counter, "You have to let us free in exchange." "Humph," he says, "I have a better idea."
He lines you all up single file going down a staircase outside his house and chains everyone to the hand rail so tightly that nobody can turn around; at least everyone can see the heads of people below them. The hatter grins smugly and says, "I'll return shortly and place randomly either a red or green turban on your head. Guess the color correctly and I'll set you free; say anything else and your life is mine." As he passes you on the bottom step, he swipes the iPod from your back pocket, pokes you in the ribs, and says, "Ho, I think I'll start at the top and ask you last."
You think you're doomed, until your fairy godmother appears in a flash of light. "Quick," you say, "Get me out of this!" "Sorry, sweetie," she tells you, "I bent the magic wand, and I'm also colorblind, so I can't even tell you which turban you'll be wearing." "But," she says comfortingly, "I can translate anything you like into Polish."
What should you say to the rest of the soldiers so that as many people as possible (including yourself) will go free?
I'll post the solution as a comment in a week.
You and 99 brave Polish soldiers are captured by a mad hatter in Baghdad. He is about to turn everyone over to Iraqi militants, when he suddenly spots you wearing a pair of telltale white earbuds. "Hrrmmm," he says in a thick accent, "Bring the iPod to papa." "Not so fast," you counter, "You have to let us free in exchange." "Humph," he says, "I have a better idea."
He lines you all up single file going down a staircase outside his house and chains everyone to the hand rail so tightly that nobody can turn around; at least everyone can see the heads of people below them. The hatter grins smugly and says, "I'll return shortly and place randomly either a red or green turban on your head. Guess the color correctly and I'll set you free; say anything else and your life is mine." As he passes you on the bottom step, he swipes the iPod from your back pocket, pokes you in the ribs, and says, "Ho, I think I'll start at the top and ask you last."
You think you're doomed, until your fairy godmother appears in a flash of light. "Quick," you say, "Get me out of this!" "Sorry, sweetie," she tells you, "I bent the magic wand, and I'm also colorblind, so I can't even tell you which turban you'll be wearing." "But," she says comfortingly, "I can translate anything you like into Polish."
What should you say to the rest of the soldiers so that as many people as possible (including yourself) will go free?
I'll post the solution as a comment in a week.
Comments:
========================================================
The soldier at the top simply has to say "red" if he counts an even number of red turbans ahead of him, and "green" otherwise. The next guy in line can count the number of red turbans worn by everyone except himself and the first soldier; if his number has the same parity (that is, if the first and second soldiers' counts are both even or both odd), then he has to be wearing a green turban; if not, he has to be wearing a red turban, since his hat is the only one that could explain the disparity. If everyone shouts out their guess as the hatter proceeds down the line, then everyone in front will be able to hear what people behind them are wearing, and so can deduce their own turban color in the same manner as the 2nd soldier. So, on average 99.5 people will be saved, always including yourself.
Post a Comment
The soldier at the top simply has to say "red" if he counts an even number of red turbans ahead of him, and "green" otherwise. The next guy in line can count the number of red turbans worn by everyone except himself and the first soldier; if his number has the same parity (that is, if the first and second soldiers' counts are both even or both odd), then he has to be wearing a green turban; if not, he has to be wearing a red turban, since his hat is the only one that could explain the disparity. If everyone shouts out their guess as the hatter proceeds down the line, then everyone in front will be able to hear what people behind them are wearing, and so can deduce their own turban color in the same manner as the 2nd soldier. So, on average 99.5 people will be saved, always including yourself.
The randomness number has absolutely nothing to do with the number of visitors to this site. I promise.