Problem of the Week 1216
Distances in Sequence
Solution
Problem 1216 was solved by Joseph DeVincentis, Stephen Meskin, John Sullivan, and John Duncan. The given problem is solved by the vertices of an isosceles triangle with base 2 and legs &sqrt;3, with the base midpoint included. The altitude has length √2 so the distance set (squared) is 0, 0, 0, 0, 1, 1, 2, 3, 3, 4. We do not know if this is the unique solution to this problem. It seems like it might be, but a proof is lacking.
The source for this problem was Ed Pegg's nice observation that the 24 vertices of a truncated octahedron (see http://mathworld.wolfram.com/TruncatedOctahedron.html) have squared distances equal to 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. The vertices are:
|
{-(3/2), -(1/2), 0}
|
{-(3/2), 1/2, 0}
|
{-1, -1, -(1/√2)}
|
{-1, -1, 1/√2}
|
|
{-1, 1, -(1/√2)}
|
{-1, 1, 1/√2}
|
{-(1/2), -(3/2), 0}
|
{-(1/2), -(1/2), -√2}
|
|
{-(1/2), -(1/2), √2}
|
{-(1/2), 1/2, -√2}
|
{-(1/2), 1/2, √2}
|
{-(1/2), 3/2, 0}
|
|
{1/2, -(3/2), 0}
|
{1/2, -(1/2), -√2}
|
{1/2, -(1/2), √2}
|
{1/2, 1/2, -√2}
|
|
{1/2, 1/2, √2}
|
{1/2, 3/2, 0}
|
{1, -1, -(1/√2)}
|
{1, -1, 1/√2}
|
|
{1, 1, -(1/√2)}
|
{1, 1, 1/√2}
|
{3/2, -(1/2), 0}
|
{3/2, 1/2, 0}
|
The 300 distances (Binomial[24, 2] + 24 since we include (v, v)) are, in tallied form,
{0, 24}
{1, 36}
{2, 12}
{3, 48}
{4, 24}
{5, 24}
{6, 24}
{7, 48}
{8, 12}
{9, 36}
{10, 12}
John Duncan found that the following set of 7 points does the same thing:
(0, 0, 0)
(1, 0, 0)
(-1, 0, 0)
(2, 0, 0)
(2, 0, 1)
(0, 0, 2)
(1, √2, 0)
The distances squared are {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10}
One can get this with fewer points by moving up in dimension. Ed Pegg found this quintet in 6-space. The squared distances are 0 through 10.
{1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 6, 5}, {1, 2, 5, 3, 4, 6}, {2, 1, 3, 5, 6, 4}, {2, 1, 6, 4, 5, 3}
And these next 6 points in 4-space give squared-distances 0 through 15.
{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 1, 1, 0}, {0, 2, 2, 2}, {2, 0, 0, 1}, {2, 3, 1, 0}
Duncan, M.J. Crabb, and Colin McGregor have further proved that this solution is unique. That is, there is, up to isometry, a unique set of four points in the plane so that the set of squared distances between all pairs of points is, ignoring duplicates, 0, 1, 2, 3, 4. Download notes from stanwagon.com/public/1205JohnDuncanNotesOnUniqueness.pdf
Reference: This all seems to be related to the permutohedron, but I fear I have not digested all the connections. See https://oeis.org/A175929
In 4-space one has the Omnitruncated 5-cell, or great prismatodecachoron, and the squared-distance set is
{0, 1, 2, 3, ..., 20}: https://en.wikipedia.org/wiki/Runcinated_5-cell#Omnitruncated_5-cell
Problems about distances have a long history. This reference is relevant both to this problem and to PoW 2014.
P. Erdos & Richard K. Guy, Distinct distances between lattice points, Elem. Math. 25 (1970) 121-123.
[Back to Problem 1216]
© Copyright 2015 Stan Wagon. Reproduced with permission.
|