Story
In its youth, the Powerful Horrible Beast (PHB) used to delight itself in capturing people as they journeyed down the road that passed near its cave in the forest. As its legend grew, rewards were offered to slay PHB; but all the brave people who undertook this challenge were ultimately overcome by its strength and cunning. Instead, people determined the best solution was to avoid PHB at all costs, and eventaully the road that passed near its home was abandoned, with travellers opting instead to pass the long way around PHB's forest.
The lack of human prey didn't bother PHB through its middle years, as there were plenty of other animals in the forest to keep it well fed. And so the years slipped by, with days spent hunting wild game, and at night PHB would lie there by the fire, and watch the evening tire, slipping into peaceful slumber.
However, as PHB reached the later years of life, it reminisced on the days long gone, when life was full of excitement of the hunt and capturing poor travellers who were foolish enough to wander too close. So PHB decided to rekindle this lost joy, and ventured away from its home in the forest to pester villagers from the nearest town.
Unfortunately, this town happens to be where you and 99 of your friends and family live (each of whom have a slightly different height than each other and than you). On the day that PHB arrives, it is able to easily overrun your village and round everyone up in the town square. Dissapointed in how little resistence it encountered, and deciding that it couldn't possibly eat all 100 of you anyway, it decides to offer a challenge, in which the most cunning will be released:
In the game, all 100 of you will line-up facing the fountain at the center of the town square. As you will all be facing the same direction in a line, you will be able to see (the back side of) the people in front of you, so long as nobody between you and them that is taller than they are.
With everyone in a line, you must all close your eyes as a hat that is either black or white is placed on each of your heads by PHB, so you won't be able to see which color is placed on your head (nor on anybody else's head). You will then be allowed to open your eyes, and see the (colors of the) hats of some of the people in front of you -- namely, you will be able to see the hat color of anyone in front of you that is taller than everyone between you and them. For example, if your cousin Alice is shorter than your uncle Bob who is shorter than your friend Charlie, and you are lined up as: You, Bob, Alice, Charlie, then you will be able to see the hat colors of Bob and Charlie, but not Alice.
Next, the person at the back of the line will start by announcing a color "Black" or "White". If they correctly guess the color hat on their own head, they are released; otherwise, they are destined to become PHB's dinner. After this, the next person (at the end of the line) announces "Black" or "White", with the same consequences. This continues all the way to front of the line.
PHB informs you that you can discuss amongst yourselves an optimal strategy before you line up and hats are distributed. After determining your strategy, you must announce it to PHB, and it will choose to distribute hat colors in such a way as to minimize the number of captives it will release.
Succinct Riddle
- You and 99 of your friends and family, each of a slightly different height, are each quite clever but unfortunately not good warriors, and are rounded up by the Powerful Horrible Beast (PHB).
- Bored by the simplicity of your collective capture, PHB offers a Challenge of Wits that will allow some of you to be released:
- The 100 of you will line-up (in an order of your collective choosing), all facing the same direction.
- A black or white hat will be placed on each of your heads, so that you don't know the color of your own hat or the color of anyone's hat behind you.
- You (and everyone else) will be able to see some of the hat colors in front of you -- namely, you will be able to see the hat color of a person in front of you so long as that person is taller than everyone else between you and them.
- Starting at the back of the line, each person will announce "Black" or "White". If they announce the color hat they are wearing, they are released. Otherwise, they become PHB's dinner.
- Everyone can hear what the people behind them announce.
- No cheating: If anyone opens their eyes too early, or says any other word besides "Black" or "White", or attempts to communicate information to the rest of the group in any other way, then everyone becomes PHB's dinner.
- You and your friends have an opportunity to come up with a strategy beforehand that will maximize the number of you who will be released.
- You must announce your strategy to PHB, who can then choose to assign black/white hats to each person so as to minimize the number of released captives.
What strategy is guaranteed to save the most people, and what is the minimum number of people that will be saved with this strategy?
BONUS: Amongst the 100 of you, there is exactly one set of twins (who have the exact same height). Assuming you want to live, would you rather be one of the twins or not (and why)?
Hints
Observations:
- No matter the group's strategy, the person at the end of the line has no information on their own hat color; and thus the best they can hope for is a 50% chance of guessing correct.
- The optimal strategy will entail some people in back guessing "black" or "white" NOT because they are truly guessing their own hat color, but rather they are using their guess to communicate information to the person(s) in front of them.
- (Lower Bound). For example, one simple strategy that is guaranteed to save at least half (50) of the group is to pair everyone up, so that the person behind announces the hat color of the person in front of them; and the (lucky) member of the pair who is in front can correctly guess their own color.
[Note that if PHB assigns hats randomly, then this strategy is guaranteed to save half the group, but even the members of each pair who are behind have a 50-50 chance of getting lucky (if their own hat color happens to match the person in front of them). On the other hand, a malicious (and hungry) PHB will hear the strategy of the group, and place hats so that every pair has two hats of opposite color.]
- For the optimal strategy, it is important that everyone can hear *everyone* else's response from the people behind them. (However, learning the fate of each person behind you is not necessary, if we assume all 100 of you are perfect logicians.)
Answer
Succinct Answer: Everyone except the last person can be saved (and the last person will, unfortunately, not survive with 100% probability if PHB is malicious and knows your strategy; but the last person can survive with 50% probability if their hat is assigned randomly).
Explanation: First, the strategy must include lining people up by height, so that the person at the back of the line can see the hats of all 99 people in front of them (and also so that everyone in line can see the hats of everyone in front of them). It actually doesn't matter the height of the person in the back of the line, so you can draw straws as to how to assign that role (which, as noted above, is the only person who will not escape).
The key idea is to use "parity". Namely, the person at the back of the line counts the number of (say) white hats amongst the 99 people in front of them. If this number is EVEN, then the person in back will say "White". But if the number of white hats (that the person in back can see) is ODD, then the person in back will say "Black". Since everyone knows the code, everyone knows the parity (ODD vs. EVEN) of the number of hats amongst the front 99 of them (not including the person in back). Next, the 99th person in line will count the number of white hats in front of them, and see if they arrive at the same answer as the 100th person. If so, their hat must be Black. But if the parity (even vs. odd) is different than what the person behind them announced, then they know their hat must be White. The 99th person therefore knows their hat color, and announces this, enjoying their own subsequent release. Next, the 98th person knows the original parity (odd vs. even) of white hats (based on the 100th person's announcement), and also knows if the parity should be adjusted based on what the 99th person was wearing. Thus, person 98 has the exact same information as the 99th person did (i.e. they know the parity (odd vs. even) of the number of white hats that remain in amongst the 98 people in front of them (including themself)). Therefore, the 98th person can survive, and so on down the line.
BONUS ANSWER:
The optimal strategy requires lining people up by height (except for the person at the end of the line, whose height can be anything). Therefore, in terms of placing the twins in line, one of two things must happen: (i) One of the twins is assigned to be the 100th (last) person in line (and the other twin is lined-up according to their height with respect to the other 99 people); or (ii) The twins will appear side-by-side in line (but neither in back of the line). In the former (Case (i)), 99 people are still saved. But in the latter (Case (ii)), it is easy to argue that the twin in front will die (assuming a malicious/hungry PHB who will assign hats to optimize his dinner size), since nobody behind him can see their hat color (since their twin is obstructing everyone's view). Thus, Case (ii) means that only 98 people survive (everyone except the person at the back of the line and the twin closer to the front), and thus can be rejected as the optimal strategy, since Case (i) saves 99 people. Therefore, the group will opt for Case (i), which means that if you are NOT one of the twins, then you are guaranteed to be released. Meanwhile, the unfortunate twins will have to draw straws, which means they each only have a 50-50 chance of survival.
Story
TL;DR Same as the "Easier" version, except there are now N hat colors (rather than just two).
In its youth, the Powerful Horrible Beast (PHB) used to delight itself in capturing people as they journeyed down the road that passed near its cave in the forest. As its legend grew, rewards were offered to slay PHB; but all the brave people who undertook this challenge were ultimately overcome by its strength and cunning. Instead, people determined the best solution was to avoid PHB at all costs, and eventaully the road that passed near its home was abandoned, with travellers opting instead to pass the long way around PHB's forest.
The lack of human prey didn't bother PHB through its middle years, as there were plenty of other animals in the forest to keep it well fed. And so the years slipped by, with days spent hunting wild game, and at night PHB would lie there by the fire, and watch the evening tire, slipping into peaceful slumber.
However, as PHB reached the later years of life, it reminisced on the days long gone, when life was full of excitement of the hunt and capturing poor travellers who were foolish enough to wander too close. So PHB decided to rekindle this lost joy, and ventured away from its home in the forest to pester villagers from the nearest town.
Unfortunately, this town happens to be where you and 99 of your friends and family live (each of whom have a slightly different height than each other and than you). On the day that PHB arrives, it is able to easily overrun your village and round everyone up in the town square. Dissapointed in how little resistence it encountered, and deciding that it couldn't possibly eat all 100 of you anyway, it decides to offer a challenge, in which the most cunning will be released:
In the game, all 100 of you will line-up facing the fountain at the center of the town square. As you will all be facing the same direction in a line, you will be able to see (the back side of) the people in front of you, so long as nobody between you and them that is taller than they are.
With everyone in a line, you must all close your eyes as a hat that is one of N colors (e.g. "Orange") is placed on each of your heads by PHB, so you won't be able to see which color is placed on your head (nor on anybody else's head). You will then be allowed to open your eyes, and see the (colors of the) hats of some of the people in front of you -- namely, you will be able to see the hat color of anyone in front of you that is taller than everyone between you and them. For example, if your cousin Alice is shorter than your uncle Bob who is shorter than your friend Charlie, and you are lined up as: You, Bob, Alice, Charlie, then you will be able to see the hat colors of Bob and Charlie, but not Alice.
Next, the person at the back of the line will start by announcing a color, which must be one of the N colors (e.g. "Orange"). If they correctly guess the color hat on their own head, they are released; otherwise, they are destined to become PHB's dinner. After this, the next person (at the end of the line) announces a color (again, must be one of the N colors in the collection), with the same consequences. This continues all the way to front of the line.
PHB informs you that you can discuss amongst yourselves an optimal strategy before you line up and hats are distributed. After determining your strategy, you must announce it to PHB, and it will choose to distribute hat colors in such a way as to minimize the number of captives it will release.
Succinct Riddle
- You and 99 of your friends and family, each of a slightly different height, are each quite clever but unfortunately not good warriors, and are rounded up by the Powerful Horrible Beast (PHB).
- Bored by the simplicity of your collective capture, PHB offers a Challenge of Wits that will allow some of you to be released:
- The 100 of you will line-up (in an order of your collective choosing), all facing the same direction.
- PHB has a collection of hats, each with a color that is one of N known colors (e.g.: Red, Orange, Yellow, ...). For each of you, PHB will choose a hat and place it on your head, so that you don't know the color of your own hat or the color of anyone's hat behind you.
- You (and everyone else) will be able to see some of the hat colors in front of you -- namely, you will be able to see the hat color of a person in front of you so long as that person is taller than everyone else between you and them.
- Starting at the back of the line, each person will announce any one of the N colors. If they announce the color hat they are wearing, they are released. Otherwise, they become PHB's dinner.
- Everyone can hear what the people behind them announce.
- No cheating: If anyone opens their eyes too early, or says any other word besides one of the N colors, or attempts to communicate information to the rest of the group in any other way, then everyone becomes PHB's dinner.
- You and your friends have an opportunity to come up with a strategy beforehand that will maximize the number of you who will be released.
- You must announce your strategy to PHB, who can then choose to assign hat colors to each person so as to minimize the number of released captives.
What strategy is guaranteed to save the most people, and what is the minimum number of people that will be saved with this strategy?
BONUS: Amongst the 100 of you, there is exactly one set of twins (who have the exact same height). Assuming you want to live, would you rather be one of the twins or not (and why)?
Hint
Observations:
- No matter the group's strategy, the person at the end of the line has no information on their own hat color; and thus the best they can hope for is a 1/N chance of guessing correct.
- The optimal strategy will entail some people in back guessing a color, NOT because they are truly guessing their own hat color, but rather they are using their guess to communicate information to the person(s) in front of them.
- (Lower Bound). For example, one simple strategy that is guaranteed to save at least half (50) of the group is to pair everyone up, so that the person behind announces the hat color of the person in front of them; and the (lucky) member of the pair who is in front can correctly guess their own color.
[Note that if PHB assigns hats randomly, then this strategy is guaranteed to save half the group, but even the members of each pair who are behind have a 1/N chance of getting lucky (if their own hat color happens to match the person in front of them). On the other hand, a malicious (and hungry) PHB will hear the strategy of the group, and place hats so that every pair has two hats of different colors.]
- For the optimal strategy, it is important that everyone can hear *everyone* else's response from the people behind them. (However, learning the fate of each person behind you is not necessary, if we assume all 100 of you are perfect logicians.)
- The solution for general N is an extension of the N=2 solution; where we need a way to extend the notion of 'parity' (hint: modular arithetic).
Answer
Succinct Answer: Everyone except the last person can be saved (and the last person will, unfortunately, not survive with 100% probability if PHB is malicious and knows your strategy; but the last person can survive with 1/N probability if their hat is assigned randomly).
Explanation: First, the strategy must include lining people up by height, so that the person at the back of the line can see the hats of all 99 people in front of them (and also so that everyone in line can see the hats of everyone in front of them). It actually doesn't matter the height of the person in the back of the line, so you can draw straws as to how to assign that role (which, as noted above, is the only person who will not escape).
The key idea is to assign a numeric value in [0, N-1] to each color, and then use modular arithmetic (mod N). For example, the assignment could be Red = 0; Orange = 1; Yellow = 2; and so on. Then, the person at the back of the line computes the "sum" of all the hat values (mod N) of the 99 people in front of them. The sum (mod N) will necessarily be a number in [0, N-1], and therefore whatever that value is, there is exactly one color that has been assigned that value. The person in back will announce this color. Since everyone knows the code, everyone knows the sum (mod N) of the 99 hats (amongst the front 99 people, i.e. not including the person in back). Next, the 99th person in line will also perform the sum, but since they cannot see their own hat, their computed sum will be off (from the announced sum of the last person) by an amount that corresponds to the missing contribution of their own hat color. Therefore, the 99th person can compare the sum that they count to the sum that the 100th person counted, and know that the difference exactly corresponds to (the value of) their own hat color. The 99th person therefore knows their hat color, and announces this, enjoying their own subsequent release. Next, the 98th person knows the original sum based on the 100th person's announcement, and also knows the color of the 99th person's hat (because they announced it). So the 98th person can compute the sum of the 97 hats in front of them, then compare this to the sum of the 100th person minus the value of the 99th person, and arrive at the value (color) of their own hat. Therefore, the 98th person can survive, and so on down the line.
BONUS ANSWER:
The optimal strategy requires lining people up by height (except for the person at the end of the line, whose height can be anything). Therefore, in terms of placing the twins in line, one of two things must happen: (i) One of the twins is assigned to be the 100th (last) person in line (and the other twin is lined-up according to their height with respect to the other 99 people); or (ii) The twins will appear side-by-side in line (but neither in back of the line). In the former (Case (i)), 99 people are still saved. But in the latter (Case (ii)), it is easy to argue that the twin in front will die (assuming a malicious/hungry PHB who will assign hats to optimize his dinner size), since nobody behind him can see their hat color (since their twin is obstructing everyone's view). Thus, Case (ii) means that only 98 people survive (everyone except the person at the back of the line and the twin closer to the front), and thus can be rejected as the optimal strategy, since Case (i) saves 99 people. Therefore, the group will opt for Case (i), which means that if you are NOT one of the twins, then you are guaranteed to be released. Meanwhile, the unfortunate twins will have to draw straws, which means they each only have a 50-50 chance of survival.
