Nerding out on the poisoned wine puzzle

Are you familiar with the puzzle of a King having 100 bottles of wine of which one is poisoned?

It goes something like this: A king has 100 bottles of wine, and one of them contains poison. The poison is so potent that even a single drop will kill. The king has 10 prisoners, and he wants to figure out which bottle contains the poison. How can he use the prisoners to identify the poisoned bottle in the most efficient way possible?

The thing is that this is very subjective depending on what efficiency means. Let’s say he wants to do it by killing least number of prisoners, then the best way is to line up 100 bottles and one person keeps tasting until he finds the poisoned bottle.

But if let’s say the King wants it as fast as possible, a distribution of the workload might help. Let’s say we divide the total number of bottles by the total number of available prisoners. So in this case, with 100 bottles and 10 prisoners, we get 10 bottles per prisoner. Now each prisoner starts a linear search (i.e. try each bottle one by one from the assigned subset until the poisoned bottle is found)

Also, since there is only one poisoned bottle, then no matter how you distribute the work load, only one prisoner will die because the whole exercise stops as soon as the poisoned bottle is found.

There’s one more possible approach that might balance both criteria, which is to use a binary search like approach.

The expectation is that the linear search method would take a long time. Distributing the workload could speed up things a bit, but can we make it faster? Especially if say we need to check, not 100 but 1000 bottles?

Let’s stick with 100 bottles for now.

Say we first divide the 100 bottles into tow groups of 50 each. Next from each group of 50, we create 2 groups of 25. So now we have 4 groups of 25 each. Since we can’t divide 25 further cleanly by 2, let’s make it 8 groups of 12 each and then add the remaining 4 bottles each to groups 1, 2, 3 and 4.

Let’s recap: when we originally distributed the load (i.e 100 bottles between 10 prisoners) each prisoner had a set of 10 bottles. Let’s say that the last bottle of prisoner number 3 was the poisoned bottle, and each tasting took one minute, the entire drill would last at most 10 minutes.

But if we divide the load (i.e 100 bottles) by recursive division by 2, we get 4 groups of 12 and 4 groups of 13. So now, if the poisoned bottle is the last bottle of prisoner number 3 (bad luck, prisoner number 3!) then at worst, it’d take 13 seconds (since prisoner 3 has 13 bottles to check)

So for 100 bottles, parallelised linear search is faster? Will it still remain faster if we were checking for say 1000 wine bottles or even higher?

One way to compare the two approaches is to think about how we can calculate the worst case time for both approaches (parallelised linear search and binary search) and compare them in general.

For parallel linear search, if we have N bottles, and P prisoners, each group would be $\frac{N}{P}$

Similarly, for the binary search approach, since we’re dividing by 2 each time, so …

To understand this can we write a simple C++ program? Let’s say we have a N * N vector of zeros with only one entry as 1 (representing the poisoned bottle).

We have two main approaches to find the bottle, parallelised linear search, and modified binary search. Each time we do one lookup in the vector, which is like opening the bottle, we add 1 to the clock. Can we use such a setup to test which is the faster method as N or P or both scale?