Bijection $f\colon\mathbb{N}\to\mathbb{N}$ with $f(0)=0$ and $|f(n)-f(n-1)|=n$

Solution 1:

The good news is that your function will never get stuck. The bad news is that the reason quite easy: your function will never have value 5. Let see how to get it.

Suppose there are $k$ and $\ell$ such that $f(\ell) = 5$, and $f(n) = f(n - 1) + n$ for all $13 \le n \le k$, and $f(n) = f(n - 1) - n$ for all $k < n \le l$. Then $$f(k) = 4 + \sum_{n = 13}^k n = 4 + \frac{k(k + 1)}2 - 78 = \frac{k(k + 1)}2 - 74$$ and $$5 = f(\ell) = f(k) - \sum_{n = k + 1}^{\ell} n = \frac{k(k + 1)}2 - 74 - \frac{\ell(\ell + 1)}2 + \frac{k(k + 1)}2,$$ i. e., $$k(k + 1) = 79 + \frac{\ell(\ell + 1)}2.$$ It is easy to see that $\frac{\ell(\ell + 1)}2 \bmod 9 \in \{\,0, 1, 3, 6\,\}$ and $k(k + 1) \bmod 9 \in \{\,0, 2, 3, 6\,\}$. Since $79 \bmod 9 = 7$ we get a contradiction, which means that there are no such $k$ and $\ell$.

Solution 2:

Such a bijection exists.

It is convenient to assume that we are looking for an infinite jump sequence on $\mathbb N$ starting from $0$, never returning to a previous position and ultimately filling all $\mathbb N$. The distance of the $n$th jump is restricted to be $n$, we can choose only its direction. So our task is to find the appropriate sequence $\mathcal D$ of jump directions like $\mathcal D=(+\!+\!+\!-\!+\dots)$, where $+$ means jumping $n$ positions forward and $-$ means jumping $n$ positions backward, $n$ is the number of the sign in the sequence. The term state below stands for a pair $(n, m)$, where $n \in \mathbb N$ is time and $m \in \mathbb N$ is position (it results from adding $\pm n$ to a previous position when $n>0$ and corresponds to $f(n)$ in the original statement). A state $(n, m)$ is called safe if $m$ is the largest position up to the time $n$ (i.e. $f(t)<f(n)$ for all $t<n$).

The solution relies on two jump patterns. Lower index $k \in \mathbb N$ after some subpattern $\mathcal P$ (which may be a single sign or a bracketed group) below means that $\mathcal P$ must be repeated $k$ times.

Saturator

Pattern: $\mathcal S_k = +_2(-+)_k$

Prerequisite: safe state $(n, m)$.

Parameter: $k, \; 0 \le k \le n$.

Result: safe state $(n+2k+2, m+2n+k+3)$.

Comment: the table below summarizes state change during the pattern realization. Position never goes into the "unsafe" area below $m$.

$$\begin{array}{|c|ccc|} \hline \text{Time (from ... to)} && \;\text{Position}\\ n+\bullet & m+\bullet & m+n+\bullet & m+2n+\bullet\\ \hline 0 \,\dots\, 2 & \color{lime}{0} & 1 & 3\\ 2i+3 \,\dots\, 2i+4 && -i & i+4\\ \hline \text{min pos} & 0 & -k+1 &3\\ \text{max pos} & 0 & 1 & \color{lime}{k+3}\\ \hline \end{array}$$

Positions are grouped in columns according to $n$-driven bands. For brevity, common summands like $n + \bullet$ are put into header, they must be added to what's written beneath. The line containing $i$, where $0 \le i < k$, describes a cycle repeated $k$ times. As $k \le n$, the bands never intersect. This is also reflected in the last two rows. For example, the minimal position in the second band is $m+n-k+1$, which is greater than the sole position $m$ in the first band.

Particular case: $k=n$. This Saturator, called the complete Saturator and denoted simply by $\mathcal S$, will be used most often. It transforms the safe state $(n, m)$ to the safe state $(3n+2, m+3n+3)$. Looking at the ratio $t = \frac m {n+1}$ for each state, it transforms $t$ to $\frac {m+3n+3} {3n+3}=1 + \frac t 3$. The map $t \to 1 + \frac t 3$ has one fixed point: $t_0 = \frac 3 2$, so starting from any safe state and using $\mathcal S$ an appropriate number of times it is possible to get $t$ as close as needed to $\frac 3 2$.

Fencer

Pattern: $\mathcal F_k = +(+_3\!-_3)_k\!+_5\!-\!+\!-_6+_6$

Prerequisites: safe state $(n, m)$ and previously unattended position $a = m - (15k+47)$.

Parameter: $k$ (fixed, determined by $a$), $0 \le k < \frac {n-33} 9$.

Result: new safe state, $a$ is attended.

Comment: the table below summarizes state change during the pattern realization. The only position inside "unsafe" area is $a$, which is indicated by the red color.

$$\begin{array}{|c|ccccccc|} \hline \text{Time (from ... to)} &&&& \;\text{Position}\\ n+\bullet & m\!+\!\bullet & m\!+\!n\!+\!\bullet & m\!+\!2n\!+\!\bullet & m\!+\!3n\!+\!\bullet & m\!+\!4n\!+\!\bullet & m\!+\!5n\!+\!\bullet & m\!+\!6n\!+\!\bullet\\ \hline 0 \,\dots\, 1 & \color{lime}{0} & 1\\ 6i+2 \,\dots\, 6i+4 &&& -3i+3 & 3i+6 & 9i+10\\ 6i+5 \,\dots\, 6i+7 && -9i-8 & -3i-1 & 3i+5\\ 6k+2 \,\dots\, 6k+6 &&& -3k+3 & 3k+6 & 9k+10 & 15k+15 & 21k+21\\ 6k+7 \,\dots\, 6k+8 &&&&&& 15k+14 &21k+22\\ 6k+9 \,\dots\, 6k+14 & \color{red}{-15k-47} & -9k-33 & -3k-20 & 3k-8 & 9k+3 & 15k+13\\ 6k+15 \,\dots\, 6k+20 && -9k-32 & -3k-16 & 3k+1 & 9k+19 & 15k+38 & \color{lime}{21k+58}\\ \hline \text{min pos} & -15k-47 & -9k-33 & -3k-20 & \min(5, 3k\!-\!8) & \min (10, 9k\!+\!3) & 15k+13 & 21k+21\\ \text{max pos} & 0 & 1 & 3 & 3k+6 & 9k+19 & 15k+38 & 21k+58\\ \hline \end{array}$$

Two lines containing $i$, where $0 \le i < k$, describe a cycle repeated $k$ times. As $9k+33 < n$, two first bands don't intersect. The same is true for other band pairs. For example, $3k+21<9k+33<n$, thus the second and the third bands don't intersect.

Sequence construction

We are starting from the safe state $(0, 0)$ and empty $\mathcal D$. The latter will be composed of $\mathcal S_k$ and $\mathcal F_k$ only. The strategy is to use the Fencer pattern repeatedly making "lunges" at the lowest unattended positions. The main purpose of the Saturator pattern is to provide prerequisites for the Fencer. If there is no unattended position below the current one (as it is at the beginning), $\mathcal S$ simply executes until it arrives. Then, after fixing minimal unattended position $a$, the Saturator must increase $m$ such that $m \equiv a+2 \pmod {15}$ and $0 \le \frac {m-a-47} {15} < \frac {n-33} 9 \iff a+47 \le m < \frac 5 3 n + a - 8$. The inequality $a+47 \le m$ can be easily achieved since the Saturator always increases $m$. After that apply the complete Saturator one or more times until the ratio $t=\frac {m'}{n'+1}$ for the next expected pair $(n',m')=(3n_{i-1}\!+\!2, m\!+\!3n_{i-1}\!+\!3)$ becomes lower than $\frac {5 / 3 \, (n'-28) + a - 8} {n'+1}$. This will happen some time because, as noted above, $t_i \to \frac 3 2$, $n_i \to +\infty$ and $\frac 3 2 < \frac 5 3$. To make the Fencer available, apply "almost complete" Saturator $\mathcal S_k$ with $k=n_{i-1}-d$ instead of $k=n_{i-1}$, where $d$ is chosen between $0$ and $14$ such that $m'-d \equiv a+2 \pmod {15}$. Then $n_i=n'-2d \ge n'-28$, $m_i=m'-d$, thus $m_i \le m'<\frac {5 / 3 \, (n'-28) + a - 8} {n'+1} (n'+1) \le \frac 5 3 n_i + a - 8$ and all prerequisites for the Fencer are fulfilled. As the lowest unattended position is greater than $n$ after the $n$th application of the Fencer, any position ultimately will be attended.