Difference between revisions of "1987 IMO Problems/Problem 4"
m |
|||
(7 intermediate revisions by 3 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 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>. | ||
Line 10: | Line 9: | ||
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. | 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: | 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 <math>n</math> such that we cannot find <math>m</math> with <math>f(m) = n</math>). 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. | 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. |
Latest revision as of 19:51, 21 January 2024
Contents
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)
1987 IMO (Problems) • Resources | ||
Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
All IMO Problems and Solutions |