2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Could you quote Hugo Steinhaus? (It'd be easier to understand the problem). $\endgroup$ – Włodzimierz Holsztyński Nov 1 '13 at 7:28
  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Nov 3 '13 at 22:41
  • $\begingroup$ @ 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. $\endgroup$ – David S. Newman Nov 6 '13 at 0:03
5
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Welcome To MathOverflow! Gerhard "Hasn't Seen You Here Before" Paseman, 2017.01.20. $\endgroup$ – Gerhard Paseman Jan 20 '17 at 19:40
  • 1
    $\begingroup$ 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. $\endgroup$ – LSpice Jan 20 '17 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.