2004 IMO Shortlist Problems/A3
Problem
(Canada)
Does there exist a function such that if
and
are distinct rational numbers satisfying
or
, then
? Justify your answer.
Solution
For a number , we define the function
to be 0, if
is an integer, or
if
is not an integer. We use the notation
to denote
composed
times. We note that if
, then
, for all nonnegative integers
. We also note that if
differ by an integer, then
.
We claim that for any nonnegative rational , there exists a nonnegative number
such that
. Let
be the relatively prime positive integers such that
. It is enough to show that if
is not an integer, then
, for then we must eventually have
and
. But this follows from
, since by definition,
. Thus for nonnegative rational
, there exists some nonnegative integer
such that
. Then for nonnegative rational
, let
denote the parity class of the least such integer
. For negative rational
, let
. We claim that
satisfies the desired conditions.
First, we prove that if are distinct rationals such that
, then
. But this follows from
.
Next, we prove that if are distinct rationals such that
, then
. Without loss of generality, let
. If
and
are integers, then
must be at least 1, and
must be at most 0, so
and
. If
is a non-integer greater than 1, then
, so
, as desired.
On the other hand, if is a positive rational less than one, then
must be positive, and there exist relatively prime positive integers
such that
and
. We note that
; and since
,
. On the other hand,
, so
. It follows that
, so
, as desired.
Finally, we prove that for nonzero rational ,
, for
. We may clearly assume
without loss of generality. We may also assume
, since in general,
. But we now have
, so
, and
. Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Comment. The solution's construction may seem arbitrary, but it follows from the observation that if such a function exists, then for nonzero
,
, and indeed we must have
, so
. Hence for positive
,
must be distinct from
, where
is any integer less than
: in particular, for non-integers
, when
. The functions
encode this condition; the solution constitutes a proof that this set of constraints is consistent with itself. In fact, from our observations, we can see that our function
is unique up to sign.