vietdo
October 5th, 2005, 05:13 PM
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 if 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 c * sqrt(n) touches, for some fixed constant c.
Need Helps. Thank you
Pinky98
October 5th, 2005, 05:38 PM
I would disagree that it is possible.
You will need at most, (n/2 + 1) touches. I fail to see how you can do it with less.
Way to do that... touch every second box, then when you reach one which is empty, touch the one before it with the second wand. This will tell you exactly which boxes do and do not have a pearl.
And besides your question makes no sense either?? If you want to find out which boxes have a pearl, then you need to find i. So why is there the statement "Show that without knowing the value of i, you ..."
And also, what is "c"... why not just make it a hundered million billion. And then you are almost sure to find your answer in c*sqrt(n) touches??
Am I missing something?