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.