Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2004 IMO Shortlist Problems/A3

Problem

(Canada) Does there exist a function $s : \mathbf{Q} \rightarrow \{ -1,1 \}$ such that if $\displaystyle x$ and $\displaystyle y$ are distinct rational numbers satisfying $\displaystyle {} xy=1$ or $x+y \in \{ 0,1 \}$, then $\displaystyle s(x)s(y) = -1$? Justify your answer.

Solution

For a number $\displaystyle x$, we define the function $\displaystyle t(x)$ to be 0, if $\displaystyle x$ is an integer, or $\frac{1}{x-\lfloor x \rfloor}$ if $\displaystyle x$ is not an integer. We use the notation $\displaystyle t^n$ to denote $\displaystyle t$ composed $\displaystyle n$ times. We note that if $\displaystyle x = 0$, then $\displaystyle t^n(x) = 0$, for all nonnegative integers $\displaystyle n$. We also note that if $\displaystyle x,y$ differ by an integer, then $\displaystyle t(x) = t(y)$.

We claim that for any nonnegative rational $\displaystyle x$, there exists a nonnegative number $\displaystyle n$ such that $\displaystyle t^n(x) = 0$. Let $\displaystyle p_n, q_n$ be the relatively prime positive integers such that $t^n(x) = \frac{p_n}{q_n}$. It is enough to show that if $\displaystyle t^n(x)$ is not an integer, then $\displaystyle q_{n+1} < q_n$, for then we must eventually have $\displaystyle q_n = 1$ and $\displaystyle t^{n+1}(x) = 0$. But this follows from $t^{n+1}(x) = \frac{1}{t^n(x) - \lfloor t^n(x) \rfloor} = \frac{q_n}{p_n - q_n \lfloor p_n/q_n \rfloor}$, since by definition, $p_n - q_n \lfloor p_n/q_n \rfloor < q_n$. Thus for nonnegative rational $\displaystyle x$, there exists some nonnegative integer $\displaystyle n$ such that $\displaystyle t^n(x) =0$. Then for nonnegative rational $\displaystyle x$, let $\displaystyle f(x) : \mathbb{Q} \rightarrow \mathbb{Z}/2\mathbb{Z}$ denote the parity class of the least such integer $\displaystyle n$. For negative rational $\displaystyle x$, let $\displaystyle f(x) = f(-x)+1$. We claim that $\displaystyle s(x) = (-1)^{f(x)}$ satisfies the desired conditions.

First, we prove that if $\displaystyle x,y$ are distinct rationals such that $\displaystyle x+y =0$, then $\displaystyle s(x)s(y) = -1$. But this follows from $f(-x) \equiv f(x) + 1$.

Next, we prove that if $\displaystyle x,y$ are distinct rationals such that $\displaystyle x+y = 1$, then $\displaystyle s(x)s(y) = -1$. Without loss of generality, let $\displaystyle x> y$. If $\displaystyle x$ and $\displaystyle y$ are integers, then $\displaystyle x$ must be at least 1, and $\displaystyle y$ must be at most 0, so $\displaystyle s(x) = -1$ and $\displaystyle s(y)=1$. If $\displaystyle x$ is a non-integer greater than 1, then $\displaystyle t(x) = t(x-1) = t(-y)$, so $\displaystyle s(x) = s(-y) = -s(y)$, as desired.

On the other hand, if $\displaystyle x$ is a positive rational less than one, then $\displaystyle y$ must be positive, and there exist relatively prime positive integers $\displaystyle p, q$ such that $\displaystyle 2p < q$ and $\displaystyle y = \frac{p}{q} , x= \frac{q-p}{q}$. We note that $\displaystyle t(x) = \frac{q}{q-p}$; and since $\displaystyle \frac{q}{q-p} = 1 + \frac{p}{q-p} < 1+ \frac{p}{2p-p} = 2$, $\displaystyle t^2(x) = \frac{q-p}{p}$. On the other hand, $\displaystyle t(y) = \frac{q}{p} = \frac{q-p}{p} + 1 = t^2(x) +1$, so $\displaystyle t^2(y) = t^3(x)$. It follows that $\displaystyle {} f(x) = f(y) +1$, so $\displaystyle s(x)s(y) = -1$, as desired.

Finally, we prove that for nonzero rational $\displaystyle x$, $\displaystyle s(x)s(1/x) = -1$, for $\displaystyle x \neq 1/x$. We may clearly assume $\displaystyle |x| > 1$ without loss of generality. We may also assume $\displaystyle x , 1/x > 0$, since in general, $\displaystyle s(x)s(y) = [-s(-x)][-s(-y)] = s(-x)s(-y)$. But we now have $\displaystyle t(x) = 1/x$, so $\displaystyle f(x) = f(1/x) +1$, and $\displaystyle s(x)s(1/x) = -1$. 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 $\displaystyle s$ exists, then for nonzero $\displaystyle x$, $\displaystyle s(x) = -s(-x)$, and indeed we must have $\displaystyle s(-x) = -s(x+1)$, so $\displaystyle s(x) = s(x+1)$. Hence for positive $\displaystyle x$, $\displaystyle s(x)$ must be distinct from $\frac{1}{x - k}$, where $\displaystyle k$ is any integer less than $\displaystyle x$: in particular, for non-integers $\displaystyle x$, when $k = \lfloor x \rfloor$. The functions $\displaystyle t,f$ 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 $\displaystyle s$ is unique up to sign.


Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_IMO_Shortlist_Problems/A3&oldid=15191"