Difference between revisions of "1987 IMO Problems/Problem 4"

Revision as of 11:44, 21 January 2024

Problem

Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n)) = n + 1987$ for every $n$ .

Solution 1

We prove that if $f(f(n)) = n + k$ for all $n$ , where $k$ is a fixed positive integer, then $k$ must be even. If $k = 2h$ , then we may take $f(n) = n + h$ .

Suppose $f(m) = n$ with $m \equiv n \mod k$ . Then by an easy induction on $r$ we find $f(m + kr) = n + kr$ , $f(n + kr) = m + k(r+1)$ . We show this leads to a contradiction. Suppose $m < n$ , so $n = m + ks$ for some $s > 0$ . Then $f(n) = f(m + ks) = n + ks$ . But $f(n) = m + k$ , so $m = n + k(s - 1) \ge n$ . Contradiction. So we must have $m \ge n$ , so $m = n + ks$ for some $s \ge 0$ . But now $f(m + k) = f(n + k(s+1)) = m + k(s + 2)$ . But $f(m + k) = n + k$ , so $n = m + k(s + 1) > n$ . Contradiction.

So if $f(m) = n$ , then $m$ and $n$ have different residues $\pmod k$ . Suppose they have $r_1$ and $r_2$ respectively. Then the same induction shows that all sufficiently large $s \equiv r_1 \pmod k$ have $f(s) \equiv r_2 \pmod k$ , and that all sufficiently large $s \equiv r_2 \pmod k$ have $f(s) \equiv r_1 \pmod k$ . Hence if $m$ has a different residue $r \mod k$ , then $f(m)$ cannot have residue $r_1$ or $r_2$ . For if $f(m)$ had residue $r_1$ , then the same argument would show that all sufficiently large numbers with residue $r_1$ had $f(m) \equiv r \pmod k$ . Thus the residues form pairs, so that if a number is congruent to a particular residue, then $f$ of the number is congruent to the pair of the residue. But this is impossible for $k$ odd.

Solution 2

Solution by Sawa Pavlov:

Let $\mathbb{N}$ be the set of non-negative integers. Put $A = \mathbb{N} - f(\mathbb{N})$ (the set of all $n$ such that we cannot find $m$ with $f(m) = n$ ). Put $B = f(A)$ .

Note that $f$ is injective because if $f(n) = f(m)$ , then $f(f(n)) = f(f(m))$ so $m = n$ . We claim that $B = f(\mathbb{N}) - f(f(\mathbb{N}))$ . Obviously $B$ is a subset of $f(\mathbb{N})$ and if $k$ belongs to $B$ , then it does not belong to $f(f(\mathbb{N}))$ since $f$ is injective. Similarly, a member of $f(f(\mathbb{N}))$ cannot belong to $B$ .

Clearly $A$ and $B$ are disjoint. They have union $\mathbb{N} - f(f(\mathbb{N}))$ which is $\{0, 1, 2, \ldots , 1986\}$ . But since $f$ is injective they have the same number of elements, which is impossible since $\{0, 1, \ldots , 1986\}$ has an odd number of elements.

Solution 3

Consider the function $g: \mathbb{Z}_{1987} \rightarrow \mathbb{Z}_{1987}$ defined by $g(x) = f(x\; {\rm mod }\; 1987) \;{\rm mod }\; 1987$ . Notice that we have $f(k) + 1987 = f(f(f(k))) = f(k + 1987)$ , so that $f(x) = f(y) \;{\rm mod }\; 1987$ whenever $x = y \;{\rm mod }\; 1987$ , and hence $g$ is well defined.

Now, we observe that $g$ satisfies the identity $g(g(x)) = x$ , for $x \in Z_{1987}$ . Thus, $g$ is an invertible function on a finite set of odd size, and hence must have a fixed point, say $a \in \mathbb{Z}_{1987}$ . Identifying $a$ with its canonical representative in $\mathbb{Z}$ , we therefore get $f(a) = a + 1987k$ for some non-negative integer $k$ .

However, we then have $f(f(a)) = a + 1987$ , while $f(f(a)) = f(a + 1987k) = 1987k + f(a) = 2\cdot1987k + a$ (where we use the identity $f(x + 1987) = f(x) + 1987$ derived above, along with $f(a) = f(a) + 1987$ . However, these two equations imply that $k = \dfrac{1}{2}$ , which is a contradiction since $k$ is an integer. Thus, such an $f$ cannot exist.

Note: The main step in the proof above is that the function $g$ can be shown to have a fixed point. This step works even if 1987 is replaced with any other odd number larger than 1. However, for any even number $c$ , $f(x) = x + \dfrac{c}{2}$ satisfies the condition $f(f(x)) = x + c$ .

--Mahamaya 21:15, 21 May 2012 (EDT)

Solution 4

Suppose $f$ were such a function. Notice that it would be injective: if $f(a) = f(b)$ , then $f(f(a)) = f(f(b))$ , so $a + 1987 = b + 1987$ and therefore $a = b$ .

Because $f \circ f$ is linear, it satisfies the following equation for all non-negative integers $a, b, c, d$ such that $a \neq b$ and $c \neq d$ :

$\frac{f(f(b)) - f(f(a))}{f(b) - f(a)} = \frac{f(f(d)) - f(f(c))}{f(c) - f(d)}.$

(Injectivity guarantees the denominators are non-zero.) But $f(f(b)) - f(f(a)) = b - a$ and $f(f(d)) - f(f(c)) = d - c$ , so

$\frac{b - a}{f(b) - f(a)} = \frac{d - c}{f(d) - f(c)},$

and therefore

$\frac{f(b) - f(a)}{b - a} = \frac{f(d) - f(c)}{d - c}.$

Thus $f$ itself is linear, so there exist non-negative integers $m, b$ such that $f(x) = mx + b$ . It follows that

$\begin{align*} f(f(x)) &= m(mx + b) + b \\ &= m^2x + b(m + 1). \end{align*}$

So $m^2 x + b(m + 1) = x + 1987$ for all non-negative integers $x$ . This is only possible if the coefficients match. So $m^2 = 1$ , and thus $m = 1$ . Likewise $b(m + 1) = 1987$ , so $b = 1987/2$ . This contradicts the fact that $b$ is an integer.

1987 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions

@@ Line 29: / Line 29: @@
 --[[User:Mahamaya|<font color="#FF 69 B4">Maha</font><font color="#FF00FF">maya</font>]] 21:15, 21 May 2012 (EDT)
+==Solution 4 ==
+Suppose <math>f</math> were such a function. Notice that it would be injective: if <math>f(a) = f(b)</math>, then <math>f(f(a)) = f(f(b))</math>, so <math>a + 1987 = b + 1987</math> and therefore <math>a = b</math>.
+Because <math>f \circ f</math> is linear, it satisfies the following equation for all non-negative integers <math>a, b, c, d</math> such that <math>a \neq b</math> and <math>c \neq d</math>:
+<cmath> \frac{f(f(b)) - f(f(a))}{f(b) - f(a)} = \frac{f(f(d)) - f(f(c))}{f(c) - f(d)}. </cmath>
+(Injectivity guarantees the denominators are non-zero.) But <math>f(f(b)) - f(f(a)) = b - a</math> and <math>f(f(d)) - f(f(c)) = d - c</math>, so
+<cmath> \frac{b - a}{f(b) - f(a)} = \frac{d - c}{f(d) - f(c)}, </cmath>
+and therefore
+<cmath> \frac{f(b) - f(a)}{b - a} = \frac{f(d) - f(c)}{d - c}. </cmath>
+Thus <math>f</math> itself is linear, so there exist non-negative integers <math>m, b</math> such that <math>f(x) = mx + b</math>. It follows that
+<cmath>\begin{align*}
+f(f(x)) &= m(mx + b) + b \\
+        &= m^2x + b(m + 1).
+\end{align*}</cmath>
+So <math>m^2 x + b(m + 1) = x + 1987</math> for all non-negative integers <math>x</math>. This is only possible if the coefficients match. So  <math>m^2 = 1</math>, and thus <math>m = 1</math>. Likewise <math>b(m + 1) = 1987</math>, so <math>b = 1987/2</math>. This contradicts the fact that <math>b</math> is an integer.
 {{IMO box|num-b=3|num-a=5|year=1987}}

Page

Toolbox

Search