Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1987 IMO Problems/Problem 4"
m
Line 12: Line 12:
 
Solution by Sawa Pavlov:
 
Solution by Sawa Pavlov:
  
−
Let <math>N</math> be the set of non-negative integers. Put <math>A = N - f(N)</math> (the set of all <math>n</math> such that we cannot find m with f(m) = n). Put <math>B = f(A)</math>.  
+
Let <math>N</math> be the set of non-negative integers. Put <math>A = N - f(N)</math> (the set of all <math>n</math> such that we cannot find <math>m</math> with <math>f(m) = n</math>). Put <math>B = f(A)</math>.  
  
 
Note that <math>f</math> is injective because if <math>f(n) = f(m)</math>, then <math>f(f(n)) = f(f(m))</math> so <math>m = n</math>. We claim that <math>B = f(N) - f(f(N))</math>. Obviously <math>B</math> is a subset of <math>f(N)</math> and if <math>k</math> belongs to <math>B</math>, then it does not belong to <math>f(f(N))</math> since <math>f</math> is injective. Similarly, a member of <math>f(f(N))</math> cannot belong to <math>B</math>.  
 
Note that <math>f</math> is injective because if <math>f(n) = f(m)</math>, then <math>f(f(n)) = f(f(m))</math> so <math>m = n</math>. We claim that <math>B = f(N) - f(f(N))</math>. Obviously <math>B</math> is a subset of <math>f(N)</math> and if <math>k</math> belongs to <math>B</math>, then it does not belong to <math>f(f(N))</math> since <math>f</math> is injective. Similarly, a member of <math>f(f(N))</math> cannot belong to <math>B</math>.  

Revision as of 01:13, 15 March 2008

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

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.

Other Solution

Solution by Sawa Pavlov:

Let $N$ be the set of non-negative integers. Put $A = N - f(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(N) - f(f(N))$. Obviously $B$ is a subset of $f(N)$ and if $k$ belongs to $B$, then it does not belong to $f(f(N))$ since $f$ is injective. Similarly, a member of $f(f(N))$ cannot belong to $B$.

Clearly $A$ and $B$ are disjoint. They have union $N - f(f(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.

1987 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_IMO_Problems/Problem_4&oldid=24023"