Difference between revisions of "1971 IMO Problems/Problem 5"

Revision as of 02:04, 11 January 2025

Problem

Prove that for every natural number $m$ , there exists a finite set $S$ of points in a plane with the following property: For every point $A$ in $S$ , there are exactly $m$ points in $S$ which are at unit distance from $A$ .

Solution 1

I shall prove a more general statement about the unit distance graph( $V=\mathbb{R}^2$ , adjacency iff the Euclidean distance between the points is $1$ ) and this will follow as a consequence. if $G,H$ occur as unit distance graphs, then so does $G\times H$ ( here $G\times H$ is described as $V(G\times H)=V(G)\times V(H), (v_1,w_1)\leftrightarrow (v_2,w_2) \Leftrightarrow v_1=v_2,w_1\leftrightarrow w_2$ or $v_1\leftrightarrow v_2,w_1=w_2$ ). this is seen by describing the vertices by complex numbers. suppose there is an embedding of $G$ by the complex numbers $v_1,v_2\ldots,v_n$ and for $H$ by the numbers $w_1,w_2,\ldots, w_m$ . we claim that for some choice of $0\leq\theta<2\pi$ , $v_i+e^{i\theta}w_j$ will do the job(a suitable rotation). what we need is that $(v_i+e^{i\theta}w_j)\leftrightarrow (v_k+e^{i\theta}w_l)$ iff either $v_i=v_k,|w_j-w_l|=1$ or $w_j=w_l,|v_i-v_k|=1$ . clearly if the condition holds then the adjacency is satisfied. suppose $i\neq k,j\neq l$ and that the corresponding complex numbers are at a distance $1$ from one another. Then this gives a quadratic in $e^{i\theta}$ and hence $\theta$ can take only finitely many values here.ruling this out for each such set of $i,j,k,l$ hence rules out finitely many values of $\theta$ and therefore a suitable choice exists. for the given problem we need a unit distance graph which is regular of degree $m$ for any given $m$ . since we can form the graph $K_2$ , we can form $Q_n=Q_{n-1}\times K_2$ (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 $S$ has the form $S_m=\left\{\sum_{\mathbf v \in U} \mathbf v \;\middle\vert\; U \subseteq V_m\right\}=\left\{\sum_{i=1}^m b_i \mathbf v_i \;\middle\vert\; b_i \in \{0,1\}\right\}\!,$ where $V_m=\{\mathbf v_1,\mathbf v_2,\dots,\mathbf v_m\}$ is unknown set of distinct unit vectors in $\mathbb R^2$ . We can build $V_m$ 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 $2^m$ vectors in $S_m$ 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 $b_i$ in the sum changes from $0$ to $1$ ). If these two conditions are kept, then each of $2^m$ points at $S_m$ will be at unit distance from exactly $m$ points corresponding to sums at which one and only one of $m$ coefficients differs from coefficients of this point. However, respecting these conditions is not hard because $\left\|\sum_{\mathbf v \in U_1} \mathbf v - \sum_{\mathbf v \in U_2} \mathbf v\right\|=\left\|\sum_{\mathbf v \in U_1 \setminus U_2} \mathbf v \,-\! \sum_{\mathbf v \in U_2 \setminus U_1} \mathbf v\right\|$ and for each new vector being added to $V_m$ 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 $m$ 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 $A$ has exactly $m$ neighbors at distance $1$ 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 $S$ as a graph in the plane. Specifically, the vertices are the points in $S$ , and the edges are the line segments of length $1$ joining the points. All points at distance $1$ are joined, and only the points at distance $1$ are joined.

We will call such a graph $m$ -regular iff every $A \in S$ has exactly $m$ lines of the graph with one end at $A$ , in other words, there are exactly $m$ points in $S$ at unit distance from $A$ ..

For the purposes of solution 1, it will be useful to think of the points $A \in S$ 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 $O$ . We will work with vectors in the plane. The points $A \in S$ 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 $m$ . First some notation:

Given two finite sets of points $S, T$ in the complex plane, and given $\theta \in [0, 2\pi)$ , define $U = S \oplus_\theta T = \{a + e^{i \theta} b, \text{\ for all\ } a \in S, b \in T\}$ .

$\mathbf{Proposition}$ : If $S$ is $m$ -regular and $T$ is $n$ -regular, and $S \cap T = \emptyset$ , then we can choose $\theta$ so that $U = S \oplus_\theta T$ is $(m + n)$ -regular.

$\mathbf{Proof}$ : Let $a_i, i = 1, \dots, m$ be the neighboring points in $S$ at distance $1$ from $a$ , and $b_j, j = 1, \dots, n$ be the neighboring points in $T$ at distance $1$ from $b.$ Clearly $a_i + e^{i \theta} b$ is at distance $1$ from $a + e^{i \theta} b$ and $a + e^{i \theta} b_j$ is at distance $1$ from $a + e^{i \theta} b$ . So $a + e^{i \theta} b$ has $(m + n)$ neighbors at distance $1$ if we choose $\theta$ such that $a_i + e^{i \theta} b \neq a + e^{i \theta} b_j$ for all $i, j$ .

But the equations $a_i + e^{i \theta} b = a + e^{i \theta} b_j$ are just a finite number of linear equations in $e^{i \theta}$ , so we just have to avoid choosing $\theta$ giving a solution to any of these equations. Thus, with such a choice of $\theta$ there are definitely at least $(m + n)$ points in $U$ at distance $1$ from $a + e^{i \theta} b$ .

We have to show that we can choose $\theta$ so that there are no more than $(m + n)$ points at distance $1$ . If we had more points from $U$ at distance $1$ from $a + e^{i \theta} b$ , we would have $\vert (a + e^{i \theta} b) - (a_i + e^{i \theta} b_j) \vert = 1$ .

This would imply $\vert (a + e^{i \theta} b) - (a_i + e^{i \theta} b_j) \vert^2 = 1$ ,

or $\vert (a - a_i) + e^{i \theta} (b - b_j) \vert^2 = 1$ ,

or $[(a - a_i) + e^{i \theta} (b - b_j)] [\overline{(a - a_i)} + e^{-i \theta} \overline{(b - b_j)}] = 1$ ,

or $\vert (a - a_i) \vert^2 + e^{i \theta} \overline{(a - a_i)}(b - b_j) + e^{-i \theta} (a - a_i) \overline{(b - b_j)} + \vert (b - b_j) \vert^2 = 1$ .

This becomes an equation of degree $2$ in $e^{i \theta}$ . So as long as we choose $\theta$ not to equal to any of the solutions of these equations, we can be sure that none of the points in $U$ are at distance $1$ from $a + e^{i \theta} b$ .

This proves the proposition.

Now the problem is very simple to prove by induction.

For $m = 1$ , take $S_1 = \{0, 1\}$ . Assume we have $S_{m-1}$ an $(m-1)$ -regular graph. Using the proposition, it follows that we can choose $\theta$ such that $S_m = S_{m-1} \oplus_{\theta} T_1$ is an $m$ -regular graph, where $T_1$ consists of two points in the plane at distance $1$ , none of which is in $S_{m-1}$ .

(Just for the sake of completeness, let us mention that when we choose $\theta$ , it can be any value in $[0, 2\pi)$ which differs from a finite set of values modulo $2\pi$ , dependent on the points in $S_{m-1}, T_1$ .)

Solution 2, rewritten

Given a set $V = \{ \mathbf{v_1}, \dots, \mathbf{v_m} \}$ of $m$ vectors in the plane, define

$S(V) = \left\{ \sum_{i=1}^m \alpha_i \mathbf{v_i}, \text{\ where\ } \alpha_i \in \{0, 1\} \right\} = \left\{ \sum_{\mathbf{v} \in U} \mathbf{v}, \text{\ where\ } U \subset V \right \}.$

Let $S_V =$ the set of end points of all $\mathbf{v} \in S(V)$ .

Note that in the case $\alpha_i = 0$ for all $i = 1, \dots, m$ , the sum $\sum_{i=1}^m \alpha_i \mathbf{v_i} = 0$ , which yields the point $O$ (the origin) in the plane. In the notation $\sum_{\mathbf{v} \in U} \mathbf{v}$ this corresponds to $U = \emptyset$ . (Just as a curiosity, note that if $V$ contains $m$ vectors, then $S_V$ contains $\leq 2^m$ points. We are not going to use this fact.)

We will prove by induction on $m$ that there is a set $V$ of $m$ unit vectors with the starting point at $O$ , such that the vector sums in $S(V)$ are all distinct, and $S_V$ is $m$ -regular. If $m = 1$ , take $V = \{\mathbf{v_1}\}$ , where $\mathbf{v_1}$ is a unit vector starting at $O$ . Then $S(V)$ consists of $\mathbf{v_1}$ , and $S_V$ consists of the origin $O$ and the end point of $\mathbf{v_1}$ , so it is clearly a $1$ -regular set.

Now assume that we have a set of unit vectors starting at $O$ , $V = \{ \mathbf{v_1}, \dots, \mathbf{v_m} \}$ , such that the sums in the corresponding $S(V)$ are all distinct, and $S_V$ is $m$ -regular. We want to show that we can find a unit vector $\mathbf{v_{m+1}}$ starting at $O$ , such that if we take $W = V \cup \{ \mathbf{v_{m+1}} \}$ , then the vector sums in $S(W)$ are all distinct, and $S_W$ is $(m+1)$ -regular. Note that $S(V) \subset S(W)$ and $S_V \subset S_W$ .

The first condition (i.e. the sums in $S(W)$ being distinct) would fail when there are $s_1, s_2 \in S(V)$ such that $s_1 + \mathbf{v_{m+1}} = s_2$ . That means that $\mathbf{v_{m+1}}$ has to avoid satisfying a finite number of equations.

Now take $A \in S_V$ corresponding to $s_1 \in S(V)$ . Then, the same $A$ viewed as a point in $S_W$ has at least $(m + 1)$ neighbors at unit distance, namely the $m$ neighbors it has in $S_V$ and the point $B$ corresponding to $s_1 + \mathbf{v_{m+1}}$ . It would have more neighbors at unit distance if we would have $s_2$ (where $s_2 \neq s_1$ and $s_2$ not at unit distance from $s_1$ ) such that the end points of $s_1 + \mathbf{v_{m+1}}$ and $s_2$ would be at distance $1$ . So, the end point of the unit vector $\mathbf{v_{m+1}}$ should not be at unit distance from the end point of the vector $s_2 - s_1$ . This gives yet another finite set of conditions $\mathbf{v_{m+1}}$ should avoid satisfying.

Now take $B \in S_W$ corresponding to $s_1 + \mathbf{v_{m+1}}$ for a $s_1 \in S(V)$ . Let $t_1, \dots, t_m \in S(V)$ be the vectors which give the points in $S_V$ at unit distance from the point corresponding to $s_1$ . Then $t_j + \mathbf{v_{m+1}}, j = 1, \dots, m$ and $s_1$ are $(m + 1)$ vectors whose end points are at unit distance from $B$ . There would be more points in $S_W$ at unit distance from $B$ if we had vectors $s_2 \in S(V)$ (where $s_2 \neq s_1$ and $s_2$ not at unit distance from $s_1$ ) such that the end points of $s_1 + \mathbf{v_{m+1}}$ and $s_2$ , or the end points of $s_1 + \mathbf{v_{m+1}}$ and $s_2 + \mathbf{v_{m+1}}$ would be at distance $1$ . The former is avoided by the choice of $\mathbf{v_{m+1}}$ made, and the latter is avoided because of the induction hypothesis.

Since there are only finite number of equations the unit vector $\mathbf{v_{m+1}}$ with starting point at $O$ has to avoid satisfying, it follows that we can find $\mathbf{v_{m+1}}$ such that $S_W$ is $(m+1)$ -regular.

Solution 3

This solution is based on the idea by Pgm03B from the discussion thread https://artofproblemsolving.com/community/c6h60830p .

TO BE CONTINUED. SAVING MID WAY SO I DON'T LOSE TEXT WRITTEN SO FAR.

@@ Line 63: / Line 63: @@
 We will call such a graph <math>m</math>-regular iff every <math>A \in S</math> has exactly
-<math>m</math> lines of the graph with one end at <math>A</math>.
+<math>m</math> lines of the graph with one end at <math>A</math>, in other words, there are
+exactly <math>m</math> points in <math>S</math> at unit distance from <math>A</math>..
 For the purposes of solution 1, it will be useful to think of the
@@ Line 69: / Line 70: @@
 of solution 2, it will be useful to think of the plane as having
 on origin <math>O</math>.  We will work with vectors in the plane.  The points
-<math>A \in S</math> will be the end points of vectors.
+<math>A \in S</math> 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.
@@ Line 135: / Line 139: @@
 it can be any value in <math>[0, 2\pi)</math> which differs from a finite set of values
 modulo <math>2\pi</math>, dependent on the points in <math>S_{m-1}, T_1</math>.)
 ==Solution 2, rewritten==
@@ Line 167: / Line 172: @@
 such that if we take <math>W = V \cup \{ \mathbf{v_{m+1}} \}</math>, then
 the vector sums in <math>S(W)</math> are all distinct, and <math>S_W</math> is <math>(m+1)</math>-regular.
+Note that <math>S(V) \subset S(W)</math> and <math>S_V \subset S_W</math>.
+The first condition (i.e. the sums in <math>S(W)</math> being distinct) would fail
+when there are <math>s_1, s_2 \in S(V)</math> such that <math>s_1 + \mathbf{v_{m+1}} = s_2</math>.
+That means that <math>\mathbf{v_{m+1}}</math> has to avoid satisfying a finite number
+of equations.
+Now take <math>A \in S_V</math> corresponding to <math>s_1 \in S(V)</math>.  Then, the same
+<math>A</math> viewed as a point in <math>S_W</math> has at least <math>(m + 1)</math> neighbors at unit
+distance, namely the <math>m</math> neighbors it has in <math>S_V</math> and the point <math>B</math>
+corresponding to <math>s_1 + \mathbf{v_{m+1}}</math>.  It would have more neighbors
+at unit distance if we would have <math>s_2</math> (where <math>s_2 \neq s_1</math> and <math>s_2</math>
+not at unit distance from <math>s_1</math>) such that the end points of
+<math>s_1 + \mathbf{v_{m+1}}</math> and <math>s_2</math>  would be at distance <math>1</math>.  So, the
+end point of the unit vector <math>\mathbf{v_{m+1}}</math> should not be at unit
+distance from the end point of the vector <math>s_2 - s_1</math>.  This gives yet
+another finite set of conditions <math>\mathbf{v_{m+1}}</math> should avoid
+satisfying.
+Now take <math>B \in S_W</math> corresponding to <math>s_1 + \mathbf{v_{m+1}}</math> for a
+<math>s_1 \in S(V)</math>.  Let <math>t_1, \dots, t_m \in S(V)</math> be the vectors which
+give the points in <math>S_V</math> at unit distance from the point corresponding
+to <math>s_1</math>.  Then <math>t_j + \mathbf{v_{m+1}}, j = 1, \dots, m</math> and <math>s_1</math>
+are <math>(m + 1)</math> vectors whose end points are at unit distance from <math>B</math>.
+There would be more points in <math>S_W</math> at unit distance from <math>B</math> if we
+had vectors <math>s_2 \in S(V)</math> (where <math>s_2 \neq s_1</math> and <math>s_2</math> not at
+unit distance from <math>s_1</math>) such that the end points of
+<math>s_1 + \mathbf{v_{m+1}}</math> and <math>s_2</math>, or the end points of
+<math>s_1 + \mathbf{v_{m+1}}</math> and <math>s_2 + \mathbf{v_{m+1}}</math> would be at
+distance <math>1</math>.  The former is avoided by the choice of
+<math>\mathbf{v_{m+1}}</math> made, and the latter is avoided because of the
+induction hypothesis.
+Since there are only finite number of equations the unit vector
+<math>\mathbf{v_{m+1}}</math> with starting point at <math>O</math> has to avoid satisfying,
+it follows that we can find <math>\mathbf{v_{m+1}}</math> such that <math>S_W</math> is
+<math>(m+1)</math>-regular.
+==Solution 3==
@@ Line 174: / Line 224: @@
+This solution is based on the idea by Pgm03B from the discussion
+thread https://artofproblemsolving.com/community/c6h60830p .

1971 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search