4
$\begingroup$

[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!]

I was recently reading over a nice puzzle called the four points, two distances problem:

Find all the ways to arrange $4$ points so that only $2$ distances occur between any two points.

The author of this piece, Alex Bellos, demonstrates with pictures that there are six such configurations. The explanation includes pictures of each of these six configurations, as well as a pointer back to writing from Colin Wright (link) who links to the problem's formulation by Peter Winkler (link).

That question is about $n = 4$ points, for which the set of distances between point pairs has size $k = 2$, and the entire matter is situated in dimension $d = 2$. After assigning this problem to high school students with some success, we have come to wonder about what can be meaningfully observed for more general cases.

Our question, and most general formulation, is:

In how many ways can you arrange $n$ points so that exactly $k$ distances occur between any two points in dimension $d$?

In this formulation, the original puzzle asserts that $(n,k,d) = (4,2,2)$ yields an answer of $6$.

Relevant resources that discuss this problem (or something related) are welcome, as are nontrivial statements that can be made about our general question. For example, are there nontrivial bounds that can be given for the case of $d=2$ as $n$ and $k$ vary?

Please edit and/or [re]tag if it will improve clarity!

Note: As per the comments, one goal is to indicate how difficult this problem is when asked in such generality. So, responses that indicate how difficult a sub-question here is (e.g., MO 58203 as pointed out by Gerry Myerson) will be great, too.

Improve this question
$\endgroup$
5
  • $\begingroup$ One observation: If $d$ is big enough (I think $\geq\! n-1$ is big enough), then all the geometric obstructions disappear and your problem becomes purely combinatorial. Specifically, if $d \geq n-1$ then $(n,k,d)$ yields the answer of however many ways there are to color the edges of $K_n$ with exactly $k$ colors. For example, in $3$ or more dimensions the problem with $4$ points and $2$ distances has $9$ solutions instead of just $6$. So I think the interesting cases are where $1 < d < n-1$, because that's where the geometry really matters. $\endgroup$
    – Will Brian
    Commented Nov 7, 2019 at 20:12
  • $\begingroup$ @WillBrian [Pointing out the obvious but] There are also uninteresting cases when $k > n(n-1)/2 =$ the number of point pairings; specifically, the answer in these cases will be zero: e.g., there is no way to place $4$ points so that exactly $7$ distinct distances arise. I'm not sure whether to include these constraints in the original post; feel free to edit as you deem appropriate! $\endgroup$
    – Benjamin Dickman
    Commented Nov 7, 2019 at 20:20
  • 1
    $\begingroup$ There are some very hard, even unsolved, questions here. You might enjoy mathoverflow.net/questions/58203/erdos-distance-problem-n-12 See also oeis.org/A131628 and oeis.org/A186704 $\endgroup$
    – Gerry Myerson
    Commented Nov 7, 2019 at 21:13
  • 1
    $\begingroup$ @GerryMyerson This pointer is great; thanks! Alon Amit's response from just four days ago - and using Desmos! - is especially timely. Part of our class is focused on developing problems of the right size, and the main question asked here is Way Too Big, So, references that help indicate oversize are of definite interest, as are references that point to the boundaries of known results. $\endgroup$
    – Benjamin Dickman
    Commented Nov 7, 2019 at 21:33
  • $\begingroup$ SHouldn't there be a definition of being "the same configuration" be included in the question? $\endgroup$
    – Behnam Esmayli
    Commented Nov 8, 2019 at 1:59

0

Reset to default

You must log in to answer this question.