$\left[\begin{array}{l}{[\text { Theory of algorithms (other). }} \\ {[\quad \text { Estimation + example }}\end{array}\right]$

There are 2004 boxes on the table, each containing one ball. It is known that some of the balls are white, and their number is even. You are allowed to point to any two boxes and ask if there is at least one white ball in them. What is the minimum number of questions needed to guarantee identifying a box that contains a white ball?
We will number the boxes (and thus the balls in them) from 1 to 2004 and denote a question by a pair of box numbers. We will call non-white balls black.

We will show that a white ball can be found in 2003 questions.

We will ask the questions $(1,2),(1,3),(1,2004)$. If all answers are positive, then the first ball is white (otherwise, there is at least one more black ball, and the first one together with it would form a black pair). If, however, at least one answer is negative, then the first ball is black; in this case, the white balls are exactly those for which (in a pair with the black first one) the answer was positive, and in this case, we will find all the white ones.

Suppose there exists an algorithm that allows finding a white ball in fewer questions. We will answer all questions positively. Then, at most after 2002 questions, the player will be able to point to some (for definiteness, the first) box and claim that the ball in it is white. At this point, a question of the form $(1, n)$ (say, the question $(1,2)$) will not have been asked, because there are 2003 such questions. Let us now place black balls in the 1st and 2nd boxes, and white balls in all the others. Then all our answers will be correct, and the ball indicated by the player will turn out to be black. Contradiction.

## Answer

In 2003 questions.

Submit a comment