Prove that for every positive integer $m$ we can find a finite set $S$ of points in the plane, such that given any point $A$ of $S$, there are exactly $m$ points in $S$ at unit distance from $A$.
Problem
Source: IMO 1971, Day 2, Problem 5
Tags: geometry, combinatorial geometry, euclidean distance, point set, IMO, IMO 1971
14.11.2005 00:15
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.
15.09.2018 16:02
Do you know some easier solution?
15.09.2018 20:02
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.
04.05.2019 21:21
We will use induction on m. For m=1 take two points with the distance 1 Let P be a set of k distinct points on the plane such that the given statement holds for m=k. Let P' be a set of distinct points on the same plane, disjoint with P, so that if X,Y∈P then there exist X', Y'∈P' such that XYY'X' is a parallelogram. and XX'=YY'=1. We call image of X is X'. Note that there are infinitely many choices for P'. Now there are at least k+1 points at a unit distance from X∈P: k points in P and the point X'. There are at least k+1 points at a unit distance from X'∈P': k points in P'(image points of the k points, which is in P, which are at a unit distance from X , are at a unit distance from X') and the point X. Now we have to avoid situations like X'Y=1 where X'∈P' and Y∈P while X' is not the image of Y(i.e.X≠Y). Note X'X=X'Y=1. So X' lies on the perpendicular bisector of XY. So there are at most 2 possible choices for X' .This means there are at most two possible choices for P' so that X'Y=1, for particular points X and Y. If |P|=p then there are at most 2×(pC2) possible choices for P' such that X'Y=1 for some points X'∈P' and Y∈P.But there are infinitely many choices for P'. So we can avoid the above mentioned situations. Therefore we are done.