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 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 |