Given $541$ points in the interior of a circle of unit radius, show that there must be a subset of $10$ points whose diameter (the maximum distance between any pair of points) is less than $\sqrt{2}/4$.
5
-
$\begingroup$ Could you tell us 1) The origin of the problem (Olympiads of year 541 ?) 2) What you have attempted ? $\endgroup$– Jean MarieOct 5, 2016 at 12:33
-
$\begingroup$ The problem is from a sample GCHQ Aptitude test. $\endgroup$– HoggOct 5, 2016 at 12:34
-
$\begingroup$ I'm finding it very difficult, I'm not sure how to approach it. $\endgroup$– HoggOct 5, 2016 at 12:35
-
1$\begingroup$ The 1 at the end of 541 seems very peculiar, potentially hinting at Pigeonhole Principle? $\endgroup$– Benson LinOct 5, 2016 at 12:45
-
1$\begingroup$ @BensonLin It does seem to hint that if you divide the unit circle into $60$ regions, there must be $10$ points in at least one of them, yes. $\endgroup$– ArthurOct 5, 2016 at 13:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We assume the circle is centered on the origin $(0,0)$
You can draw a $8$ by $8$ grid of squares each with side length $\frac{1}{4}$. The top-left square will have the 4 coordinates $(-1,1),(-1,\frac{3}{4}),(-\frac{3}{4},1),(-\frac{3}{4},\frac{3}{4})$ and the bottom-right square will have the 4 coordinates $(1,-1),(1,-\frac{3}{4}),(\frac{3}{4},-1),(\frac{3}{4},-\frac{3}{4})$ etc.
We know that this grid will completely cover the entire circle since the diameter of the circle is equal to the side length of the entire grid (i.e. $2$). We can also rule out any points being in the 4 corner squares of the grid. This is because the distance from the closest point in each of these squares to the origin is $\sqrt{\frac{3}{4}^2 + \frac{3}{4}^2} = \sqrt{\frac{18}{16}} > 1$. Thus no point inside the circle can be in these 4 corner squares.
From here, we can use Pigeonhole Principle. Since there are only $64 - 4 = 60$ squares for the $541$ points to be in, there is at least $1$ square with at least $10$ points within the square (along the sides is fine). The maximum distance between any $2$ points in such a square is clearly the diagonal length, which is $\sqrt{\frac{1}{4}^2 + \frac{1}{4}^2} = \sqrt{\frac{2}{16}} = \frac{\sqrt 2}{4}$.
