18-point problem

Input interpretation

18-point problem

Definition

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 element {1, ..., N} and every k element {1, ..., n}, the inequality (k - 1)/n<=x_i<k/n holds for some i element {1, ..., n}? Surprisingly, it is only possible to place 17 points in this manner (Berlekamp and Graham 1970, Warmus 1976).
More information »

Related terms

discrepancy theorem | point picking

Subject classifications

MathWorld

packing problems | random point picking

MSC 2010

41-XX | 51E23
POWERED BY THE WOLFRAM LANGUAGE