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

Let $\mathbb{N}=\{0,1,2,\ldots\}$. Does there exist a bijection $f\colon\mathbb{N}\to\mathbb{N}$ such that $f(0)=0$ and $|f(n)-f(n-1)|=n$ for all $n\geq1$?

The values $f(1)=1$, $f(2)=3$, and $f(3)=6$ are forced. After that, you might choose to continue with

$$\begin{array}{c|c}n&f(n)\\\hline0&0\\1&1\\2&3\\3&6\\4&2\end{array}\qquad\begin{array}{c|c}n&f(n)\\\hline5&7\\6&13\\7&20\\8&28\\9&37\end{array}\qquad\begin{array}{c|c}n&f(n)\\\hline10&27\\11&16\\12&4\\13&17\\14&31\end{array}$$

Here, after deceasing to $f(4)=2$, the next smallest remaining value was 4. I chose to continue to increase until there was a clear way down to 4 and back up.

As mentioned in the comments, the greedy algorithm where you decrease whenever you can is given by sequence A005132 in the OEIS. However, this sequence gets stuck at $f(20)=42$, $f(21)=63$, $f(22)=41$, $f(23)=18$ as there is no possible value for $f(24)$. Also, this greedy approach would take longer to get to the value $4$.

In general, if $k$ is the smallest number that you haven’t hit yet then the strategy of increasing until there is a clear way down to $k$ and a clear way back up seems to be a reasonable strategy. This is the strategy employed by the table above. Unfortunately, Symlic’s answer shows that this strategy doesn’t work (in fact, it will never hit the value 5). Therefore, a more sophisticated strategy is required.

If you instead consider $f\colon\mathbb{N}\to\mathbb{Z}$ then alternating between increasing and decreasing is a valid bijection. However, employing this technique in original situation will often lead to you getting stuck in coming back up.

Answer

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

Attribution
Source : Link , Question Author : Thomas Browning , Answer Author : Smylic

Leave a Comment