info prev up next book cdrom email home

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 $N$th 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,\ldots,N\}$ and every $k\in\{1,\ldots,n\}$, the inequality

{k-1\over n}\leq x_i<{k\over n}

holds for some $i\in\{1,\ldots,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
${\textstyle{4\over 7}}\leq x_1<{\textstyle{7\over 12}}, {\textstyle{2\over 7}}\...
...6\over 17}}\leq x_3<1, {\textstyle{1\over 14}}\leq x_4<{\textstyle{1\over 13}},$
${\textstyle{8\over 11}}\leq x_5<{\textstyle{11\over 15}}, {\textstyle{5\over 11...
...textstyle{2\over 13}}, {\textstyle{14\over 17}}\leq x_8<{\textstyle{5\over 6}},$
${\textstyle{3\over 8}}\leq x_9<{\textstyle{5\over 13}}, {\textstyle{11\over 17}...
...xtstyle{2\over 3}}, {\textstyle{3\over 14}}\leq x_{11}<{\textstyle{3\over 13}},$
${\textstyle{15\over 17}}\leq x_{12}<{\textstyle{11\over 12}}, {\textstyle{1\over 2}}\leq x_{12}<{\textstyle{9\over 17}}, 0\leq x_{14}<{\textstyle{1\over 17}},$
$ {\textstyle{13\over 17}}\leq x_{15}<{\textstyle{4\over 5}}, {\textstyle{5\over...
...tyle{6\over 17}}, {\textstyle{10\over 17}}\leq x_{17}<{\textstyle{11\over 17}}.$
Warmus (1976) states that there are 768 patterns of 17-point solutions (counting reversals as equivalent).

See also Discrepancy Theorem, Point Picking


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.

© 1996-9 Eric W. Weisstein