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"
(LaTeX-ification nad Wiki-fication)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
We prove that if <math>f(f(n)) = n + k</math> for all <math>n</math>, where <math>k</math> is a fixed positive integer, then <math>k</math> must be even. If <math>k = 2h</math>, then we may take <math>f(n) = n + h</math>.
  
−
{{IMO box|num-b=3|num-a=5|year=1987}}
+
Suppose <math>f(m) = n</math> with <math>m \equiv n \mod k</math>. Then by an easy induction on <math>r</math> we find <math>f(m + kr) = n + kr</math>, <math>f(n + kr) = m + k(r+1)</math>. We show this leads to a contradiction. Suppose <math>m < n</math>, so <math>n = m + ks</math> for some <math>s > 0</math>. Then <math>f(n) = f(m + ks) = n + ks</math>. But <math>f(n) = m + k</math>, so <math>m = n + k(s - 1) \ge n</math>. Contradiction. So we must have <math>m \ge n</math>, so <math>m = n + ks</math> for some <math>s \ge 0</math>. But now <math>f(m + k) = f(n + k(s+1)) = m + k(s + 2)</math>. But <math>f(m + k) = n + k</math>, so <math>n = m + k(s + 1) > n</math>. Contradiction.
  
−
[[Category:Olympiad Algebra Problems]]
+
So if <math>f(m) = n</math>, then <math>m</math> and <math>n</math> have different residues <math>\mod k</math>. Suppose they have <math>r_1</math> and <math>r_2</math> respectively. Then the same induction shows that all sufficiently large <math>s \equiv r_1 \mod k</math> have <math>f(s) \equiv r_2 \mod k</math>, and that all sufficiently large <math>s \equiv r_2 \mod k</math> have <math>f(s) \equiv r_1 \mod k</math>. Hence if <math>m</math> has a different residue <math>r \mod k</math>, then <math>f(m)</math> cannot have residue <math>r_1</math> or <math>r_2</math>. For if <math>f(m)</math> had residue <math>r_1</math>, then the same argument would show that all sufficiently large numbers with residue <math>r_1</math> had <math>f(m) \equiv r \mod k</math>. Thus the residues form pairs, so that if a number is congruent to a particular residue, then <math>f</math> of the number is congruent to the pair of the residue. But this is impossible for <math>k</math> odd.
  
−
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.
+
==Other Solution==
 +
Solution by: Sawa Pavlov
  
−
-------Solution     
+
Let <math>N</math> be the set of non-negative integers. Put <math>A = N - f(N)</math> (the set of all n such that we cannot find m with f(m) = n). Put <math>B = f(A)</math>.
  
−
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.  
+
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>.  
  
−
Suppose f(m) = n with m = 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) ≥ n. Contradiction. So we must have m ≥ n, so m = n + ks for some s ≥ 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.  
+
Clearly <math>A</math> and <math>B</math> are disjoint. They have union <math>N - f(f(N))</math> which is <math>\{0, 1, 2, \ldots , 1986\}</math>. But since <math>f</math> is injective they have the same number of elements, which is impossible since <math>\{0, 1, \ldots , 1986\}</math> has an odd number of elements.
  
−
So if f(m) = n, then m and n have different residues mod k. Suppose they have r1 and r2 respectively. Then the same induction shows that all sufficiently large s = r1 (mod k) have f(s) = r2 (mod k), and that all sufficiently large s = r2 (mod k) have f(s) = r1 (mod k). Hence if m has a different residue r mod k, then f(m) cannot have residue r1 or r2. For if f(m) had residue r1, then the same argument would show that all sufficiently large numbers with residue r1 had f(m) = r (mod 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.
+
{{IMO box|num-b=3|num-a=5|year=1987}}
  
−
A better solution by Sawa Pavlov is as follows
+
[[Category:Olympiad Algebra Problems]]
−
 
 
−
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, ... , 1986}. But since f is injective they have the same number of elements, which is impossible since {0, 1, ... , 1986} has an odd number of elements.
 

Revision as of 01:10, 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 $\mod k$. Suppose they have $r_1$ and $r_2$ respectively. Then the same induction shows that all sufficiently large $s \equiv r_1 \mod k$ have $f(s) \equiv r_2 \mod k$, and that all sufficiently large $s \equiv r_2 \mod k$ have $f(s) \equiv r_1 \mod 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 \mod 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=24021"