There are 2004 boxes on the table, each containing one ball. It is known that some of the balls are white, and their quantity 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 any two boxes containing white balls?

#
We will number the boxes (and the balls in them) from 1 to 2004 and denote the question by a pair of box numbers. We will call non-white balls black.

We will show that in 4005 questions, we can find two white balls.

We will ask the questions (1,2), (1,3), (1,2004), (2,3), (2,4), (2,2004).

If all answers are positive, then the first and second balls are white (let's say, for example, the first one is black; then there is at least one more black ball, which together with the first one forms a black pair).

If, however, at least one answer is negative (for example, on a question including the first ball), then the first ball is black; then the white ones are exactly those balls, for which (in a pair with the black first one) the answer was positive, and in this case, we will even find all the white ones, of which there are at least two.

Suppose there is an algorithm that allows us to find two white balls with fewer questions. We will answer all questions positively.

Then, at most after 4004 questions, the player will be able to point to some (for definiteness, the first and second) boxes and claim that the balls in them are white. In this case, one of the questions of the form (1, n) or (2, n) (say, the question (1, k)) will not be asked, because there are 4005 such questions. Now, let's put black balls in the 1st and k-th boxes, and white balls in all the others. Then all our answers will be correct, and the first ball indicated by the player will turn out to be black. Contradiction.

## [Polygons and polyhedra with vertices on lattice points] Problem 109939 Topics: $\frac{\text { Convex hull and supporting lines (planes). }}{\underline{\text { Induction in geometry }}}$

![](https://cdn.mathpix.com/cropped/2024_05_06_98b9f094130a137f64e2g-47.jpg?height=46&width=295&top_left_y=403&top_left_x=1)

A polygon with sides along the edges of the cells was cut out from an infinite chessboard. A segment of the perimeter of the polygon is called black if the cell adjacent to it from inside the polygon is black, and white if the cell is white. Let $A$ be the number of black segments on the perimeter, $B$ be the number of white segments, and let the polygon consist of $a$ black and $b$ white cells. Prove that $A-B=4(a-b)$.

## Solution

We will count the sides of all cells forming the polygon as follows: from the number of sides of black cells, we subtract the number of sides of white cells. This value is equal to $4(a-b)$, since each cell has four sides, while each segment inside the polygon was counted once with a + sign and once with a - sign. Therefore, the obtained value is equal to the sum of the perimeter segments with the corresponding signs: + for black and - for white, from which we get the required equality. The problem can be solved by induction, proving the inductive step by removing one boundary cell from the polygon. In this case, the polygon may break into several parts, and it is more convenient to prove the formula not for one polygon but for a collection. The number of variants for the location of the removed cell can be reduced to two:

,

(with three sides extending to the perimeter, and with two).

Submit a comment