Identify the Posionous Bucket with Minimal Cost

1. Problem Description
This is a Micorsoft interview question for software engineer intern from careercup. Here is the description of the original thread,
"

Just a disclaimer: I doubt you will ever get this interview question. My interviewer even started off by saying, "Hmm, well this isn't really fair, but..." So don't place too much stock in whether or not you can solve this. 

Question: You have a group of pigs and buckets of food for said pigs. There are 1,000 buckets of food, and exactly 1 of them is poisoned. Your goal is to determine, by the end of 1 hour, which bucket is poisoned. 

The poison takes 30 minutes to kill a pig, and you'd like to kill as few pigs as possible. The number of pigs you can test is limitless, and you can assign a number to each bucket and each pig so that you know exactly which pig ate from which bucket(s). You determine which buckets to feed to which pigs, but you have no timer and no way to guesstimate the time. What is the minimum number of pigs you need to use to solve the problem?

- oxymoronic2012 November 02, 2016 in United States for Bing | Report Duplicate | Flag 
".

2. Analysis
I don't think there is a definite answer to this question. Because in the worst case it needs 1000 pigs to find out the poisonous bucket and the best case is 1. Therefore instead of looking of a definite answer this question is to find out the minimum of expectation of how many pigs needed to find the poisonous bucket.

Also in this problem it offers a trial because the poison takes 30 minutes to take effect and the time limit is one hour. Hence the first 30 minutes allow us to try first and then decide what to do in the next 30 minutes. Typical relative probability problem.

In the worst case (without attempting a trial) 1000 pigs eat the food of the buckets and then in 30 minutes find the answer. Then 1000 pigs with 100% assurance. Then the cost is 1000. But in a trial case, for instance 500 pigs to try the bucket first (with the probability of 50% to spot the poisonous bucket) and then terminates if found otherwise put another 500. Then expected value is 500*0.5 + 1000*0.5 = 725.

Here is the formula: assume the first try is x, where x is within [1, 1000], then the possibility of successful is x/1000. If fail, then use another (1000-x) to test to get the answer.
    - First try x pigs with probability of x/1000
    - 1000-x pigs with probability of 100%, if the first try fail (the probability of fail as (1 - x/1000))
Then the expectation E is x*(x/1000) + 1000 * (1-x/1000).

The problem can be regarded as: Min{x*x/1000 - x + 1000}, where x is within [1, 1000].

(x*x - 1000x + 1000000)/1000 = ((x - 500)*(x-500) + 725000)/1000.
Min{((x - 500) * (x- 500) + 725000)/1000)}, where x is within [1, 1000].
Therefore x=500, it has the minimum expectation as 725.

3. General Case
What if the poison takes only 20, 10 5, ...... minutes to take effect. This means that we have 2, , 5, 11, ...... trials before hitting the last resort.

Let's generalize the problem. The number of total bucket as N and the number of trial as M. In the above case N = 1000 and M = 2 (1 hour/30minutes). Then we represent the above question as,
     F(N, M) as F(1000, 2).

Let's check the case of take 20 minutes for the poison to take effect and one hour allowed. Then N = 1000 and M = 3, as F(1000, 3)
Assume the first attempt x within [1, 1000],
     - Probability to successful: x/1000
     - Expected value: x * x/1000
If the first trial fail, then the follow has possibility of (1 - x/1000). Therefor the expectation can be written as:
    E{F(1000, 3)} = E{x * x/1000 + F(1000 - x, 2) * (1 - x/1000)}, where x is within [1, 1000]
Here F(1000-x, 2) can solved as in Section 2.

Using the induction theory, for F(N, M) case,
    E{F(N, M)} = E{x * x/N + F(N - x, M - 1) * (1 - x/N)}, where x is within [1, N].
The special case:
    Min{E{F(N, 1)}} = N
    Min{E{F(N, 2)}} = 3*N/4