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 | |
| B6 | x | x | |
| B7 | x | x | x |
| B8 |
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 |
| B6 | 0 | 1 | 1 |
| B7 | 1 | 1 | 1 |
| B8 | 0 | 0 | 0 |
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.
- By doubling the barrels a few times "26=64" almost gets us there.
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.
Scaling Up
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 (one quintillion) barrels!
Top comments (4)
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. :)
If you're a king, poisoning prisoners is probably not considered a "risk," per se.
Excellent illustration of the technique
just wow ♥️.