'Within' 15 minutes means the pig can die any time within that time.
in 60 min timeframe, we have 4 slots of 15 mins each. Now that means there are 5 states at the end of 60 mins as follows:
- Pig dies within 00 - 15 mins
- Pig dies within 15 - 30 mins
- Pig dies within 30 - 45 mins
- Pig dies within 45 - 60 mins
- Pig is Alive
Now, each pig can be used to detect 5 events.
let's number pigs as 0, 1, 2, .... x-1
Assume, that we need to create some kind of unique encoding for 1000 buckets using 5 digits (i.e. base 5) since we have 5 states. We can use base 5 number system like 00, 01, 02, 03, 04, 10, 11, 12, 13, 14, 20 , 21 ...
Now, at time t = 0, make pig0 drink the buckets with 0 as the last digit, pig1 drink second last digit as 0 and so on... take the note about the result at the end
at time t = 15 min, make pig0 drink the buckets with 1 as the last digit, pig1 drink second last digit as 1 and so on... take the note about the result at the end. Remember if any pig died in the first case, we know the ping number is nothing but the encoded digit of the bucket which further reduces our scope and helps in convergence.
Hence, going by this logic, we should be able to find our the number of pigsfor 1000 buckets and 15/60 min time. We have 5 states for each pug experiment and hence need ceil(log(1000)/log(5)) pigs
in a generic case, the ans would be as follows:
numOfStates = minutesToTest / minutesToDie + 1
Assume we have 125 buckets.
We will number them from 000 to 444.
Assume 123 numbered bucket has poison (123)base5 = 38
how will we detect the above bucket.
For this case, pig2 will die within 15-30 mins since it would have had poison from 123. That gives us the 3rd digit from last is 1.
pig1 will die within 30-45 mins since it would have had poison from 123. That gives us the 2nd digit from last is 2.
pig3 will die within 45-60 mins since it would have had poison from 123. That gives us the last digit is 3.
Hence we know the bucket!