Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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: – Martin Sleziak Jan 6 '12 at 11:56
up vote 2 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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