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"
 
(16 intermediate revisions by 7 users not shown)
Line 2: Line 2:
 
Prove that there is no function <math>f </math> from the set of non-negative  integers into itself such that <math>f(f(n)) = n + 1987 </math> for every <math>n </math>.
 
Prove that there is no function <math>f </math> from the set of non-negative  integers into itself such that <math>f(f(n)) = n + 1987 </math> for every <math>n </math>.
  
−
==Solution==
+
==Solution 1 ==
−
{{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.
 +
 
 +
So if <math>f(m) = n</math>, then <math>m</math> and <math>n</math> have different residues <math>\pmod 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 \pmod k</math> have <math>f(s) \equiv r_2 \pmod k</math>, and that all sufficiently large <math>s \equiv r_2 \pmod k</math> have <math>f(s) \equiv r_1 \pmod 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 \pmod 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.
 +
 
 +
==Solution 2 ==
 +
Solution by Sawa Pavlov:
 +
 
 +
Let <math>\mathbb{N}</math> be the set of non-negative integers. Put <math>A = \mathbb{N} - f(\mathbb{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>.
  
−
[[Category:Olympiad Algebra Problems]]
+
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(\mathbb{N}) - f(f(\mathbb{N}))</math>. Obviously <math>B</math> is a subset of <math>f(\mathbb{N})</math> and if <math>k</math> belongs to <math>B</math>, then it does not belong to <math>f(f(\mathbb{N}))</math> since <math>f</math> is injective. Similarly, a member of <math>f(f(\mathbb{N}))</math> cannot belong to <math>B</math>.
  
−
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.
+
Clearly <math>A</math> and <math>B</math> are disjoint. They have union <math>\mathbb{N} - f(f(\mathbb{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.
  
−
-------Solution      
+
==Solution 3 ==
  
−
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.  
+
Consider the function <math>g: \mathbb{Z}_{1987} \rightarrow \mathbb{Z}_{1987}</math> defined by <math>g(x) = f(x\; {\rm  mod }\; 1987) \;{\rm  mod }\; 1987</math>.  Notice that we have <math>f(k) + 1987 = f(f(f(k))) = f(k + 1987)</math>, so that <math>f(x) = f(y) \;{\rm  mod }\; 1987</math> whenever <math>x = y \;{\rm mod }\; 1987</math>, and hence <math>g</math> is well defined.
  
−
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.  
+
Now, we observe that <math>g</math> satisfies the identity <math>g(g(x)) = x</math>, for <math>x \in Z_{1987}</math>.   Thus, <math>g</math> is an invertible function on a finite set of odd size, and hence must have a fixed point, say <math>a \in \mathbb{Z}_{1987}</math>. Identifying <math>a</math> with its canonical representative in <math>\mathbb{Z}</math>, we therefore get <math>f(a) = a + 1987k</math> for some non-negative integer <math>k</math>.  
  
−
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.  
+
However, we then have <math>f(f(a)) = a + 1987</math>, while <math>f(f(a)) = f(a + 1987k) = 1987k + f(a) = 2\cdot1987k + a</math> (where we use the identity <math>f(x + 1987) = f(x) + 1987</math> derived above, along with <math>f(a) = f(a) + 1987</math>. However, these two equations imply that <math>k = \dfrac{1}{2}</math>, which is a contradiction since <math>k</math> is an integer.  Thus, such an <math>f</math> cannot exist.
  
−
A better solution by Sawa Pavlov is as follows
+
''Note: The main step in the proof above is that the function <math>g</math> 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 <math>c</math>, <math>f(x) = x + \dfrac{c}{2}</math> satisfies the condition <math>f(f(x)) = x + c</math>.
  
−
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).
+
--[[User:Mahamaya|<font color="#FF 69 B4">Maha</font><font color="#FF00FF">maya</font>]] 21:15, 21 May 2012 (EDT)
  
−
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.
+
{{IMO box|num-b=3|num-a=5|year=1987}}
  
−
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.
+
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Functional Equation Problems]]

Latest revision as of 19:51, 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)

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=211991"