The Prisoner Hat Problem
Ten prisoners are put to a test. If they pass, they’ll be freed. They’ll be placed in a single-file line in size order, each seeing only those ahead. Each person will wear a randomly assigned black or white hat and won’t know the total numbers of each color. They’re only allowed to say “black” or “white.” Starting from the back, each person must guess their hat’s color. If at least nine guess correctly, they’ll all be spared. What is the best strategy to make it work?
Solution. The key to solving this problem is to use the words “black” or “white” to communicate coded information. The person at the back of the line, who can see everyone else’s hats, will use their guess to indicate whether they see an odd or even number of black hats.
Here’s the strategy. The person at the back of the line will say “black” if they see an odd number of black hats and “white” if they see an even number. This word serves as code for the rest of the line. The next person in line will count the number of black hats they see. If the count matches the parity (odd or even) indicated by the first person’s word, they know their hat is white. If it doesn’t match, they know their hat is black.
Each subsequent person uses the parity of the hats they see in front of them, combined with the information from the previous guesses, to deduce the color of their own hat. If the parity they expect based on previous guesses matches what they see, they can determine their hat color correctly.
This strategy works for any arrangement of hats. The first person has a 50% chance of guessing their own hat color correctly, but their guess provides critical information for everyone else to guess with 100% accuracy.
The Pirate Gold Problem
Five pirates have 100 gold coins and must decide how to distribute them. The pirates are ranked by seniority, A to E. The most senior pirate proposes a distribution, and all pirates vote on it. If the majority (including the proposer) agree, the coins are distributed accordingly. If not, the proposer is thrown overboard and the next most senior pirate makes a new proposal. What distribution will Pirate A propose to maximize his share while ensuring he survives?
Solution. To solve this, the pirates must consider their strategies and survival at each stage. Pirate A needs to ensure that he gets the majority of votes, which means at least three out of five (including his own). Pirates are logical and will act in their own best interest. We solve this by working backward.
If only Pirate E remains, he takes all 100 coins since there’s no one to oppose him. If Pirates D and E remain, Pirate D proposes to take all 100 coins. Pirate E can’t do better by rejecting (he’d be alone with nobody to oppose D), so he accepts.
If Pirates C, D, and E remain, Pirate C needs one more vote besides his own. He offers Pirate E one coin and takes 99 for himself. Pirate E will accept because one coin beats the nothing he’d get under D’s proposal.
If Pirates B, C, D, and E remain, Pirate B needs two more votes. He offers Pirate D one coin and Pirate E one coin, keeping 98 for himself. Pirates D and E accept because they get more than what C’s proposal would give them.
If all five pirates are present, Pirate A needs two more votes. He offers Pirate C one coin (since C gets nothing under B’s proposal) and Pirate E one coin. Pirates B and D get nothing. Pirate A keeps 98 coins. This distribution ensures Pirate A’s survival and maximizes his share of the gold.
The 1,000 Wine Bottles
A king has 1,000 wine bottles, one of which is poisoned. The poison is tasteless, odorless, and kills exactly 24 hours after ingestion. You have 10 prisoners and 24 hours to identify the poisoned bottle. How can you find it using the prisoners?
Solution. Use a binary approach for efficient testing. Label each bottle from 1 to 1,000 and convert these numbers into binary. Assign each prisoner a binary digit position from 1 to 10. Each prisoner will drink from bottles that have a 1 in their assigned digit position.
To understand how this works, consider a simplified example with just two prisoners, A and B, and four bottles. Bottle 0 (binary 00): neither prisoner drinks. Bottle 1 (binary 01): only Prisoner B drinks. Bottle 2 (binary 10): only Prisoner A drinks. Bottle 3 (binary 11): both Prisoners A and B drink. If the poison is in Bottle 0, no one dies. If it’s in Bottle 1, only Prisoner B dies. If Bottle 2, only Prisoner A. If Bottle 3, both die.
With this strategy and 10 prisoners, you can test up to 2¹⁰ = 1,024 bottles, efficiently identifying the poisoned bottle in one round of testing. For each bottle, have the prisoners whose positions match a 1 in the bottle’s binary label drink from it. After 24 hours, check which prisoners have died. Their corresponding bit positions give the binary representation of the poisoned bottle’s number.
The Bridge and Torch Problem
Four people need to cross a bridge at night. They have only one torch, and the bridge is too dangerous to cross without it. The bridge can only hold two people at a time. The four people take different times to cross: 1 minute, 2 minutes, 7 minutes, and 10 minutes. When two people cross together, they move at the speed of the slower person. What is the shortest time for all four to cross?
Solution. The key is to minimize the total crossing time by strategically pairing people and managing the torch. Here is the optimal sequence.
Step 1: Person A (1 min) and Person B (2 min) cross together. Time: 2 minutes. Step 2: Person A returns with the torch. Time: 1 minute. Step 3: Person C (7 min) and Person D (10 min) cross together. Time: 10 minutes. Step 4: Person B returns with the torch. Time: 2 minutes. Step 5: Person A and Person B cross together again. Time: 2 minutes.
Total time: 2 + 1 + 10 + 2 + 2 = 17 minutes.
The trick is sending the two slowest people across together in Step 3 so their times overlap rather than adding up separately. If instead you paired each slow person with the fastest person, the total would be higher.
The Handshake Problem
If there are 10 people in a room and each person shakes hands with every other person exactly once, how many handshakes occur?
Solution. In a group of n people, each person shakes hands with n − 1 others. However, this counts each handshake twice (once for each participant), so the total number of unique handshakes is n(n − 1)/2.
For 10 people: 10 × 9 / 2 = 45. Thus with 10 people, there are 45 unique handshakes. This formula works for any number of people.
The Two Envelope Problem
You are given two envelopes, each containing a sum of money. One envelope has twice the amount of money as the other. You pick one envelope and see the amount inside. You are then given the option to switch to the other envelope. Should you switch?
Solution. This problem involves conditional probability and expected value. Let’s denote the amount in the envelope you picked as x. The other envelope can contain either 2x or x/2, with equal probability. Calculating the expected value if you switch: 0.5 × 2x + 0.5 × x/2 = x + x/4 = 5x/4.
Since the expected value of switching (5x/4) is greater than x, it seems you should always switch. However, this leads to a paradox, because the same logic applies after switching, implying you should always switch back, creating an infinite loop.
The resolution lies in the subtle assumptions about the probability distribution of the amounts. The calculation above implicitly assumes a probability distribution that doesn’t actually work in practice. You can’t have a uniform distribution over all possible envelope amounts, because that would require an impossible probability distribution. The apparent paradox dissolves once the prior distribution of money in the envelopes is properly specified, making the problem more complex than it initially appears.
The Josephus Problem
During the First Jewish-Roman War, a group of 41 Jewish soldiers, including the military leader Flavius Josephus, were surrounded by Roman forces. To avoid capture, they agreed to a system of sequential elimination of each other in a fixed order. While the other soldiers preferred self-elimination over surrendering, Josephus wanted to live. So he secretly devised a strategy to be the last survivor without getting his troops to turn on him. What is the best strategy to be the last one standing?
Solution. If everyone stands in a circular path and eliminates the person next to them in a clockwise direction while systematically taking turns, a predictable pattern emerges.
In the first wave of elimination, everyone standing in an even-numbered spot will pass away. For example, with eight soldiers: 1 k*lls 2, 3 k*lls 4, 5 k*lls 6, 7 k*lls 8 in wave one, leaving 1, 3, 5, and 7. If the total number of soldiers n is a power of two (n = 2ᵃ, such as 4, 8, 16, etc.), the winning position will always be 1. Whoever starts the k*lling wins.
For numbers that aren’t a power of two, we use the formula. If n = 2ᵃ + L (where 2ᵃ is the largest power of two less than or equal to n, and L is the remainder), then the winning position W(n) = 2L + 1, where L < 2ᵃ.
For example, take 13 soldiers: 13 = 8 + 5, so L = 5. Doing five turns of elimination (1 k*lls 2, 3 k*lls 4, 5 k*lls 6, 7 k*lls 8, 9 k*lls 10) leaves us at position 11, with soldiers 11, 12, 13, 1, 3, 5, 7, and 9 alive. That’s 8 remaining, a power of two, and whoever goes next wins. That’s soldier 11. Working it through: 11 k*lls 12, 13 k*lls 1, 3 k*lls 5, 7 k*lls 9, then 11 k*lls 13, 3 k*lls 7, and 11 k*ls 3. Winner: 11. And indeed, 2(5) + 1 = 11.
In Josephus’s scenario with 41 people: 41 = 32 + 9, so L = 9, and the winning seat is 2(9) + 1 = 19.
There’s also a neat shortcut. Write the number of soldiers in binary (41 = 101001₂), then take the leading digit and move it to the end (010011₂), and convert back to decimal: 19. To ensure survival, Josephus put himself in the 19th position to be the last man standing and surrendered to the Roman soldiers.
Further Reading
- The Josephus Problem on MathWorld
- The Pirate Game on Wikipedia
- The Two Envelope Problem at Stanford Encyclopedia of Philosophy
- Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik (covers the Josephus problem in depth)
Leave a Reply