Do rearrangements of $\mathbb{N}$ necessarily have fixed points with respect to placement distance?

Question

Let $f:\mathbb{N}\to\mathbb{N}$ be a bijection. Does there exist $\ n_1,n_2\in\mathbb{N},\ n_2>n_1, $ such that $\vert f(n_2)-f(n_1) \vert = n_2 - n_1\ ?$

I have tried coming up with counter-examples, but so far they all fail. But I'm not sure why they are failing.

Answer 1

This is a back-and-forth induction, with a correction from the previous version.

Let $D$ and $R$ denote the (current) domain and range as we build the function $f$. Both are empty at the start.

Step $1$. Chooses $f(1)=a$ where $a$ is arbitrary, then $D = \{1\}$ and $R = \{a\}$.

Step $2j$. Choose $m$ minimal not in $R$ so far. Choose $k$ not in $D$ so that $|d-k|$ and $|f(d)-m|$ are distinct for each $d$ in $D$ (can do since there are only finitely many such $d$ in $D$). Set $f(k)=m$, and add $k$ into $D$ and $m$ into $R$.

Step $2j+1$. Choose $k$ minimal not in $D$ so far. Choose $m$ not in $R$ so that $|m-f(d)|$ and $|k-d|$ are distinct for each $d$ in $D$ (can do since there are only finitely many such $d$ in $D$). Set $f(k)=m$ and add $k$ into $D$ and $m$ into $R$.

That defines the inductive construction of $f$. It's easy to check that $f$ is bijective on $N$ and since the value of $|f(n)-f(k)|$ is never equal to $|n-k|$ by construction, the desired condition on $f$ holds.

Since there are more than one choice (infinitely many, in fact) at each step, there're uncountably many infinite sequences of such choices, giving uncountably many such functions.

Answer 2

Partial answer:

One can interatively construct an injective map $f: \mathbb{N} \rightarrow \mathbb{N}$ such that we always have $|f(n_2)-f(n_1)| \neq n_2-n_1$. Just start with $f(1)=1$ and given the values of $f$ up to $f(k-1)$ define $f(k)$ to be the minimal natural number that makes $f$ injective for $1, .., k$ and satisfies your distance condition. This forbids only a finite number of values for $f(k)$ so there always exists such a minimum.

The interesting question is whether this map would be surjective or not. It seems like all natural numbers should end up in the image of $f$ eventually but I don't have a rigorous proof.

Answer 3

The greedy solution is to choose $f(1), f(2), f(3), \dots$ in order, and at every step to choose $f(n)$ to be the least natural number that does not create any problems so far. This produces the sequence $$ 1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, \dots $$ This is sequence A065188 in the OEIS; the "Greedy Queens" sequence. (The condition on $f$ is equivalent to asking us to place queens on the infinite chessboard $\mathbb N \times \mathbb N$ so that every row and column has a queen, and none of the queens attack each other; hence the name.)

A comment on the related sequence A269526 gives a proof that the greedily-constructed $f$ is a bijection; I will reproduce it here in a bit more detail. Suppose for the sake of contradiction that $m$ (for "missing") is the first value missing from the range of $f$.

For $i=1, \dots, m-1$, there is a value $f^{-1}(i)$ mapped to $i$ (by assumption), and this prevents $f^{-1}(i)+(m-i)$ from being equal to $m$. However, this type of constraint only happens finitely many times; we can choose $N$ larger than $f^{-1}(i)+(m-i)$ for any $i$. ($N$ is a capital letter because it's a big number.)

Here is the other way that the value $m$ can be blocked: whenever $f(x)=y$ for $y>m$, this means $f(x+y-m)$ cannot be $m$. This is the only time that $f(x)=y$ prevents a later value of $f$ from being $m$. So lots of values of $f$ must somehow be "dedicated" to blocking the value $m$; this will be a problem.

If $f(N), f(N+1), \dots, f(10N)$ are all blocked in this way, that means that at least $9N$ values of $f$ up to this point are used for blocking them: we have $f(x)=y$ with $x+y-m \le 10N$ for at least $9N$ values of $x$ less than $10N$. Equivalently, for at least $9N$ values of $x$ less than $10N$, $f(x) \le 10N+m-x$.

Now take a $10N$ by $10N$ chessboard, and whenever $m < f(x) \le 10N + m-x$, place a queen in row $x$ and column $f(x)-m+1$. We have placed at least $9N$ non-attacking queens on the chessboard... what's more, each of them is placed on or below the main antidiagonal!

However, yet another OEIS sequence, A274616, counts the maximum number of non-attacking queens that can be placed on such a triangular board with side $n$. That number is $\frac23 n$ rounded to the nearest integer: it is certainly not $\frac9{10}n$ for any $n$ as big as $10N$. Therefore no function $f$ that satisfies our other constraints can keep blocking $m$ for this long: eventually the value $m$ will also be attained.