Pigeonhole Principle Proof

Question

2004 flies are inside a cube of side 1. Show that some 3 of them are within a sphere of radius 1/11.

I am not sure how to begin the proof especially since we are asked to work on a sphere rather than the given cube.

Answer 1

I would try and see if I can cover the cube with $1001$ balls of radius $1/11$. If I could do that, then if more than $2002$ flies were inside the cube, each fly would be in one of those little balls, and $3$ of them would have to be in the same ball.

Hmm. I can divide the cube into $1000$ little cubes of side $1/10$. I wonder what radius of sphere it takes to contain one of those little cubes?

The distance between opposite corners of the unit cube is $\sqrt3$. For the little cubes, the corner-to-corner distance is $\sqrt3/10$, the center-to-corner distance is $\sqrt3/20$, so each little cube is contained in a sphere of radius $\sqrt3/20$. I wonder how that compares with $1/11$?

Answer 2

Bof has the right idea - divide the cube into, say, $n<\frac{2004}{2}$ little cubes of side length $m$ each. By pigeonhole, there at least 3 flies sharing one such cube. Is the $m$ small enough such that a sphere of radius $1/11$ can contain it entirely?