The solution to this problem is due to log_6(1000) = 2.5... The algorithm is as such:
- Divide 1000 by 6 which is approximately 167. Take 6 pigs and make them drink from 167 buckets each. It is okay to have one overlapping buckets because then we will find the poison bucket immediately.
- Take the subarray of buckets one of the 6 pigs died from. The poison bucket must be within that subarray. Take the 5 pigs that survived and add one more, divide that subarray into 6 more equal divisions.
- Continue this pattern. You will be able to find the poison bucket with 8 pigs.
1000 -> 6 Pigs -> 167 (One dies) , 15 minutes used
166 -> 7 Pigs -> 28 (One dies) , 30 minutes used
28 -> 8 Pigs -> 5 (One dies) , 45 minutes used (No need to add another pig)
5 -> 8 Pigs -> 1 (One dies) found bucket
Abstract solution: If we are given
N time to find one poisonous bucket in
M buckets and each pig dies in
T amount of time. We know we have time for
N/T samples. We need to find the solution to this equation:
log_x(M) = N/T (find x)
The total number of pigs needed will be
x + (N/T - 1) pigs.