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 form
where
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 a very nice solution, simpler than the two above. It has a few flaws in the way it is presented. 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.
3. Finally, I will give some examples. Philosophically speaking, these
are nice, but "bad". They are bad for two reasons: on the one hand, I
don't think they can be generalized. On the other hand, it appears from
the three solutions we have, that the configurations of points in which
every point has exactly
neighbors at distance
are good
because they are not "nice". By contrast, the examples I give are "nice".
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 are the
points in
, and the edges 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
.
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
on origin
. We will work with vectors in the plane. The points
will be the end points of vectors.
Solution 1, rewritten
We will give a proof by induction on . First some notation:
Given two finite sets of points in the complex plane, 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
.
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.
Now the problem is very simple to prove by induction.
For , take
. 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 can be any 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.
TO BE CONTINUED. SAVING MID WAY SO I DON'T LOSE TEXT WRITTEN SO FAR.
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 |