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 $.
No comments:
Post a Comment