TOPICS
Search

18-Point Problem


Place a point somewhere on a line segment. Now place a second point and number it 2 so that each of the points is in a different half of the line segment. Continue, placing every Nth point so that all N points are on different (1/N)th of the line segment. Formally, for a given N, does there exist a sequence of real numbers x_1, x_2, ..., x_N such that for every n in {1,...,N} and every k in {1,...,n}, the inequality

 (k-1)/n<=x_i<k/n

holds for some i in {1,...,n}? Surprisingly, it is only possible to place 17 points in this manner (Berlekamp and Graham 1970, Warmus 1976).

Steinhaus (1979) gives a 14-point solution (0.06, 0.55, 0.77, 0.39, 0.96, 0.28, 0.64, 0.13, 0.88, 0.48, 0.19, 0.71, 0.35, 0.82), and Warmus (1976) gives the 17-point solution

 4/7<=x_1<7/(12),2/7<=x_2<5/(17),(16)/(17)<=x_3<1,1/(14)<=x_4<1/(13), 
8/(11)<=x_5<(11)/(15),5/(11)<=x_6<6/(13),1/7<=x_7<2/(13), 
(14)/(17)<=x_8<5/6,3/8<=x_9<5/(13),(11)/(17)<=x_(10)<2/3, 
3/(14)<=x_(11)<3/(13),(15)/(17)<=x_(12)<(11)/(12),1/2<=x_(12)<9/(17), 
0<=x_(14)<1/(17),(13)/(17)<=x_(15)<4/5,5/(16)<=x_(16)<6/(17), 
(10)/(17)<=x_(17)<(11)/(17).

Warmus (1976) states that there are 768 patterns of 17-point solutions (counting reversals as equivalent).


See also

Discrepancy Theorem, Point Picking

Explore with Wolfram|Alpha

References

Berlekamp, E. R. and Graham, R. L. "Irregularities in the Distributions of Finite Sequences." J. Number Th. 2, 152-161, 1970.Gardner, M. The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications. New York: Springer-Verlag, pp. 34-36, 1997.Steinhaus, H. "Distribution on Numbers" and "Generalization." Problems 6 and 7 in One Hundred Problems in Elementary Mathematics. New York: Dover, pp. 12-13, 1979.Warmus, M. "A Supplementary Note on the Irregularities of Distributions." J. Number Th. 8, 260-263, 1976.

Referenced on Wolfram|Alpha

18-Point Problem

Cite this as:

Weisstein, Eric W. "18-Point Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/18-PointProblem.html

Subject classifications