Prove that for every positive integer we can find a finite set of points in the plane, such that given any point of , there are exactly points in at unit distance from .
Solution
1. Introduction and General Statement:
We aim to prove that for every positive integer , there exists a finite set of points in the plane such that each point in has exactly points in 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 where and two vertices are adjacent if and only if the Euclidean distance between them is 1. We will show that if and are unit distance graphs, then their Cartesian product is also a unit distance graph.
3. Cartesian Product of Graphs:
The Cartesian product is defined as follows:
and two vertices and are adjacent if and only if:
Here, denotes adjacency in the respective graphs.
4. Embedding Using Complex Numbers:
Suppose is embedded in the complex plane with vertices and with vertices . We claim that for some choice of , the points will form the required embedding.
5. Condition for Adjacency:
We need to show that:
If the condition holds, adjacency is satisfied. Suppose and , and the corresponding complex numbers are at a distance 1 from each other. This gives a quadratic equation in , which can have only finitely many solutions.
6. **Choosing **:
By ruling out finitely many values of for each set of , we can find a suitable that satisfies the adjacency condition.
7. Constructing the Graph:
For the given problem, we need a unit distance graph that is regular of degree . We can start with the graph (a single edge) and form the -dimensional hypercube by iteratively taking the Cartesian product . The -dimensional hypercube is a regular graph of degree .
8. Conclusion:
By choosing , we obtain a finite set of points in the plane such that each point has exactly points at a unit distance from it.