Difference between revisions of "1987 IMO Problems/Problem 4"
m (→Solution 4) |
m (→Solution 4) |
||
Line 50: | Line 50: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
f(f(x)) &= m(mx + b) + b \\ | f(f(x)) &= m(mx + b) + b \\ | ||
− | &= m^2x + | + | &= m^2x + (m + 1)b. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | So <math>m^2 x + b(m + 1) = x + 1987</math> for all non-negative integers <math>x</math>. This is only possible if the coefficients match: <math>m^2 = 1</math> and <math> | + | So <math>m^2 x + b(m + 1) = x + 1987</math> for all non-negative integers <math>x</math>. This is only possible if the coefficients match: <math>m^2 = 1</math> and <math>(m + 1)b = 1987</math>. It follows that <math>b = 1987/2</math>, which contradicts the fact that <math>b</math> is an integer. |
{{IMO box|num-b=3|num-a=5|year=1987}} | {{IMO box|num-b=3|num-a=5|year=1987}} |
Revision as of 14:32, 21 January 2024
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:
and
. It follows that
, which 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 |