1

Is there a function $f:\mathbb N \to \mathbb N$ such that $\forall n \in \mathbb N, f(f(n))=n+2015$ ?

Here's what I've done:

Assuming such a function exists,

$f(f(f(n)))=f(\color{red}{f(f(n))})=f(n+2015)=\color{red}{f(f(}f(n)\color{red}{))}=f(n)+2015$.

Hence $\forall n, f(n+2015)=f(n)+2015$.

A simple induction yields $\forall n,\forall k, f(n+2015k)=f(n)+2015k$.

This means that $f(n) \operatorname{mod}2015$ only depends on $n \operatorname{mod}2015$.

What then ? I can't reach a contradiction from here.

Gabriel Romon
  • 35,428
  • 5
  • 65
  • 157

1 Answers1

3

Suppose such a function exists. Then define the function $$g\colon \{1,\dots,2015\}\to \{1,\dots,2015\},\quad g(n)=f(n)\bmod{2015}.$$ Then $g$ is an involution of $\{1,\dots,2015\}$. Since there are an odd number of elements, it follows that $g$ has a fixed point, say $k$. Then $f(k)=k+2015j$ for some $j$, whereupon $f(f(k))=k+2015\cdot 2j\not=k+2015$, contradiction.

user26857
  • 52,094
pre-kidney
  • 30,223