There 1,000 buckets, one of them contains poison, the rest of them are filled with water. They all look the same. If a pig drinks that poison, it will die within 30 minutes. What is the minimum number of pigs to you need to figure out which bucket contains the poison within one hour?
[Math] Minimum number of objects required to figure out the issue
puzzlerecreational-mathematics
Related Solutions
I asked this question on MathOverflow and got a great answer there.
For $k = 2$ I can do it with ${\lceil \log_2 N \rceil + 2 \choose 2} - 1$ servants. In particular for $N = 1000$ I can do it with $65$ servants. The proof is somewhat long, so I don't want to post it until I've thought about the problem more.
I haven't been able to improve on the above result. Here's how it works. Let $n = \lceil \log_2 N \rceil$. Let me go through the algorithm for $k = 1$ so we're all on the same page. Number the wines and assign each of them the binary expansion of their number, which consists of $n$ bits. Find $n$ servants, and have servant $i$ drink all the wines whose $i^{th}$ bit is $1$. Then the set of servants that die tells you the binary expansion of the poisoned wine.
For $k = 2$ we need to find $n$ butlers, $n$ maids, and ${n \choose 2}$ cooks. The cooks will be named $(i, j)$ for some positive integers $1 \le i < j \le n$. Have butler $i$ drink all the wines whose $i^{th}$ bit is $1$, have maid $i$ drink all the wines whose $i^{th}$ bit is $0$, and have cook $(i, j)$ drink all the wines such that the sum of the $i^{th}$ bit through the $j^{th}$ bit, inclusive, mod 2, is $1$. This is how the casework breaks down for butlers and maids.
- If both butler $i$ and maid $i$ die, then one of the poisoned wines has $i^{th}$ bit $0$ and the other has $i^{th}$ bit $1$.
- If only butler $i$ dies, then both of the poisoned wines have $i^{th}$ bit $1$.
- If only maid $i$ dies, then both of the poisoned wines have $i^{th}$ bit $0$.
The second two cases are great. The problem with case 1 is that if it occurs more than once, there's still ambiguity about which wine has which bit. (The worst scenario is if all the butlers and maids die.) To fix the issue with case 1, we use the cooks.
Let $i_1 < ... < i_m$ be the set of bits where case 1 occurs. We'll say that the poisoned wine whose $(i_1)^{th}$ bit is $1$ is wine A, and the other one is wine B. Notice that the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine A mod 2 is the same as the sum of the $(i_1)^{th}$ through $(i_2)^{th}$ bits of wine B mod 2, and we can determine what this sum is by looking at whether cook $(i_1, i_2)$ died. The value of this sum determines whether the $(i_2)^{th}$ bit of wine A is 1 or 0 (and the same for wine B). Similarly, looking at whether cook $(i_j, i_{j+1})$ died tells us the remaining bits of wine A, hence of wine B.
One last comment for now. The lower bound is not best possible when $k$ is large compared to $N$; for example, when $k = N-1$ it takes $N-1$ servants. The reason is that any servant who drinks more than one wine automatically dies, hence gives you no information.
8 8 0 [0 0 0 0]
8 5 3 [0 0 0 0]
8 5 0 [3 0 0 0]
8 2 3 [3 0 0 0]
8 0 3 [3 2 0 0]
8 3 0 [3 2 0 0]
5 3 3 [3 2 0 0]
5 6 0 [3 2 0 0]
2 6 3 [3 2 0 0]
2 8 1 [3 2 0 0]
2 8 0 [3 2 1 0]
0 8 2 [3 2 1 0]
0 7 3 [3 2 1 0]
3 7 0 [3 2 1 0]
3 4 3 [3 2 1 0]
6 4 0 [3 2 1 0]
6 1 3 [3 2 1 0]
6 0 3 [3 2 1 1]
8 0 1 [3 2 1 1]
8 0 0 [4 2 1 1]
5 0 3 [4 2 1 1]
5 3 0 [4 2 1 1]
2 3 3 [4 2 1 1]
0 3 3 [4 4 1 1]
0 0 3 [4 4 4 1]
0 0 0 [4 4 4 4]
Best Answer
You can do it with $10$ pigs, based on the binary representation of a number. Mark the pigs $1, 2, ..., 10$. Given bucket number $n$, write $n$ in binary; every time the $k$th digit is $1$, have pig #$k$ drink.
Wait for pigs to die. Form the appropriate number, putting $0$'s for every living pig in the appropriate place, and $1$'s otherwise. The number formed marks the bad bucket.
Note that I'm assuming that the pigs can drink from a lot of buckets quickly, and that more than one pig can drink from a bucket.