Difference between revisions of "1987 IMO Problems/Problem 4"
m |
(Added Alternate solution) |
||
Line 18: | Line 18: | ||
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>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. | ||
+ | |||
+ | ===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\; {\rm mod }\;1987) = f(y \;{\rm mod }\; 1987) \;{\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 \mathbb{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 teh 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 = \drac{1}{2}</math>, which is a contradiction since <math>k</math> is an integer. Thus, such an $f4 cannot exist. | ||
+ | |||
+ | --[[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]] |
Revision as of 20:15, 21 May 2012
Problem
Prove that there is no function from the set of non-negative integers into itself such that for every .
Solution
Solution 1
We prove that if for all , where is a fixed positive integer, then must be even. If , then we may take .
Suppose with . Then by an easy induction on we find , . We show this leads to a contradiction. Suppose , so for some . Then . But , so . Contradiction. So we must have , so for some . But now . But , so . Contradiction.
So if , then and have different residues . Suppose they have and respectively. Then the same induction shows that all sufficiently large have , and that all sufficiently large have . Hence if has a different residue , then cannot have residue or . For if had residue , then the same argument would show that all sufficiently large numbers with residue had . Thus the residues form pairs, so that if a number is congruent to a particular residue, then of the number is congruent to the pair of the residue. But this is impossible for odd.
Solution 2
Solution by Sawa Pavlov:
Let be the set of non-negative integers. Put (the set of all such that we cannot find with ). Put .
Note that is injective because if , then so . We claim that . Obviously is a subset of and if belongs to , then it does not belong to since is injective. Similarly, a member of cannot belong to .
Clearly and are disjoint. They have union which is . But since is injective they have the same number of elements, which is impossible since has an odd number of elements.
Solution 3
Consider the function defined by . Notice that we have , so that , and hence is well defined.
Now, we observe that satisfies the identity , for $x \in \mathbb{Z_{1987}$ (Error compiling LaTeX. Unknown error_msg). Thus, is an invertible function on a finite set of odd size, and hence must have a fixed point, say . Identifying with its canonical representative in , we therefore get for some non-negative integer .
However, we then have , while (where we use teh identity derived above, along with . However, these two equations imply that $k = \drac{1}{2}$ (Error compiling LaTeX. Unknown error_msg), which is a contradiction since is an integer. Thus, such an $f4 cannot exist.
--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 |