Skip to main content
4 of 4
I added the quotation of Steinhaus as suggested in one of the comments. I removed a comment about being unable to resolve a question of formatting since that prolem had been taken care of in a previous edit.

A Problem Related to the 17 Point Problem of Steinhaus

In his book of problems from elementary mathematics Hugo Steinhaus asked the following:
does there exist for every positive integer N 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} we have

$(k-1)/n\le x_i<k/n$ for some i in {1,...,n}. If not, what is the greatest possible N?

In a paper of more than 40 years ago: "Irregularities in the Distributions of Finite Sequences", E.R. Berlekamp and R.L. Graham , Journal of Number Theory 2,152-161 (1970), the authors define a number, a generalization of Steinhaus's problem, $s=s(d)$ in the following way.

"For $n \ge1,0 \le k\lt n$ , define

$B_{n,k}=[k/n, k/n+1/n)$.

Fix an integer $d \ge 0$ and suppose $(x_1,x_2,...,x_{s+d})$ is a sequence with $x_i$ belonging to $[0,1)$ and with $s=s(d)$ chosen to be maximal such that for each $r \le s$ and each $k \lt r$, $B_{r,k}$ contains at least one point of the subsequence
$(x_1,x_2,...,x_{r+d})$,"

$s(0)$ is the answer to the question of Hugo Steinhaus and is known to be 17. The calculation to find $s(0)$ takes only seconds. I believe that it is possible to calculate $s(1)$ in a reasonable amount of time, perhaps weeks. I'd be willing to make my Mathematica program available to anyone who's interested.

What is the value of $s(1)$?