1987 IMO Problems/Problem 4
Problem
Prove that there is no function from the set of non-negative integers into itself such that for every .
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 whenever , and hence is well defined.
Now, we observe that satisfies the identity , for . 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 the identity derived above, along with . However, these two equations imply that , which is a contradiction since is an integer. Thus, such an cannot exist.
Note: The main step in the proof above is that the function 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 , satisfies the condition .
--Mahamaya 21:15, 21 May 2012 (EDT)
Solution 4
Suppose were such a function. Notice that it would be injective: if , then , so and therefore .
Because is linear, it satisfies the following equation for all non-negative integers such that and :
(Injectivity guarantees the denominators are non-zero.) But and , so
and therefore
Thus itself is linear, so there exist non-negative integers such that . It follows that
So for all non-negative integers . This is only possible if the coefficients match. So , and thus . Likewise , so . This contradicts the fact that is an integer.
1987 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |