There are $ n \geq 5$ pairwise different points in the plane. For every point, there are just four points whose distance from which is $ 1$. Find the maximum value of $ n$.
Problem
Source: China TST 2004 Quiz
Tags: combinatorics unsolved, combinatorics
01.02.2009 17:35
As stated, the infinite square lattice is such a set. What's it supposed to say?
02.02.2009 17:45
Minimum. See Zhaoli's pdf in http://www.mathlinks.ro/viewtopic.php?t=5283
24.08.2019 18:11
The minimum value of $n$ is $\boxed{9}.$ First let us construct this. Throw the points onto the complex plane. Let $a, b$ denote the complex numbers $e^{i \sqrt 2}, e^{i \sqrt 3},$ respectively. Let $c, d$ denote the complex numbers $a \cdot e^{i \frac{\pi}{3}}, b \cdot e^{i \frac{\pi}{3}}.$ Then, we claim that the set of $9$ points corresponding to the complex numbers in the set $\{0, a, c\} + \{0, b, d\}$ works. This is easily verified. Let us now show that $9$ is indeed optimal. Consider the graph on the given $n$ points where we connect two points iff their distance is $1.$ It's easy to see that a $K_4$ is impossible, and so this easily proves $n \ge 6.$ Suppose that $n = 6.$ Take two points $A, B$ which are connected. As there are four other points, and each of $A, B$ is connected to three of them, there exists a point $C$ so that $\triangle ABC$ is equilateral. Now, there's three other points $D, E, F$. Each of $A, B, C$ is connected to two of them, so it follows that $\triangle DEF$ is the anticomplementary triangle of $\triangle ABC.$ These six points clearly do not work. Suppose that $n = 7.$ Again, we can force an equilateral $\triangle ABC.$ Let $D, E, F, G$ be the other four points. Each of $A, B, C$ is connected to exactly two of them. Furthermore, each of $D, E, F, G$ is connected to at most $2$ of $A, B, C.$ As there are a total of $3 \cdot 2 = 6$ connections between $\{A, B, C\}$ and $\{D, E, F, G\}$, we can WLOG assume that $D$ is connected to $A, B$ and $E$ is connected to $B, C.$ Up to this point, $D$ is connected to only $A, B$, and so thus it must be connected to both $F$ and $G$. Analogously, so must $E$. However, as $D, E$ are a distance two apart, this is clearly absurd. There are essentially two cases to be considered when $n =8.$ Case 1. There is an equilateral triangle Let's again suppose that $\triangle ABC$ is equilateral. As there are five other points, and again $3 \cdot 2 = 6$ connects between $A, B, C$ and the others, we know that there exists $D$ which is connected to $A, B$, WLOG. Observe that $C, D$ each have only two connections up to this point ($A$ and $B$). Furthermore, every point which isn't $A$ or $B$ is connected to at most one of $C, D.$ Hence, among the other four points $E, F, G, H$, we know that exactly two of them are connected to $D$, and exactly two are connected to $C.$ In other words, if we let $\omega_c, \omega_d$ be the circles centered at $C, D$ with radius $1$, two of $E, F, G, H$ lie on $\omega_c$ and two on $\omega_d.$ Observe that $A$ is connected only to $A, B, C$ at this point, and so WLOG $E$ is connected to $A$. By symmetry, we may also assume that $E \in \omega_c.$ This implies that $\triangle ACE$ is equilateral. However, notice that $E$ can now be connected to at most $2$ points on $\omega_c$ ($A$ and possibly another point) and no points on $\omega_d$ which are not $A$. Hence, $E$ is connected to at most three points: $A, C,$ and potentially the other point on $\omega_c$. Thus, this case is a failure. Case 2. There is no equilateral triangle. Let $A, B$ be two connected points. Let $\omega_a, \omega_b$ be the circles centered at $A, B$ with radius $1.$ Since no points are on both $\omega_a, \omega_b$ (else an equilateral triangle is formed), each point is on precisely one of $\omega_a, \omega_b.$ Let $P \neq A$ be a point on $\omega_a.$ Then, it can't be connected to any other point on $\omega_a$ (else an equilateral triangle is formed), and is connected to at most two points on $\omega_b.$ This means that $P$ is connected to at most two points, and so this case is also a failure. As we've exhausted all cases when $n \le 8$ and concluded that no configurations of $n \le 8$ points work, we conclude that the minimum value of $n$ is $\boxed{9}.$