Maths Olympiad Prep

Library / /271 of 520

Geometry Difficulty 5.3 AIME, harder Find the answer

Four, (15 points) On a plane, nn points are called a "standard nn-point set" if among any three of these points, there are always two points whose distance is no more than 1. To ensure that a circular paper with a radius of 1 can cover at least 25 points of any standard nn-point set, find the minimum value of nn.

A number or a short expression. Spacing and $ signs are ignored.

Solution

First, prove: nmin >48n_{\text {min }}>48.
Draw a line segment ABAB of length 5 on the plane, and construct two circles with radii of 0.5 centered at AA and BB, respectively. Take 24 points in each circle. Then there are 48 points on the plane that satisfy the problem's condition (any three points must have at least two points with a distance no greater than 1).

Obviously, it is impossible to construct a circle with a radius of 1 that contains 25 of the selected points.
Therefore, nmin >48n_{\text {min }}>48.
Next, prove: nmin =49n_{\text {min }}=49.
If n=49n=49, let AA be one of the points. Construct a circle A\odot A with a radius of 1. If all the points are within A\odot A, then the condition of the problem is satisfied.

Otherwise, there is at least one point BB not in A\odot A. Construct another circle B\odot B with a radius of 1. Then the distance between points AA and BB is greater than 1 (as shown in Figure 4).

Thus, for the remaining 47 points, each point PP forms a triplet with AA and BB, and it must be true that PA1PA \leqslant 1 or PB1PB \leqslant 1, meaning point PP is either in A\odot A or in B\odot B.

According to the pigeonhole principle, one of the circles must contain at least 24 of these 47 points (let's assume it is A\odot A). Adding the center point AA, there are at least 25 points in the circle A\odot A with a radius of 1 (inside or on the circumference).
Therefore, the minimum value of nn is 49.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.