Track / Stage 6 / 51 of 400 #1531 of 2444

Problem 1531

National Olympiad, first round

Combinatorics Difficulty 6.0 Prove it Baltic Way competition problems · Baltic Way

Albert, Ben and Carla are looking at the dust in the air, and Ben says that if there are $1000$ dust grains in a $10\text{cm} \times 10\text{cm} \times 10\text{cm}$ box, then no matter how they are situated, he can choose a point such that there are at least $10$ dust grains in a distance of at most $2$ cm from the point, but Albert does not believe him. Carla says that no matter how the dust grains are situated, she can choose a point such that there are at least $10$ dust grains in a distance of at most $2$ cm and at least $1$ cm from the point, but Ben does not believe her. Determine who is right, Albert, Ben or Carla.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Carla is right. Take each dust grain and colour all points in a distance of at most $2$ cm and at least $1$ cm from the grain. Then we have coloured a volume of $1000 \cdot \frac{4}{3} \cdot \pi \cdot (2^3 - 1^3) = \frac{28000}{3}\pi\text{cm}^3 > 28000\text{cm}^3$ counted with multiplicity. All the coloured points are contained in a $14\text{cm} \times 14\text{cm} \times 14\text{cm}$ box of volume $14^3 = 2744\text{cm}^3$ . Hence there is a point that is coloured at least $10$ times, and then there are at least $10$ points in a distance of at most $2$ cm and at least $1$ cm from this point.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.