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)
 
(15 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 ==
 
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>.  
 
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>.  
  
 
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.  
 
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>\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.  
+
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.  
  
−
==Other Solution==
+
==Solution 2 ==
−
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 n such that we cannot find m with f(m) = n). Put <math>B = f(A)</math>.  
+
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>.  
  
−
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(\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>.  
  
−
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.
+
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 3 ==
 +
 
 +
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. 
 +
 
 +
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>. 
 +
 
 +
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.
 +
 
 +
''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>.
 +
 
 +
--[[User:Mahamaya|<font color="#FF 69 B4">Maha</font><font color="#FF00FF">maya</font>]] 21:15, 21 May 2012 (EDT)
  
 
{{IMO box|num-b=3|num-a=5|year=1987}}
 
{{IMO box|num-b=3|num-a=5|year=1987}}
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Functional Equation Problems]]

Latest revision as of 18: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"