31
$\begingroup$

Choose a point anywhere in the unit interval $[0, 1]$. Now choose a second point from the same interval so that there is one point in each half, $[0, \frac12]$ and $[\frac12, 1]$. Now choose a third point so that there is one point in each third of the interval, and so on. How long can you choose points like this?

In other words, what is the largest $n$ so that there exists a (finite) sequence $(a_i)_{i=1}^n$ so that for all $k$, among the first $k$ points $(a_i)_{i=1}^k$, there is at least one in each interval $[0, \frac1k], [\frac1k, \frac2k], \ldots, [\frac{k-1}k,1]$?

My question

Is there a slick proof that $n$ is bounded? (Note that by compactness, the existence of such a sequence for all $n$ is equivalent to the existence of an infinite sequence with the same property.)

Backstory

I was recently re-reading old columns of Martin Gardner's, and he describes this problem in "Bulgarian solitaire and other seemingly endless tasks". (Original column 1983, available in his collections "The last recreations: ..." and "The colossal book of mathematics".) He says that the problem first appeared in "One hundred problems in elementary mathematics" by Hugo Steinhaus. There, he shows that there is a sequence of length 14, but there is none of length 75. The first published proof of the longest sequence, which has length 17, was by Elwyn Berlekamp and Ron Graham in their paper "Irregularities in the distributions of finite sequences" in the Journal of Number Theory. This was followed by a shorter proof by Mieczysƚaw Warmus in "A supplementary note on the irregularities of distributions" in the same journal.

Now, these proofs mostly use case analysis to some degree or other. They are of varying complexities, oddly with Warmus's proof of the optimal $n$ being the shortest. It's also not too hard to write a computer check oneself that finds the optimal $n$. However, I feel that because of the elegant nature of the problem, there should be some "nice" proof -- not of optimality, but simply that such a sequence can't continue forever. Can anyone find one?

Technical note: The problem is usually stated with half-open intervals. I made them closed so that compactness worked. (Edit: The possibility that this changes the answer did occur to me. I assume it doesn't, and I'll check by computer soon. I am fine with answers for any kind of intervals -- open, closed, half-open.)

$\endgroup$
7
  • 1
    $\begingroup$ Is it obvious that the problem isn't made harder (or false!) by changing half-open intervals to closed ones? You could have points on the boundaries. $\endgroup$ Mar 31, 2010 at 0:16
  • 1
    $\begingroup$ An interesting related problem is to choose an infinite sequence x_1, x_2, ... of points on a circle of circumference 1 so that the lengths of the gaps formed by x_1, ..., x_n is as "uniform as possible" as n goes to infinity. There are different interpretations of "uniform as possible." Some were considered by DeBruijn and Erdos in a 1949 paper. More details can be found at db.stanford.edu/pub/cstr/reports/cs/tr/77/637/CS-TR-77-637.pdf. $\endgroup$ Mar 31, 2010 at 0:59
  • $\begingroup$ What proof did Steinhaus give that there are no such sequences of length 75? $\endgroup$ Mar 31, 2010 at 2:48
  • $\begingroup$ @Douglas: Steinhaus (attributing the proof to Schinzel) analyzes what happens between 7/35 and 10/35. He then derives that something happens before the 75th term. His proof isn't case analysis, but does run a few pages. PS. The book is on Google Books. $\endgroup$
    – aorq
    Mar 31, 2010 at 7:02
  • $\begingroup$ @A. Rex: the four colour theorem and Fermat's Last Theorem are very concise and simple to state. As far as we know there are no slick proofs of them. There are also theorems in logic of the form "for any N, there is a theorem whose shortest proof is N times the length of its statement". What I'm saying is that it's not inconcievable that there is no slick proof. Maybe you're well aware of this but it seemed worth flagging, in the sense that everyone is talking about interesting things but my comment actually includes an answer (or at least my opinion on the answer) to the question you asked! $\endgroup$ Mar 31, 2010 at 9:27

2 Answers 2

10
$\begingroup$

The proof given by Steinhaus (following A. Schinzel) is slick indeed. I'll paraphrase what he does:

At step number $n$, the interval (0,1) is divided into $n$ intervals $I_0^{(n)}=(0,\frac{1}{n}), \ldots, I_{n-1}^{(n)}=(\frac{n-1}{n},1)$. Then $\lfloor nP \rfloor$ gives you the number of the interval to which a point $P$ in the sequence belongs in the $n.$ step.

He proceeds by proving the following claim:

If $P_1 \in (\frac{7}{35},\frac{8}{35})$ and $P_2 \in (\frac{9}{35}, \frac{10}{35})$, then there is some $n \in \mathbb{N}$ big enough such that $\lfloor (n-1)P_1 \rfloor < \lfloor nP_1 \rfloor$ , but $\lfloor (n-1)P_2 \rfloor = \lfloor nP_2 \rfloor$.

Let's see how this claim implies that there is no infinite such sequence. Eventually, in your sequence at the $k.$ step there will be two points $P_1,P_2$ as in the claim. Let $n$ be as in the claim, in particular $n>k$.

Let $k_1:=\lfloor (n-1)P_1\rfloor$ and $k_2:=\lfloor (n-1)P_2\rfloor$. Then $P_i$ belongs to the $k_i$. interval in the $(n-1).$st step and there are $k_2-k_1-1$ points of $a_1, \ldots, a_{n-1}$ of the sequence in-between. But in the $n.$ step, $P_1$ will move to the $k_1+1$.st interval, while $P_2$ will remain in the $k_2$.st interval, and so there will be a ''collision'' of the in-between points.

$\endgroup$
1
  • 1
    $\begingroup$ I agree that claim is nice. However, it takes him a couple pages to prove it, during which he has random fractions like 5/7 and 8/35 floating around, interspersed with floors and ceilings. Is there some intuitive way to see that (some version) of that claim will be true? $\endgroup$
    – aorq
    Mar 31, 2010 at 17:07
4
$\begingroup$

The non-existence of an infinite sequence falls out of a result of van Aardenne-Ehrenfest on discrepancy of sequences. I do not know whether there is a slick proof of her theorem. The result appeared as T van Aardenne-Ehrenfest, Proof of the impossibility of a just distribution of an infinite sequence over an interval, Proc Kon Ned Akad Wetensch 48 (1945) 3-8.

$\endgroup$
2
  • $\begingroup$ Yes, this is in the first paragraph of the paper of Berlekamp and Graham. $\endgroup$
    – aorq
    Mar 31, 2010 at 3:13
  • $\begingroup$ So, do you know whether the TvA-E proof is slick? $\endgroup$ Mar 31, 2010 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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