# Bijection between the positive integers with a restriction

How can I find a function (or more) $f(n)$, defined for the positive integers $n$, and which outputs every positive integer exactly once (and nothing else) and which satisfy i) For every integer $k$ in $\mathbb{Z}$, $f(n)=n+k$ has only finitely many solutions in $n$?

-
One approach: there is a bijection f such that for all positive integers n, either f(n)=2n or f(n)=n/2. – Colin McQuillan Jan 6 '12 at 11:49
I guess elementary-set-theory or functions would be more suitable tags; if you think than number theory is relevant, then elementary-number-theory might be better. You can have a look how other questions on bijections are tagged: math.stackexchange.com/search?q=bijection+set math.stackexchange.com/search?q=bijection – Martin Sleziak Jan 6 '12 at 11:56

Break $\mathbb{Z}^+$ into consecutive blocks $B_n$ of integers in such a way that $B_n$ contains $2n$ consecutive integers: $B_1=\{1,2\}$, $B_2=\{3,4,5,6\}$, $B_3=\{7,8,9,10,11,12\}$, and so on. Permute $B_n$ by adding $n$ to each of the first $n$ members and subtracting $n$ from each of the last $n$:

$$\begin{array}{r} &&B_1&|&&&&B_2&|&&&&&&B_3\\ \hline n:&1&2&|&3&4&5&6&|&7&8&9&10&11&12\\ \hline f(n):&2&1&|&5&6&3&4&|&10&11&12&7&8&9\\ \hline f(n)-n:&1&-1&|&2&2&-2&-2&|&3&3&3&-3&-3&-3 \end{array}$$

Then for each $k\in\mathbb{Z}$ the equation $f(n)=n+k$ has $|k|$ solutions.

If you want to specify explicitly what integers belong to $B_n$, note that the last member of $B_n$ is preceded by $$\sum_{k=1}^{n-1}2k+(2n-1)=2\sum_{k=1}^nk-1=n(n+1)-1$$ positive integers and is therefore equal to $n(n+1)$. Thus, $$B_n=\{k\in\mathbb{Z}^+:(n-1)n<k\le n(n+1)\}\;.$$ This allows an explicit (and not too messy) description of $f$:

$$f(k)=\begin{cases} k+n,&\text{if }n^2-n<k\le n^2\\ k-n,&\text{if }n^2<n\le n^2+n\;. \end{cases}$$

-

It is possible to find a clever function satisfying your conditions, but this is also the kind of question where you can find a "Just-do-it" proof with a messy function that works "by construction". For example notice that it is fairly easy, for fixed k, to find a permutation f of an interval {N,N+1,...,N+D} such that $|f(x)-x|$ is always at least k, as long as $D$ is large enough relative to $k$. In particular if $D\geq 2k$ take $f$ to be the function that adds $k$ and wraps around. So we can split up the integers into intervals of length 2,4,6,... and apply such a permutation to each interval. It might seem more difficult to check this kind of construction than a simple clever function, but this kind of proof is, I think, the right way (certainly a good way) to approach this kind of question.

Edit: I'm a bit unhappy with the above argument, and I think the following is more in the spirit of "just do it". First show that for any k and any infinite subset S of the integers we can pick a finite set S' including min(S) and a permutation f of S' such that $|f(x)-x|\geq k$ for all $x\in S'$. By repeating this for larger and larger $k$, we partition the integers into sets such that for each $k$, there are only a finite number of solutions to $|f(x)-x|< k$.

-