The King's Party
Part 1
You are a king hosting a grand party. To accommodate your guests, you order 1000 barrels of your most expensive wine. A day before your party, your trusted advisor tells you exactly one of the barrels has been spiked with Gluvenom: a deadly poison that kills its victims in exactly 24 hours no matter the dosage.
Luckily, you have a dungeon full of prisoners. There is just enough time for a wine tasting trial where you can assign a set of barrel(s) to your prisoners and have them taste a drop of each. If any prisoners drink from the poisoned barrel, they will die before the party with enough time for you to identify and destroy the toxic barrel.
What is the minimum number of prisoners you need for the trial to deduce which barrel was poisoned?
Clarifications
Can you have 1000 prisoners each taste a different barrel?
Yes. If you label the barrels 1 to 1000 and assign a prisoner to each barrel, whichever prisoner dies will indicate which barrel number is poisonous. However there are ways to solve this using a smaller number of prisoners.
Can you use the order/timing of when the prisoners taste the wine in the solution?
No. All prisoners must taste their assigned barrels simultaneously, and all results (deaths) occur at the same time. You cannot use the order or timing of events to solve the problem.
Part 2
After the smashing success of your first party, you decide to host a second celebration with another 1000 barrels of wine. Your advisor warns you that once again, exactly one barrel has been poisoned with Gluvenom.
However, this time you have 48 hours to identify the toxic barrel (instead of 24 hours like in Part 1).
Since the poison takes exactly 24 hours to take effect, you can now conduct two sequential wine trials:
- First trial (Day 1): Assign each prisoner a specific set of barrels to taste from, just like in Part 1
- Second trial (Day 2): After 24 hours, any prisoners who survived the first trial can taste from a different set of barrels
What is the minimum number of prisoners you need to find the poisoned barrel?
Part 3
You decide to have a final party with your last 1000 barrels of wine. Predictably, you find exactly one barrel has been poisoned with Gluvenom yet again. However, this time you only have 20 prisoners remaining in your dungeon after the events of your first two parties. Feeling guilty, you want to ensure as many prisoners survive the wine trial as possible.
After a single trial, what is the maximum number of prisoners you can guarantee the survival of while still finding the poisoned barrel?
How about with only 10 prisoners left?
Solution
Send me an email at [email protected]!