Problem 4. Suppose you are given a set of small boxes, numbered 1 to n, identical in every aspect except that each of the first i contains a pearl whereas the remaining n i are empty. You can 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 a box that is empty. Show that, without knowing the value of i, you can use the two wands to determine all the boxes containing pearls using at most no more than 2 n wand touches. Hint: For a suitable parameter k that you choose consider using one wand on boxes 1, k, 2k, 3k, . . .; find the value i where the empty box is among (i 1)k + 1, . . . , ik. Then use the second wand sequentially from (i 1)k + 1 to ik 1 to the empty box. The total number of touches will be at most: n/k + k. Then, let k = n (think about why this value of k; why not, e.g., let k = n 0.4 ?).