# 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)$?

• Could you quote Hugo Steinhaus? (It'd be easier to understand the problem). – Włodzimierz Holsztyński Nov 1 '13 at 7:28
• David will know that Graham has returned to this problem in a paper, A note on irregularities of distribution, in Integers 13 (2013), available at emis.de/journals/INTEGERS/papers/n53/n53.pdf --- in this paper, Graham gets $s(d)\lt16000d^3$, a bound he calls "rather loose", and states $s(1)\ge23$. – Gerry Myerson Nov 3 '13 at 22:41
• @ Gerry Myerson. I sent Graham a set of 23 intervals which satisfy the conditions of the problem. This may explain his statement that s(1)>=23. With further calculation I found a set with 25 intervals. So s(1)>=25. – David S. Newman Nov 6 '13 at 0:03

## 1 Answer

The value of $s(1)$ is 31, because the maximal number of points that can be placed on the unit interval satisfying the given constraits is 32. While the computation of the exact value of $s(0)$ takes a few milliseconds (program written in C), the computation of the exact value of $s(1)$ takes about 2 days. So, it appears that knowledge of $s(2)$ will require much more computing effort.

Here goes one possible solution with 32 points ($[a,b[$ means an interval of the real line closed at $a$ and open at $b$): $$\begin{array}{rl|rl|rl|rl} [0/1, & 1/31[ & [11/29, & 8/21[ & [13/16, & 22/27[ & [4/19, & 3/14[ \\ [20/29, & 9/13[ & [9/16, & 13/23[ & [19/20, & 20/21[ & [11/24, & 6/13[ \\ [8/29, & 5/18[ & [1/8, & 4/31[ & [16/21, & 13/17[ & [28/31, & 19/21[ \\ [16/25, & 9/14[ & [13/25, & 12/23[ & [7/22, & 8/25[ & [5/29, & 4/23[ \\ [1/12, & 2/23[ & [17/20, & 23/27[ & [5/12, & 13/31[ & [3/5, & 17/28[ \\ [21/29, & 8/11[ & [30/31, & 1/1[ & [7/29, & 1/4[ & [1/24, & 1/23[ \\ [10/29, & 9/26[ & [15/31, & 1/2[ & [24/31, & 7/9[ & [27/31, & 8/9[ \\ [19/29, & 2/3[ & [4/29, & 5/31[ & [17/30, & 18/31[ & [13/31, & 14/31[. \end{array}$$

• Welcome To MathOverflow! Gerhard "Hasn't Seen You Here Before" Paseman, 2017.01.20. – Gerhard Paseman Jan 20 '17 at 19:40
• I submitted an edit to re-format your inline list (which I found very hard to read) as an array, formatted in 8 rows of 4 columns. I hope that you don't mind. – LSpice Jan 20 '17 at 19:42