Total distance traveled when visiting all rational numbers

Question

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.

Answer 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.

Answer 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.

Answer 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$.

Answer 4

My intuition says no.

Let $a_{n_1} := 0, a_{n_q} := q \in \mathbb{N}$

Then $ q^2 = (a_{n_1} - a_{n_q})^2 \leq \sum_{n = 1}^{\max(n_1,n_q)} (a_n - a_{n+1})^2 $ By the triangle inequality.

We know that $n_q \to \infty$ as $q \to \infty$ (because $a$ is a bijection, and the rationals are unbounded)

Hence $\sum_{n = 1}^{\infty} (a_n - a_{n+1})^2$ diverges.

Answer 5

Think of it this way. What you need to make your sum convergent is to make $(a_n - a_{n+1})$ get infinitely close to, but not equal to 0 (otherwise it would not be a bijection). So we should try to eliminate as many options as we can:

Polynomials: Obviously, even-degreed ones can't work. Odd-degreed ones are our only option.

Non-polynomials Categories:

1. sin, cos, etc: disproved by bijection
2. polynomials divided by cases: we'll try this later
3. arrays: we'll try this later

So, for right now, I focused on odd polynomials. Grouping them into ones with positive degrees and negative degrees, I ruled out ones with positive degrees based on their common property of divergence.

Negative degrees look pretty interesting - so let's work with these - starting with $n^{-1}$, or more colloquially, $\frac{1}{x}$.

Theoretically, the limit as n approaches infinity of $(\frac{1}{n} - \frac{1}{n+1})$ is 0, but will never reach 0.

And bam, $\frac{1}{n}$ is your bijection. As a proof, let's replace infinity with rational numbers and test.

1. 0 - 0
2. 10 - 0.28961810696118045
3. 100 - 0.28986781017274627
4. 1000 - 0.28986813336411776
5. 10000 - 0.2898681336961168

We can additionally prove this is convergent by saying that if x is convergent, $x^2$ will be convergent. Therefore, since $(\frac{1}{n} - \frac{1}{n+1})$, then $(\frac{1}{n} - \frac{1}{n+1})^2$ is convergent, and its integral from 0 to infinity will also be convergent.

P.S., no clue why it converges at this exact point or if it has a deep mathematical meaning, and I just saw this and wanted to take a crack at it. Hopefully I didn't screw up and helped you.