1971 IMO Problems/Problem 5
Contents
[hide]Problem
Prove that for every natural number , there exists a finite set of points in a plane with the following property: For every point in , there are exactly points in which are at unit distance from .
Solution 1
I shall prove a more general statement about the unit distance graph(, adjacency iff the Euclidean distance between the points is ) and this will follow as a consequence. if occur as unit distance graphs, then so does ( here is described as or ). this is seen by describing the vertices by complex numbers. suppose there is an embedding of by the complex numbers and for by the numbers . we claim that for some choice of , will do the job(a suitable rotation). what we need is that iff either or . clearly if the condition holds then the adjacency is satisfied. suppose and that the corresponding complex numbers are at a distance from one another. Then this gives a quadratic in and hence can take only finitely many values here.ruling this out for each such set of hence rules out finitely many values of and therefore a suitable choice exists. for the given problem we need a unit distance graph which is regular of degree for any given . since we can form the graph , we can form (the unit cube) and that solves the problem.
This solution was posted and copyrighted by seshadri. The original thread for this problem can be found here: [1]
Solution 2
Suppose has the formwhere is unknown set of distinct unit vectors in . We can build inductively, starting from the empty set and adding vectors to it, one by one. We just need to make sure that two thing are respected: 1. All vectors in are distinct; 2. Two vector sums are at unit distance from one another if and only if they differ in presence of exactly one summand (i.e. one and only one coefficient in the sum changes from to ). If these two conditions are kept, then each of points at will be at unit distance from exactly points corresponding to sums at which one and only one of coefficients differs from coefficients of this point. However, respecting these conditions is not hard because and for each new vector being added to there is at most some finite set of forbidden endpoints given by sums/differences of already determined vectors but the rest of the (infinite) unit circle is permissible.
This solution was posted and copyrighted by Bandera. The original thread for this problem can be found here: [2]
Remarks (added by pf02, January 2025)
1. On the original thread at https://artofproblemsolving.com/community/c6h60830p there is a third solution, by Pgm03B. It is simpler than the two solutions above. It has a flaw in the argument, and it is not presented in a nice way, but it is a nice idea, well worth presenting here. As a public service, I will add an edited version of it below.
2. Solutions 1 and 2 above are based on good ideas, but they are presented very poorly. If this page was a reviewed publication, and I were a reviewer, I would reject both of them saying "rewrite and resubmit".
2.1. Solution 1 suffers from undefined notation and terminology, from minor errors, and from unacceptable amount of hand waving replacing explanations of details.
2.2. Solution 2 suffers from poor explanation of details and from what seems to me to be an error (starting an inductive proof for a property of vectors from an empty set).
As a public service I will rewrite these proofs below, in what I hope is a much more presentable style.
Definitions and terminology
It will be helpful (though not necessary) to imagine the set of points as a graph in the plane. Specifically, the vertices of the graph are the points in , and the edges of the graph are the line segments of length joining the points. All points at distance are joined, and only the points at distance are joined.
We will call such a graph -regular iff every has exactly lines of the graph with one end at , in other words, there are exactly points in at unit distance from . Using this definition, the problem can be reformulated as "prove that for any natural number , there exists an -regular graph."
For the purposes of solution 1, it will be useful to think of the points as points in the complex plane. For the purposes of solution 2, it will be useful to think of the plane as having an origin . We will work with vectors in the plane. The points will be the end points of vectors. We will try to differentiate between vectors and their end-points, although at times, when there is no danger of confusion, we may be sloppy about it.
Solution 1, rewritten
We will give a proof by induction on . First some notation:
Given two finite sets of points in the complex plane, and given , define .
: If is -regular and is -regular, and , then we can choose so that is -regular.
: Let be the neighboring points in at distance from , and be the neighboring points in at distance from Clearly is at distance from and is at distance from . So has neighbors at distance if we choose such that for all .
But the equations are just a finite number of linear equations in , so we just have to avoid choosing giving a solution to any of these equations. Thus, with such a choice of there are definitely at least points in at distance from .
We have to show that we can choose so that there are no more than points at distance . If we had more points from at distance from , we would have for some and .
This would imply ,
or ,
or ,
or .
This becomes an equation of degree in . So as long as we choose not to equal to any of the solutions of these equations, we can be sure that none of the points in are at distance from .
This proves the proposition because we have to choose different from finite number of values.
Now the problem is very simple to prove by induction.
For , take , which is a -regular set. For the induction step, assume we have an -regular graph. Using the proposition, it follows that we can choose such that is an -regular graph, where consists of two points in the plane at distance , none of which is in .
(Just for the sake of completeness, let us mention that when we choose , it is a value in which differs from a finite set of values modulo , dependent on the points in .)
Solution 2, rewritten
Given a set of vectors in the plane, define
Let the set of end points of all .
Note that in the case for all , the sum , which yields the point (the origin) in the plane. In the notation this corresponds to . (Just as a curiosity, note that if contains vectors, then contains points. We are not going to use this fact.)
We will prove by induction on that there is a set of unit vectors with the starting point at , such that the vector sums in are all distinct, and is -regular. If , take , where is a unit vector starting at . Then consists of , and consists of the origin and the end point of , so it is clearly a -regular set.
Now assume that we have a set of unit vectors starting at , , such that the sums in the corresponding are all distinct, and is -regular. We want to show that we can find a unit vector starting at , such that if we take , then the vector sums in are all distinct, and is -regular. Note that and .
Prove that we can choose such that the sums in are all distinct. If then . So we just need to make sure that we choose such that for all . This means that has to avoid satisfying a finite number of equations. Since there are infinitely many possibilities for the unit vector , we can definitely choose it such that it is not satisfying a finite number of equations.
We will now prove that we can choose such that is -regular. First, let correspond to . Then, the same viewed as a point in has at least neighbors at unit distance, namely the neighbors it has in and the point corresponding to . It would have more neighbors at unit distance if we there would exist an (where and not at distance from ) such that the end points of and would be at distance . So, the end point of the unit vector should not be at distance from the end point of the vector , or in other words, should not be on the circle of radius centered at the end of . This circle intersects the unit circle centered at (on which the end point of is) in at most points. This gives yet another finite set of conditions should avoid satisfying.
Second, take corresponding to for a . Let be the vectors which give the points in at unit distance from the point corresponding to . Then and are vectors whose end points are at unit distance from . Again, we have to show that we can choose so that there are no more points in at distance from the end point of . There would be more points in at distance from if we had vectors (where and not at distance from ) such that the end points of and , or the end points of and were at distance . The former is already avoided by the choice of made so far, and the latter is avoided because of the induction hypothesis.
Since there are only finite number of equations the unit vector with starting point at has to avoid satisfying, it follows that we can find such that is -regular.
Solution 3
We will give a proof by induction on . For consider the graph consisting of two points at distance joined by a line segment.
Assume that we have a graph which is -regular. Let be a direction along which we make a translation of of length (that is, the distance of translation ). Denote by the translated graph, and let be the graph whose vertices are , and whose edges are those of , together with those of , and the edges obtained when we join each with the corresponding (where is the result of translating ). We will prove that we can choose the direction of translation such that is -regular.
First, let us make sure we choose such that no point in is a point of . This means that has to be different from a finite number of values, which is possible since to begin with, we have infinitely many choices for .
Let , and the translated image of . Let be the points in at distance from , and let the coresponding points in . The point has neighbors in at distance , namely , and the point has neighbors in at distance , namely . So every point in has at least neighbors at distance .
We have to show that we can choose the direction so that no point has more than -neighbors at distance . For this, we have to show that for all and the corresponding we can choose such that the distance between and is . This means that should be such that is not at the intersection of the two circles of radius centered at and . Since these two circles intersect in at most points, and we have finitely many pairs , this imposes that the direction does not equal finitely many values. This proves the induction step, and the problem.
(Note that as far as the construction goes, this solution is essentially the same as solution 1, but the formalism and the point of view are so different that I think it should be viewed as a different solution.)
This solution is based on the idea by Pgm03B from the discussion thread https://artofproblemsolving.com/community/c6h60830p .
See Also
1971 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |