Suppose you are given a set of small boxes, numbered 1 to n, identical in every

Question

Suppose you are given a set of small boxes, numbered 1 to n, identical in every respect except that
each of the first i contain a pearl whereas the remaining n - i are empty. You also have two magic
wands that can each test whether a box is empty or not in a single touch, except that a wand
disappears if you test it on an empty box. Show that, without knowing the value of i, you can
use the two wands to determine all the boxes containing pearls using at most o(n) wand touches.
Express, as a function of n, the asymptotic number of wand touches needed.

Explanation / Answer

This problem is very similar to the famous Egg dropping puzzle which can be solved using Dynamic programming.

Consider the case when we have only one wand and there are n boxes. In this case we will need n wand touches(in worst case) to find the boxes containing pearls. Explanation : Suppose all the boxes contain a pearl i.e, no box is empty. So we need to touch all the boxes from 1 to n to find that every box has a pearl. So it takes n attempts

Now consider the case when we have two wands and there are n boxes. Lets express this as a function f(2,n) where 2 is number of wands and n is the number of boxes. Now this problem can be divided into sub problems.

1)Suppose we have started with the last box(nth box). Here 2 cases are possible i)last box is empty ii)last box is not empty.

If case 1 is true then we have 1 wand and n-1 boxes (as 1st wand disappears as we tested on empty box) so f(2,n) becomes 1+f(1,n-1) where +1 is to count the attempt

If case 2 is true then we have 2 wands and remaining n-1 boxes will be full(as the last one is full) so f(2,n) becomes 1+f(2,0) where +1 is to count the attempt

Now we need to consider the worst case so the answer will be f(2,n) = 1 + maximum(f(1,n-1),f(2,0))

2)

Suppose we have started with the last but one box(n-1 th box). Here also 2 cases are possible i)n-1 th box is empty ii)n-1 th box is not empty.

If case 1 is true then we have 1 wand and n-2 boxes (as 1st wand disappears as we tested on empty box) so f(2,n) becomes 1+f(1,n-2) where +1 is to count the attempt

If case 2 is true then we have 2 wands and n-2 boxes before it will be full(as the last but one is full) and we need to check last box only so f(2,n) becomes 1+f(2,1) where +1 is to count the attempt

Now we need to consider the worst case so the answer will be f(2,n) = 1 + maximum(f(1,n-2),f(2,1))

3) Similarly if we start with n-2th box we get 1 + maximum(f(1,n-3),f(2,2)) and so on

So the various outputs based on the box which we check first will be

1)if we start with nth box : 1 + maximum(f(1,n-1),f(2,0))

2)if we start with n-1 th box : 1 + maximum(f(1,n-2),f(2,1))

3)if we start with n-2 th box : 1 + maximum(f(1,n-3),f(2,2))

4)if we start with n-3 th box : 1 + maximum(f(1,n-4),f(2,3))

.

.

.

.

n)if we start with 1st box : 1 + maximum(f(1,0),f(2,n-1))

So the optimum solution will be the minimum of all the above n cases

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.