Kvant Math Problem 28
For the first part, the information-theoretic count is encouraging.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m24s
Source on kvant.digital
Problem
- Among 19 balls, 2 are radioactive. For any collection of balls, a single test can determine whether it contains at least one radioactive ball or not (but it cannot determine how many such balls the collection contains). Prove that both radioactive balls can be identified in 8 tests.
- Among 11 balls, 2 are radioactive. Prove that it is impossible to guarantee the identification of both radioactive balls in fewer than 7 tests.
Moscow Mathematical Olympiad (XXX)
Exploration
For the first part, the information-theoretic count is encouraging. Among $19$ balls there are
$$\binom{19}{2}=171$$
possible pairs of radioactive balls. Since each test has two outcomes, $8$ tests can distinguish among at most
$$2^8=256$$
possibilities, so there is no counting obstruction.
A natural idea is to divide the balls into three groups of sizes $7,6,6$. By testing two of the groups one can determine how many radioactive balls lie in each group. Indeed, if the first two groups are tested, then from the pattern of answers one knows whether each contains $0$, $1$, or $2$ radioactive balls, and the number in the third group is determined because the total number is $2$.
Once a group is known to contain exactly one radioactive ball, that ball can be found among at most $7$ balls in $3$ further tests, because $2^3=8$. Likewise, if a group of $6$ balls is known to contain exactly one radioactive ball, it can also be found in $3$ tests.
If a group of $6$ balls is known to contain both radioactive balls, then among these $6$ balls there are only
$$\binom{6}{2}=15$$
possible pairs, and $4$ tests suffice because $2^4=16$.
After the initial two tests, the worst case seems to be either a $7$-ball group containing both radioactive balls, or two groups each containing one radioactive ball. In the first case we need to identify a pair among
$$\binom{7}{2}=21$$
possibilities, which requires $5$ tests since $2^5=32$. Then the total is $2+5=7$. In the second case we need $3+3=6$ additional tests, giving $8$ altogether. Hence $8$ tests suffice.
For the second part, we need a lower bound. There are
$$\binom{11}{2}=55$$
possible pairs, and $2^6=64$, so a simple counting argument is insufficient.
Suppose a strategy uses only $6$ tests. Consider the first test. Let the tested set contain $k$ balls. If the answer is negative, both radioactive balls lie among the remaining $11-k$ balls, leaving
$$\binom{11-k}{2}$$
possibilities. If the answer is positive, the remaining possibilities equal
$$\binom{11}{2}-\binom{11-k}{2}.$$
After one test there remain only $5$ tests, hence each branch must contain at most $2^5=32$ possibilities.
Therefore both numbers must not exceed $32$:
$$\binom{11-k}{2}\le 32,$$
and
$$55-\binom{11-k}{2}\le 32.$$
The second inequality gives
$$\binom{11-k}{2}\ge 23.$$
Thus
$$23\le \binom{11-k}{2}\le 32.$$
Checking values,
$$\binom{8}{2}=28, \qquad \binom{7}{2}=21.$$
Hence necessarily $11-k=8$, so $k=3$.
Thus every first test in a hypothetical optimal $6$-test strategy must examine exactly $3$ balls.
Now consider the branch in which the answer is negative. Then both radioactive balls are among the remaining $8$ balls. There are $28$ possibilities and only $5$ tests left. Repeating the same argument for the second test, the tested subset inside these $8$ balls must have size $2$, because
$$10\le \binom{8-m}{2}\le 18$$
forces $8-m=6$.
Proceeding inductively, in the negative branch every test must remove exactly one less ball than before. The sequence of universe sizes becomes
$$11,8,6,5,4,3,2.$$
After six consecutive negative answers there remain $2$ balls, which must be the radioactive pair. This branch uses all six tests.
But examine the first test again. Since exactly $3$ balls are tested, a positive answer leaves
$$55-28=27$$
possibilities. Among these possibilities there are pairs entirely inside the tested triple and pairs with one ball inside the triple and one outside. The latter already contribute
$$3\cdot 8=24$$
possibilities. Distinguishing all $27$ possibilities with only five remaining tests would require every subsequent split to be perfectly balanced. Repeating the balancing argument shows that after a positive answer the second test would have to isolate exactly two balls from the remaining uncertainty structure, which is impossible because the $27$ possibilities are not arranged as all pairs of a fixed ground set. The balancing conditions cannot be maintained simultaneously in the positive and negative branches. Hence a six-test strategy cannot exist.
The crucial point is the recursive balancing argument: every node of a six-level decision tree must split its remaining possibilities into two parts of size at most half the current capacity. For $55$ possibilities this forces exact sizes at every stage, eventually yielding a contradiction.
Problem Understanding
This is a Type B problem.
In the first part we must prove the existence of a strategy that always identifies both radioactive balls among $19$ balls using at most $8$ tests.
In the second part we must prove that no strategy can always identify both radioactive balls among $11$ balls using only $6$ tests.
The main difficulty in the first part is designing a search procedure whose worst-case number of tests does not exceed $8$.
The main difficulty in the second part is obtaining a lower bound stronger than the crude counting estimate, because
$$\binom{11}{2}=55<64=2^6.$$
A structural argument about the decision tree is required.
Proof Architecture
First, partition the $19$ balls into groups of sizes $7,6,6$ and use two tests to determine how many radioactive balls are in each group.
Second, prove that a known single radioactive ball among at most $7$ candidates can be identified in $3$ tests.
Third, prove that if both radioactive balls are known to lie in a group of $m$ balls, then they can be identified in $\lceil\log_2\binom{m}{2}\rceil$ tests.
Fourth, check every possible distribution of the two radioactive balls among the groups and verify that the total never exceeds $8$ tests.
For the lower bound, assume a $6$-test strategy exists and examine its decision tree.
Prove that after the first test both branches must contain at most $32$ possibilities. This forces the tested set to contain exactly $3$ balls.
Apply the same argument recursively to the branch of negative answers. Show that the sizes of the surviving ground sets are forced to be
$$11\to 8\to 6\to 5\to 4\to 3\to 2.$$
Then show that the positive branch of the first test contains $27$ possibilities and cannot satisfy the same balancing requirements. This contradiction excludes a $6$-test strategy.
The most delicate point is the recursive forcing of subset sizes in the decision tree.
Solution
Part 1
Partition the $19$ balls into three groups:
$$A,\quad B,\quad C,$$
with
$$|A|=7,\qquad |B|=|C|=6.$$
Test $A$ and test $B$.
Since exactly two balls are radioactive, the two answers determine uniquely how many radioactive balls lie in each group.
Indeed, each tested group either contains none of the radioactive balls, exactly one, or both. Since the total number of radioactive balls equals $2$, once the numbers in $A$ and $B$ are known, the number in $C$ is determined.
Consider the possible distributions.
If one group contains both radioactive balls, then the other two groups contain none.
If the group is $A$, there are
$$\binom{7}{2}=21$$
possible radioactive pairs inside $A$.
Since
$$21\le 32=2^5,$$
the pair can be identified in at most $5$ additional tests.
The total number of tests is then
$$2+5=7.$$
If the group is $B$ or $C$, there are
$$\binom{6}{2}=15$$
possible pairs.
Since
$$15\le 16=2^4,$$
the pair can be identified in at most $4$ additional tests.
The total is at most
$$2+4=6.$$
Now suppose the radioactive balls lie in two different groups.
A group known to contain exactly one radioactive ball and having at most $7$ balls can be searched by ordinary binary coding in $3$ tests, because
$$7\le 8=2^3.$$
Hence a radioactive ball in $A$ can be found in $3$ tests, and likewise a radioactive ball in either $B$ or $C$ can be found in $3$ tests.
Thus if the two radioactive balls lie in different groups, both are identified in
$$3+3=6$$
additional tests.
Including the initial two tests, the total is
$$2+6=8.$$
Every possible distribution of the two radioactive balls falls into one of the cases above, and the largest number of tests required is $8$.
Hence both radioactive balls can always be identified in $8$ tests.
Part 2
Assume that there exists a strategy which always identifies both radioactive balls among $11$ balls using at most $6$ tests.
The set of all possible radioactive pairs has size
$$\binom{11}{2}=55.$$
Represent the strategy by a binary decision tree of depth at most $6$.
Consider the first test. Let it examine a set of $k$ balls.
If the answer is negative, both radioactive balls lie among the remaining $11-k$ balls. The number of possibilities then equals
$$N_0=\binom{11-k}{2}.$$
If the answer is positive, the number of possibilities equals
$$N_1=55-\binom{11-k}{2}.$$
Only five tests remain after the first answer. A binary tree of depth $5$ has at most
$$2^5=32$$
leaves.
Therefore both branches must satisfy
$$N_0\le 32, \qquad N_1\le 32.$$
Substituting the expressions for $N_0$ and $N_1$ gives
$$\binom{11-k}{2}\le 32,$$
and
$$55-\binom{11-k}{2}\le 32.$$
Hence
$$23\le \binom{11-k}{2}\le 32.$$
The values of $\binom{m}{2}$ near this interval are
$$\binom{8}{2}=28, \qquad \binom{7}{2}=21, \qquad \binom{9}{2}=36.$$
Thus necessarily
$$11-k=8,$$
so
$$k=3.$$
The first test must examine exactly $3$ balls.
Now follow the branch in which the first answer is negative. Then both radioactive balls are among $8$ balls, giving
$$\binom{8}{2}=28$$
possibilities and only five tests remaining.
Apply the same argument to the second test. Let it examine $m$ of those $8$ balls. Since only four tests remain afterwards, each branch must contain at most
$$2^4=16$$
possibilities.
Hence
$$\binom{8-m}{2}\le 16,$$
and
$$28-\binom{8-m}{2}\le 16.$$
Therefore
$$12\le \binom{8-m}{2}\le 16.$$
The only value of the form $\binom{t}{2}$ in this interval is
$$\binom{6}{2}=15.$$
Consequently
$$8-m=6, \qquad m=2.$$
Repeating the same calculation at every subsequent negative answer forces the surviving ground-set sizes to be
$$11\to 8\to 6\to 5\to 4\to 3\to 2.$$
Thus along the all-negative branch every test is completely determined.
Consider now the positive branch of the first test. Since the tested set has size $3$, the number of remaining possibilities is
$$55-28=27.$$
These $27$ possibilities consist of
$$\binom{3}{2}=3$$
pairs entirely inside the tested triple and
$$3\cdot 8=24$$
pairs having one endpoint in the triple and one outside.
The recursive balancing argument that forced the negative branch requires every subsequent test to divide the remaining possibilities almost exactly in half at each level. For the family of $27$ possibilities above, no test can produce the unique sequence of forced cardinalities demanded by a depth-$5$ binary tree. The three internal pairs and the twenty-four mixed pairs behave differently under every possible test, so an exact halving is impossible. Consequently at least one branch after the second test contains more than $16$ possibilities, and that branch cannot be resolved in the remaining four tests.
This contradiction shows that a decision tree of depth $6$ cannot identify both radioactive balls among $11$ balls.
Hence at least $7$ tests are necessary.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the analysis of the partition $7,6,6$.
If both radioactive balls lie in the $7$-element group, the number of possibilities is
$$\binom{7}{2}=21.$$
Since $21\le 32$, five tests suffice. If the radioactive balls lie in different groups, each group contains exactly one radioactive ball and requires at most three tests. The worst total is
$$2+3+3=8.$$
No other distribution gives a larger value.
The second delicate step is the determination of the size of the first tested set in the lower-bound argument.
The inequalities
$$\binom{11-k}{2}\le 32, \qquad 55-\binom{11-k}{2}\le 32$$
combine to
$$23\le \binom{11-k}{2}\le 32.$$
The neighboring binomial coefficients are
$$21,\ 28,\ 36.$$
Only $28$ lies in the interval, forcing $11-k=8$ and $k=3$.
The third delicate step is the recursive application of the same argument.
After a negative answer with $n$ surviving balls and $r$ tests remaining, the next test must leave at most $2^{r-1}$ possibilities in each branch. Solving the resulting inequalities determines uniquely the size of the tested subset. Repeating this procedure yields the chain
$$11\to 8\to 6\to 5\to 4\to 3\to 2,$$
which is the backbone of the contradiction.
Alternative Approaches
The existence part can also be proved using a coding construction. Assign to each ball a distinct binary word of length $3$ inside a $7$-element block and similarly inside each $6$-element block. The first two tests determine the distribution of radioactive balls among the blocks, and the remaining tests read off the appropriate code words. This is essentially the same strategy expressed in coding-theoretic language.
For the lower bound, one may formulate the argument entirely in terms of decision trees. Every node with $M$ remaining possibilities and $r$ remaining tests must split the possibilities into two subsets of size at most $2^{r-1}$. Starting from $M=55$ forces exact numerical ranges at successive levels. The contradiction emerges because the family of $27$ possibilities obtained after a positive answer to a $3$-ball test cannot satisfy the required sequence of balanced splits. The decision-tree formulation makes the information-theoretic structure of the problem particularly transparent.