14
$\begingroup$

Does there exist a finite set of points on the Euclidean plane, such that:

  • No 3 points are collinear, and
  • Every one of the points has (at least) three other points in the set at the same distance from it?

It seems to me that the answer should be No, but my naïve attempts to prove it have failed.

$\endgroup$
14
  • 3
    $\begingroup$ When you say “every point [P] has at least three points [Q,R,S] in the same distance”, does that just mean PQ=PR=PS, or do you also require PQ=PR=PS=P’Q’=P’R’=P’S’ for any other P’? $\endgroup$
    – Matt F.
    Aug 4 at 16:53
  • 10
    $\begingroup$ For instance, the 8 points in the graph of a cube, drawn with all edges of length 1? $\endgroup$ Aug 4 at 17:07
  • 2
    $\begingroup$ Yes, of course, it was assumed to be on the plane. The example I wrote in answer is also a 2D projection of the 1-skeleton of a 4D polytope (the cartesian square of a triangle). $\endgroup$ Aug 4 at 19:26
  • 3
    $\begingroup$ @PietroMajer's comment above also solves the generalisation for $k$ instead of $3$ points at the same distance from each point - just take a suitable projection of the $k$-dimensional hypercube graph. $\endgroup$ Aug 5 at 7:30
  • 3
    $\begingroup$ It's simpler to talk not about a hypercube, etc. but about an $\ n$-point subset $\ V\ $ of the unit circle. Then we get the $\ 2^n$-set solution $$ E\ :=\ \left\{\sum K:\ K\subseteq2^V\right\}$$ $(\ V\ $ should be generic). $\endgroup$
    – Wlod AA
    Aug 5 at 12:39

7 Answers 7

30
$\begingroup$

enter image description here

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $

$\endgroup$
5
  • 5
    $\begingroup$ In words: two equilateral triangles on the same base, plus the rotation of that figure by $\arcsin(1/\sqrt(12))$ about one of the extreme vertices. $\endgroup$
    – Matt F.
    Aug 4 at 20:39
  • 19
    $\begingroup$ This is the Moser spindle, right? en.wikipedia.org/wiki/Moser_spindle $\endgroup$ Aug 4 at 23:02
  • $\begingroup$ @mattF. is the rotation angle actually $\sin^{-1}(1/\sqrt{12})$? Looks like twice that to me, in which case it would be $\cos^{-1}(5/6)$. $\endgroup$ Aug 5 at 12:30
  • $\begingroup$ A variation: insert a square between each pair of equilateral triangles. The rotation angle would be reduced accordingly to $2\sin^{-1}(1-\sqrt{3/4})$. $\endgroup$ Aug 7 at 16:01
  • $\begingroup$ @MattF. The notation $\sqrt{12}$ is coded in MathJax and LaTeX as \sqrt{12}. $\qquad$ $\endgroup$ Aug 8 at 20:00
17
$\begingroup$

The figure below has all line segments shown congruent. The quadrilaterals sharing edges with the central triangle are squares.

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ An interesting example. $\endgroup$
    – Wlod AA
    Aug 5 at 12:55
  • $\begingroup$ Certain subsets of tilings, e.g. this one should look similar and also satisfy the conditions specified. Oscar Lanzi's solution with 12 points seems to be the maximum so far. Makes one wonder what the actual maximum of number of points satisfying the specified conditions is, if there is one at all - I'd guess there is a maximum. $\endgroup$ Aug 5 at 19:09
  • 5
    $\begingroup$ There is no maximum. Draw any equilateral polygon, then translate one side-unit in any direction that avoids collinear triples and make a second copy. Every vertex on either copy is equidistant from its neighbors on the same copy and the corresponding vertex on the other copy. $\endgroup$ Aug 5 at 19:20
  • 2
    $\begingroup$ @OscarLanzi : Great! This way you get all even $n\geq 6$ as vertex number of such a configuration. If you attach to such a "double circle" 5 additional points to form a 7-point configuration including 2 points on one of the circles as given by Petrunin's answer, you get also all odd $n+5\geq11$ as vertex number. Since 7 and 9 are vertex numbers covered separately, for exactly all $n\geq 6$ we can find a suitable configuration. $\endgroup$ Aug 5 at 20:49
  • $\begingroup$ +1 for not requiring any line segment intersections :-P $\endgroup$
    – einpoklum
    Aug 7 at 21:41
11
$\begingroup$

Example: If $1,\xi,\xi^2$ are the three cubic roots of unity, (and $c$ is generic, with $|c|=1$) $\xi^k+c\xi^j$ gives a set of $9$ points, no three of which collinear, where each point has $4$ points at the same distance.

$\endgroup$
4
  • $\begingroup$ For c = ±1 al least two given points coincide and, moreover, there is a Re = const line (namely, Re = −1 for c = 1 and Re = 0 for c = −1) having three distinct points on it. The same for powers-of-ξ multiples. Why didn’t the author exclude bad values of c explicitly? $\endgroup$ Aug 5 at 9:13
  • 1
    $\begingroup$ Suppose we use fifth roots instead of cube roots. We generate 25 points and my understanding is that each of these has two sets of three equidistant neighbors, if we are careful to avoid degenerate cases. $\endgroup$ Aug 5 at 13:06
  • $\begingroup$ @IncnisMrsi shall I be completely honest: I said "$c$ is generic" and didn't exclude bad values of $c$ explicitly, just by laziness. It should be clear that the bad values are finitely many though. $\endgroup$ Aug 5 at 22:33
  • $\begingroup$ @OscarLanzi I agree, I'd say two sets of four equidistant neighbours, with distance resp. $1$ and the golden number $\endgroup$ Aug 5 at 22:39
8
$\begingroup$

Yes.

Place five points $P_1,P_2,P_3,P_4,P_5$ in a regular pentagon inscribed in the unit circle centered at the origin. For each of these points $P$, we're going to add another point $Q$ somewhere on the circle centered at $P$ and passing through the neighbors of $P$ on the pentagon:

enter image description here

If we choose consistent relative positions on each arc for the new $Q$'s, we will have five new points $Q_1, Q_2, Q_3, Q_4, Q_5,$ arranged in another pentagon centered at the origin. Our construction currently makes all the $P_i$'s circumcenters, but not all the $Q_i$'s. We want each $Q_i$ to be equidistant from $Q_{i+2}, Q_{i+3},$ and $P_i$ (where we take indices mod $5$).

If we choose each $Q_i$ to be the midpoint of our arc, then the distance $\overline{Q_iQ_{i+2}}$ will be less than $\overline{Q_iP_i}$. On the other hand, if each $Q_i$ all the way to the side approaching $P_{i+1}$, then the distance will be greater. So by continuity, there is a point at which they are equal, and each $Q_i$ is a circumcenter.

$\endgroup$
1
  • $\begingroup$ @Oscar Lanzi: the midpoint of the arc certainly doesn’t lie on any diagonal of the outer pentagon. Two respective isosceles triangles, mirror-symmetric, have angles 54° (marked with P on the drawing) and 63°, whereas all angles between sides and diagonals of a regular pentagon are multiples of 36°. Anyway some positions on the arc are not eligible due to collinearity constrain. $\endgroup$ Aug 5 at 9:45
5
$\begingroup$

While there are 6-point solutions, and 6 is the minimum, nevertheless there is a 7-point solution that feels to me to be the simplest, and it's very symmetric, namely

the regular 6-gon (hexagon) together with it's center.

$\endgroup$
4
  • 5
    $\begingroup$ This has collinear point triples though $\endgroup$ Aug 5 at 11:48
  • $\begingroup$ Oops, sorry. Thus, this is an imperfect while still symmetric almost-solution. $\endgroup$
    – Wlod AA
    Aug 5 at 12:00
  • 1
    $\begingroup$ Yes, I was fooled by collinearity as well when I had a solution based on a regular pentagon and pentagram. I have since revamped, see my answer which should work. $\endgroup$ Aug 5 at 12:15
  • $\begingroup$ @OscarLanzi's answer referenced above. $\endgroup$
    – LSpice
    Aug 8 at 20:43
4
$\begingroup$

I can't say much about colinearity here, but the current record holder in the Polymath Project for the "Hadwiger-Nelson problem" lists a 510-vertex unit distance graph of chromatic number 5, so in particular, an arrangement of 510 points where every point has at least four other points at distance 1.

$\endgroup$
6
  • 1
    $\begingroup$ My understanding is that chromatic number 5 means a vertex of the hraph/ region of the map has four bounding neighbors, not necessarily all of them. $\endgroup$ Aug 5 at 15:30
  • 2
    $\begingroup$ @OscarLanzi Suppose this graph has a vertex $v$ of degree 3 or lower. If $G-v$ has a 4-coloring, then we can add $v$ back in with no new color necessary, in contradiction to the claim $\chi(G)=5$. If $G-v$ has no 4-coloring then we would have found a smaller unit distance graph with chromatic number 5, and I just assumed that this would not have escaped the people working on this problem. So this is an argument from "trust in experts" :D $\endgroup$
    – M. Winter
    Aug 5 at 15:59
  • 1
    $\begingroup$ So the 510 is a minimum for four points at unit distance? But would not a graph of a hypercuve give that result with 16? $\endgroup$ Aug 5 at 16:12
  • $\begingroup$ @OscarLanzi It is the smallest known such graph with chromatic number 5, which wasn't asked for, but the answer of Anton reminded me of this. The hypercube solution is much more flexible and someone should write it down as an answer. $\endgroup$
    – M. Winter
    Aug 5 at 16:17
  • 1
    $\begingroup$ @TimothyChow There is a deleted answer by Florian Lehner describing this idea, and I don't see why it is deleted. Start with a drawing of the d-cube graph into the plane so that each vertex has d neighbors at distance 1 (certainly possible for d=1). Then add a copy of that embedding translated into a generic direction by 1 unit. Then I connect it up to get the (d+1)-cube . I don't see any colinearities. $\endgroup$
    – M. Winter
    Aug 7 at 10:20
2
$\begingroup$

This text is an extended Answer that I have posted some 17h ago and removed some 16h ago.

THE NEW PART: I've removed my answer because @PietroMajer has posted earlier (some 19h ago) an elegant 9-point example that had a richer and more impressive structure (and Pietro has posted a comment under the OP too). This 9-point solution contained a 6-point solution.

However, I've decided to mention the existence of that 6-point solution explicitly. Of the Pietro's 9 points one may take only 6-points

$$ \{\xi^k+c\cdot\xi^j: k=0,1,2\ \ \text{and}\ \ j=0,1\} $$

THE OLD PART (posted about 3h after @PietroMajer's solution):

In $\ \mathbb C,\ $ let $a$ and $b$ and $c$ be the vertices of a triangle such that $\ |a-c|=|b-a|=|c-a|=1.\ $ Let $\ v\in\mathbb C\ $ be such that $\ |v|=1,\ $ and $\ \pm v\ $ be different from any $\ a-c\ $ or $\ b-a\ $ or $\ c-a.\ $ Then the $\ 6$-point set consisting of points $\ x+v,\ $ where $\ x\ $ is any of the points $\ a\ $ or $\ b\ $ or $\ c\ $ together with these three points, provides an example of a $\ 6$-point planar set such that each point has distance $\ 1\ $ from at least three other selected points.

Is $\ 6\ $ the record or is it $\ 5?$ — I feel lazy :) but this should not be a difficult question to settle.

Oh, $\ 5\ $ is impossible. This is a simple exercise. Thus, the record is $\ \mathbf 6$.



PS. 5-point solution is impossible even if collinearity was allowed.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.