Total distance traveled when visiting all rational numbers

My students found an old problem given in my school in 2007 (probably from a Honor Calculus class) and had been trying to solve for some time. Here is the problem:

Prove or disprove: there exists a bijection $a$ from $\mathbb N$ onto $\mathbb Q$ such that $\sum_{n=1}^\infty (a_n-a_{n+1})^2$ is convergent. (With $a_n=a(n)$)

I have to confess that I am clueless on the method to deal with this problem. My intuition is that the sum represents the square of the distance traveled when visiting all rational numbers, but there is so many rationals that the sum should be infinite. On the other hand, the density of Q means that I can travel the distance between consecutive rationals of my travel can be arbitrarily small, so I am confused...

The only thing we could prove is that $\sum(a_n-a_{n+1})$ is divergent (otherwise, $\{a_n\}$ would be bounded, a contradiction).

Any clue is welcome.

Solution 1:

My intuition says yes (there exists). Choose $a$ so that $a_n-a_{n+1}\leq \frac{1}{n}$; since $\sum_n\frac{1}{n^2}$ converges, if you can indeed choose one such $a$ you should be fine. Now, because $\sum_n\frac{1}{n}$ diverges, you could in principle take steps that are roughly that length and still get to 'cover all of $\mathbb{Q}$'. I might try and make this more precise.

EDIT: Making it precise.

Choose any bijection $f:\mathbb{N}\longrightarrow \mathbb{Q}$. We will obtain $a$ from $f$ inductively as follows.

First, let $a(1)=f(1)$. Now, if $|f(2)-a(1)|\leq \frac12$, we set $a(2)=f(2)$. Otherwise, we set $a(2)=a(1)\pm\frac12$, whichever sign brings $a(2)$ closer to $f(2)$. Then, if |$f(2)-a(2)|\leq \frac13$, we set $a(3)=f(2)$; otherwise we set $a(3)=a(2)\pm \frac13$, whichever signs brings $a(3)$ closer to $f(2)$. We proceed in this manner until we each $f(2)$, then we move onto $f(3)$, and so on.

Observations:

• Because $\sum_n\frac{1}{n}$ diverges, we will always reach the next $f(n)$ in finite time.
• Of course, since $f$ is a bijection, our intermediate $a(k)$'s may step onto some of the $f(n)$'s prematurely. If, after reaching some $f(n)$, $f(n+1)$ has already been previously assigned to some $a(k)$, we simply skip $f(n+1)$ and proceed to $f(n+2)$. Notice that, at any point in the induction, $a$ will be defined at a finite number of points so there may be at most a finite number of skips, and the process can always continue.
• Finally, if when defining $a(k+1) = a(k) \pm \tfrac1k$ the RHS is already taken, simply choose another rational $r$ near $a(k) \pm \tfrac1k$, say $\left|r-\left(a(k) \pm \tfrac1k\right)\right|\leq\tfrac{1}{2k}$, and put $a(k+1)=r$.

These observations guarantee that this inductive process can always continue and will eventually reach every rational. It uses the axiom of choice near the end, and I believe there's a way not to use it: look for

\begin{align} &a(k) \pm \tfrac1k\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\mp\tfrac{1}{8k}\\ &\dots \end{align}

until you find one that's not yet been used. But honestly I'm not too worried about it.

Solution 2:

Here's an idea (it'll take some work to flesh it out into a proof, but you asked for a clue, so...):

At some point I need to get from, say, $0$ to $1$ - I have to hit one of them, and then the other at some later time. Now, this looks like distance $1$, which is fine - IF I don't have to do steps like it very often. But I also have to do $1$ to $2$, $2$ to $3$, and so on; so I need to make it smaller. But $0, \frac{1}{2}, 1$ only has cumulative distance-squared equal to $\frac{1}{2}$. $0, \frac{1}{4}, \frac{1}{2}, \frac{3}{4}, 1$ has cumulative distance-squared of only $\frac{1}{4}$.

The cool thing is that I can do this with any interval I like. So imagine taking any enumeration of $\mathbb{Q}$ you like and inserting elements in between to "shrink" the steps involved so that each successive step of the original enumeration has smaller and smaller cumulative distance-squared in the new one - say, shrinking like $2^{-n}$.

This isn't complete - I've been very vague about lots of stuff, and I haven't said how to deal with the fact that the enumeration you end up with (at least the one I'm visualizing) visits most of the rationals many times; but you might be able to fill in the gaps.

Solution 3:

I will expand my comment into an answer (though still not a formal proof).

Lemma: Given rationals $a < b$, $\epsilon > 0$, and any finite set $S$, there exist rationals $k_1,\ldots,k_n \not\in S$ such that $$(k_1 - a)^2 + \sum_i (k_{i+1} - k_i)^2 + (b - k_n)^2 < \varepsilon.$$

Sketch of proof: Note that by inserting a single rational $c$ in the interval $\left[\frac{3a+b}{4},\frac{a+3b}{4}\right]$, we have $$(b-a)^2 \leq \frac{5}{8}\left((c-a)^2 + (b-c)^2\right).$$ We can always do this, because that interval contains infinitely many rationals, and so in particular it contains a rational that is not in $S$. Keep doing this until the sum of squared distances is less than $\varepsilon$.

Now let $(a_n)$ be any enumeration of the rationals. Form a new enumeration of the rationals as follows: Let $b_{n_1} = b_1 = a_1$. Insert as many rationals $b_2, \ldots, b_{n_2-1}$ as necessary so that when finally $b_{n_2} = a_2$, we have $$\sum_{i=1}^{n_2-1} (b_{i+1} - b_i)^2 < 1/2.$$

Let $b_{n_3}$ be the next unvisited member of $(a_n)$. Continue like this, inserting rationals $b_{n_2+1},\ldots,b_{n_3-1}$ so that $$\sum_{i=n_2}^{n_3-1} (b_{i+1} - b_i)^2 < 1/4.$$

At each step, the forbidden set $S$ is simply the sequence $(b_n)$ that has been defined so far. We take finitely many steps to reach $a_1$, and then $a_2$, and so on, so $(b_n)$ is also an enumeration of the rationals. Moreover, $\sum_i (b_{i+1} - b_i)^2 < 1$.