[Math] Total distance traveled when visiting all rational numbers

rational numberssequences-and-series

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.

Best Answer

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.

Related Question