Maths Olympiad Prep

Library / /130 of 520

Geometry Difficulty 6.5 National olympiad Find the answer

Prove that for every positive integer mm we can find a finite set SS of points in the plane, such that given any point AA of SS, there are exactly mm points in SS at unit distance from AA.

Solution

1. Introduction and General Statement:
We aim to prove that for every positive integer m m , there exists a finite set S S of points in the plane such that each point in S S has exactly m m points in S S at a unit distance from it. To do this, we will use a more general statement about unit distance graphs.

2. Unit Distance Graphs:
Consider the unit distance graph G G where V(G)=R2 V(G) = \mathbb{R}^2 and two vertices are adjacent if and only if the Euclidean distance between them is 1. We will show that if G G and H H are unit distance graphs, then their Cartesian product G×H G \times H is also a unit distance graph.

3. Cartesian Product of Graphs:
The Cartesian product G×H G \times H is defined as follows:
V(G×H)=V(G)×V(H) V(G \times H) = V(G) \times V(H)
and two vertices (v1,w1)(v_1, w_1) and (v2,w2)(v_2, w_2) are adjacent if and only if:
(v1=v2 and w1w2) or (v1v2 and w1=w2) (v_1 = v_2 \text{ and } w_1 \leftrightarrow w_2) \text{ or } (v_1 \leftrightarrow v_2 \text{ and } w_1 = w_2)
Here, \leftrightarrow denotes adjacency in the respective graphs.

4. Embedding Using Complex Numbers:
Suppose G G is embedded in the complex plane with vertices v1,v2,,vn v_1, v_2, \ldots, v_n and H H with vertices w1,w2,,wm w_1, w_2, \ldots, w_m . We claim that for some choice of 0θ<2π 0 \leq \theta < 2\pi , the points vi+eiθwj v_i + e^{i\theta} w_j will form the required embedding.

5. Condition for Adjacency:
We need to show that:
(vi+eiθwj)(vk+eiθwl)    (vi=vk and wjwl=1) or (wj=wl and vivk=1) (v_i + e^{i\theta} w_j) \leftrightarrow (v_k + e^{i\theta} w_l) \iff (v_i = v_k \text{ and } |w_j - w_l| = 1) \text{ or } (w_j = w_l \text{ and } |v_i - v_k| = 1)
If the condition holds, adjacency is satisfied. Suppose ik i \neq k and jl j \neq l , and the corresponding complex numbers are at a distance 1 from each other. This gives a quadratic equation in eiθ e^{i\theta} , which can have only finitely many solutions.

6. **Choosing θ\theta**:
By ruling out finitely many values of θ\theta for each set of i,j,k,l i, j, k, l , we can find a suitable θ\theta that satisfies the adjacency condition.

7. Constructing the Graph:
For the given problem, we need a unit distance graph that is regular of degree m m . We can start with the graph K2 K_2 (a single edge) and form the n n -dimensional hypercube Qn Q_n by iteratively taking the Cartesian product Qn1×K2 Q_{n-1} \times K_2 . The n n -dimensional hypercube Qn Q_n is a regular graph of degree n n .

8. Conclusion:
By choosing n=m n = m , we obtain a finite set S S of points in the plane such that each point has exactly m m points at a unit distance from it.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.