39
$\begingroup$

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.

However, this strategy requires proving that there will eventually be a clear path down where you won't get stuck coming back up.

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.

$\endgroup$
  • 5
    $\begingroup$ related sequence $\endgroup$ – lulu Jun 21 '18 at 20:47
  • $\begingroup$ Why did you set $f(8)=20$? $12$ was available... is there a clear (automatable) rule which you followed? The sequence I linked to above follows the rule "go down if the slot is available, otherwise go up." Alas, the sequence you get that way is neither injective nor surjective (though it sure looks surjective). $\endgroup$ – lulu Jun 21 '18 at 20:56
  • $\begingroup$ If you set $f(8)=12$ then it takes more time to hit $4$. You could think of the rule as: Continue to increase until it is possible to "go down until you hit the target and then go up until you are in the clear". $\endgroup$ – Thomas Browning Jun 21 '18 at 20:57
  • 1
    $\begingroup$ But then you are stuck as you would have to go back up to $10$. $\endgroup$ – Thomas Browning Jun 23 '18 at 21:28
  • 2
    $\begingroup$ The composition $g\circ f$ probably will not satisfy the condition $|g(f(n))-g(f(n-1))|=n$ for all $n\geq1$. $\endgroup$ – Thomas Browning Jun 26 '18 at 5:01
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very nice! This shows that a more sophisticated choice of $f$ is required. $\endgroup$ – Thomas Browning Jun 27 '18 at 1:54
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I will have to take some time to go through the details but this looks very promising. $\endgroup$ – Thomas Browning Jul 1 '18 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.