A king has 100 barrels of wine, but one of them is poisoned. The poison only shows symptoms after 1 day, and he needs the wine soon after that.
Not wanting to take the risk, he decides to have prisoners test the wine. How many testers does he need to identify the poisoned barrel in just one round of testing?
Try solving it yourself, or read on for the solution!
Initial Steps
The intuitive answer might be 100 testers, or perhaps 99, assuming that if no one shows symptoms, the final barrel would be the poisoned one. But in reality, we can manage with far fewer testers.
Let’s start small to see how this might work by looking at a simplified example with just three testers:
| Barrel | Tester 1 | Tester 2 | Tester 3 |
|---|---|---|---|
| B1 | x | ||
| B2 | x | ||
| B3 | x |
In this setup, each tester only drinks from a single barrel. But the table demonstrates that there is clearly room for more tests to be made! What if we allow testers to combine efforts by tasting from multiple barrels?
| Barrel | Tester 1 | Tester 2 | Tester 3 |
|---|---|---|---|
| B1 | x | ||
| B2 | x | ||
| B3 | x | ||
| B4 | x | x | |
| B5 | x | x |
With this setup, we can now identify barrels based on unique combinations of testers who show symptoms. For example, if only Tester 1 shows symptoms, it’s Barrel 1; if both Testers 1 and 2 show symptoms, then it’s Barrel 4, and so on.
Binary Encoding
For each barrel, each tester either drinks from it or doesn’t. This creates two possible states per tester, which we can encode in binary.
Let’s rewrite our previous table using binary (1 for drinking, 0 for not drinking):
| Barrel | Tester 1 | Tester 2 | Tester 3 |
|---|---|---|---|
| B1 | 1 | 0 | 0 |
| B2 | 0 | 1 | 0 |
| B3 | 0 | 0 | 1 |
| B4 | 1 | 1 | 0 |
| B5 | 1 | 0 | 1 |
Now, if we reorder the table by binary counting and complete it, we get:
| Barrel | Tester 1 | Tester 2 | Tester 3 |
|---|---|---|---|
| - | 0 | 0 | 0 |
| B1 | 0 | 0 | 1 |
| B2 | 0 | 1 | 0 |
| B3 | 0 | 1 | 1 |
| B4 | 1 | 0 | 0 |
| B5 | 1 | 0 | 1 |
| B6 | 1 | 1 | 0 |
| B7 | 1 | 1 | 1 |
This table is now simply a mapping between decimal and binary! Each bit represents a tester, and each unique combination tells us which barrel they drank from.
How Many Testers Are Needed for 100 Barrels?
Each additional tester (binary digit) doubles the number of barrels we can cover:
- With 3 testers, we cover "23=8" barrels.
- Adding one tester at a time gives us 2𝑛 possibilities, where
𝑛is the number of testers.
To cover all 100 barrels, we need "27=128" combinations — so 7 testers are enough.
Alternatively, we could calculate it in two ways:
- Since our table above is now simply a mapping between decimal and binary, convert the number 100 to binary (1100100), count the bits (7), and we get our answer.
- Logarithm: Use "log2(100)≈6.64" and round up to 7.
So, with just 7 testers, we can identify the poisoned barrel in a single round.
What's even more interesting is how efficiently this solution scales. For example, if you had 1,000 barrels instead of 100, you would only need 10 testers, and for 1,000,000 barrels, just 20 testers will be sufficient!
And if you still insist on getting 100 testers on board, well now you can test a whopping 1,267,650,600,228,229,401,496,703,205,376 barrels!
Top comments (1)
Great write-up.
Of course, it might be worth noting that with 8 testers and 8 barrels only one prisoner is poisoned. Whereas with just 3 testers, you run the risk of poisoning all of them. :)