Difference between revisions of "1987 IMO Problems/Problem 4"
(Added Alternate solution) |
m (Minor typo) |
||
Line 21: | Line 21: | ||
===Solution 3=== | ===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 | + | 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 \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>. | 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>. |
Revision as of 21:16, 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
whenever
, 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 |