Problem A. 387. (December 2005)
A. 387. We have n marbles that look all alike, but we know that one of them is radioactive. We want to find that marble. We also have a detector that can determine whether any chosen subset of the marbles contains the radioactive marble or not. We want to choose a measurement strategy for which the expected number of measurements is a minimum. Find that smallest expected value possible.
(5 pont)
Deadline expired on 16 January 2006.
Solution 1. Denote by a_{n} the expected value of measures for an optimal strategy. We show that if 2^{k}n2^{k+1} then
Introduce also b_{n}=na_{n}é the statement is
b_{n}=kn+2(n2^{k}).
Apply induction. Trivially a_{1}=0 and a_{2}=1. Now let n2 and assume that the statement is true for all smaller indices.
Let the number of the measured marbles in the first measuremebt be x. We have the probability is x/n that the radioactive one is among those x marbles and we expect another a_{x} measurements. Therefore, the expected number of measurements will be
and
 (1) 
It is easy to check that for all m<n1 we have b_{m+1}b_{m}=[log_{2}m]+2 which is increasing. Therefore, sequence b_{1},...,b_{n1} is convex and we obtain the minimum in (1) when x=[n/2]. (The minimum is not necessarily unique.) Then x,nx[2^{k1},2^{k}] and
b_{n}=n+b_{x}+b_{nx}=n+((k1)x+2(x2^{k1}))+((k1)(nx)+2(nx2^{k1}))=kn+2(n2^{k}).
Solution 2. Encode the strategy by a binary graph. Each state of the procedure is represented by a vertex. Assing the lists of suspicious marbles to the vertices. If there are more than one suspicious marbles at a vertex then the vertex has two children. The leaves of the tree are those vertices where there are single marbles; they represent the possible ends of the strategy. Figure 1 shows the tree for the strategy when the marbles are measured one by one.
Figure 1
On the other hand, each binary tree with n leaves represent a strategy. To reproduce the strategy, first write the numbers 1,2,...,n to the leaves then write the union of the children to each vertex (Figure 2).
Figure 2
The expected number of measurements is the average depth of the leaves. Denote the minimum and maximum of those depths by a and b. If b>a+1 then the sum of depths can be decreased (Figure 3). So an optimal strategy uses at most two consecutive depths.
Figure 3
Let the two depths be k and k+1 and the number of leaves at depth (k+1) be x. Then n=2^{k}+x and 2^{k}n2^{k+1}. The average depth is
Statistics:
