## Wednesday, January 11, 2006

### No Way! Topic: Algebra/NT. Level: Olympiad.

Problem: (1987 IMO - #4) Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for all $n$.

Solution: Suppose such a function does exist.

Note that $f(f(n)) = n+1987$, so $f(n+1987) = f(f(f(n))) = f(n)+1987$.

So given two integers $k_1 > k_2$, we have $k_1 \equiv k_2 \pmod{1987} \Rightarrow k_1 = k_2+1987a$ for some positive integral $a$. $f(k_1) \equiv f(k_1-1987) \equiv f(k_1-2\cdot1987) \equiv \cdots \equiv f(k_1-a\cdot1987) = f(k_2) \pmod{1987}$.

Also note that $f$ is one-to-one. That is, given $x,y$ such that $f(x) = f(y)$, we have $f(f(x)) = f(f(y)) \Rightarrow x+1987 = y+1987 \Rightarrow x = y$.

Consider $g(n) \equiv f(n) \pmod{1987}$ where $0 \le g(x) < 1986$, $0 \le n < 1986$. If we have $x \neq y$ such that $g(x) = g(y)$, we have $f(x) \equiv f(y) \Rightarrow x \equiv y$, but since the domain of $g$ is limited, we have a contradiction. Hence $g$ takes on all residues $\pmod{1987}$.

Let $f(n) = m$ where $n$ and $m$ have different residues $\pmod{1987}$. Then we have $f(m) = f(f(n)) = n+1987 \equiv n \pmod{1987}$. So $f(n) \equiv m, f(m) \equiv n \pmod{1987}$. Pairing up all values this way, we have an odd number (at least one) of remaining $n$ such that $f(n) \equiv n \pmod{1987}$.

However, if $f(n) \equiv n \pmod{1987}$, we have $f(n) = n+1987t$ for some $t \ge 0$. Then $f(n+1987t) = f(n+1987(t-1)) +1987 = \cdots = f(n)+1987t = n+1987(t+1)$, but $f(f(n+1987t)) = n+1987(t+1)$ as well, so $f(n+1987t) = n+1987t < n+1987(t+1)$, which clearly gives a contradiction.

Therefore no such functions $f$ exist. QED.

--------------------

Practice Problem: Find all positive integrs $k$ such that there exists a function $f$ from the set of non-negative integers into itself such that $f(f(n)) = n+k$.