Maths Olympiad Prep

Library / /19 of 86

Geometry Difficulty 6.0 National Olympiad Prove it United States

Problem:
Prove that there exists a set SS of 310003^{1000} points in the plane such that for each point PP in SS, there are at least 2000 points in SS whose distance to PP is exactly 1 inch.

Solution

Solution:
Let us define a kk-configuration to be a finite set of points on the plane such that for each point PP in the set, there are at least kk points of the set 1 inch from PP. Then the problem is asking us to show that there is a 2000-configuration with 310003^{1000} points.

Notice that an equilateral triangle is a 2-configuration which has 3 points. Now, let AA be a kk-configuration with NN points, and let TT be an equilateral triangle with unit side length. We shall show that it is possible to "add" AA and TT to create a (k+2)(k+2)-configuration with 3N3N points:

Define the set SS by
S={a+taA, tT} S = \{ a + t \mid a \in A,\ t \in T \}
where we treat the points as vectors. In other words, SS consists of the vector sums of every point in AA with every point in TT. Since AA has NN points, and TT has 3 points, the set SS will have 3N3N points as long as all of these sums are distinct. For the time being, let us assume that the sums are all distinct.

Now we will show that SS is a (k+2)(k+2)-configuration. Consider any point a+ta + t in SS, where aAa \in A and tTt \in T. Since AA is a kk-configuration, there are kk points a1,,akAa_1, \ldots, a_k \in A that are 1 inch away from aa. Likewise, there are two points t1,t2t_1, t_2 in TT which are each 1 inch away from tt. It is easy to check that the k+2k+2 points
t+a1,,t+ak; a+t1,a+t2 t + a_1, \ldots, t + a_k ;\ a + t_1, a + t_2
are each 1 inch away from a+ta + t. Thus SS is a (k+2)(k+2)-configuration.

But how do we ensure that all 3N3N sums are distinct? The sums fail to be distinct only if there are pairs a,aAa, a' \in A and t,tTt, t' \in T with a+t=a+ta + t = a' + t', which in turn is true if and only if aa=tta - a' = t' - t. To ensure that this does not happen, it suffices to rotate one of the two sets (say, TT) so that the slopes of all of the lines connecting all pairs of points in TT do not equal any of the slopes in AA (easy to do since there are finitely many points).

For example, in the following diagram, we attempt to "add" two equilateral triangles (the second triangle is outlined), but because of equal slopes, the sum contains only 6 points.
Figure 1

On the other hand, if we rotate the second triangle (in this case, by 30 degrees), the resulting sum contains 9 points (and you should check that this new set is indeed a 4-configuration).
Figure 2

Clearly, we can continue this summation process, adding additional copies of equilateral triangles (making sure to rotate so that no slopes are equal). For each triangle that we add, the new set will have three times as many points. Thus if we add 1000 triangles, we will get a set with 310003^{1000} points which is a 2+2++2=20002 + 2 + \cdots + 2 = 2000-configuration.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.