Maths Olympiad Prep

Library / /95 of 105

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:
Determine if it is possible to color each of the rational numbers either red or blue such that the following three conditions are all satisfied:
(i) xx and x-x are opposite colors, for all rational x0x \neq 0;
(ii) xx and 1x1-x are opposite colors, for all rational x1/2x \neq 1 / 2;
(iii) xx and 1/x1 / x are opposite colors, for all rational x0,±1x \neq 0, \pm 1.

Solution

Solution:
The answer is yes.
We will prove the following statement by induction: It is possible to color the rational numbers with denominator at most nn red and blue such that the conditions (i)-(iii) hold whenever the two rational numbers in question both have denominator at most nn, and such that no number reverses color at any step. (The last condition ensures that, when the induction is complete, every number will have a well-defined color.)

We make two base cases. For n=1n=1, color all the positive integers red and all the nonpositive integers blue. Then, for n=2n=2, color the number x+12x+\frac{1}{2} (for integer xx) blue if x0x \geq 0 and red if x<0x<0. It is easy to see that conditions (i)-(iii) are satisfied so far.

Assume that all rational numbers with denominator less than nn (n3n \geq 3) have been colored. We must color the fractions m/nm / n, where mm is an integer coprime to nn. First, when 0<m<n0<m<n, color m/nm / n the opposite of n/mn / m (which has already been colored). Then color 1+m/n1+m / n the same color as m/nm / n for each m>0m>0 coprime to nn. Finally, color m/n-m / n the opposite of m/nm / n. Condition (i) is obviously satisfied. Condition (iii), that m/nm / n and n/mn / m are opposite colors, is relevant only if m<n|m|<n; it is satisfied by definition if m>0m>0, and otherwise it is enough to note that the row of numbers
mn,nm,nm,mn \frac{m}{n}, \quad \frac{n}{m}, \quad-\frac{n}{m}, \quad-\frac{m}{n}
has been colored alternately red and blue, implying that the two end terms have opposite colors. It remains to verify condition (ii). If x>1x>1 or x<0x<0, this follows from (i) and the fact that yy and y+1y+1 have been colored alike for y>0y>0. So we are left with the case 0<x<10<x<1, that is, proving that m/nm / n and (nm)/n(n-m) / n are the same color when 0<m<n0<m<n. The six numbers
mn,nm,nmm,mnm,nnm,nmn \frac{m}{n}, \frac{n}{m},-\frac{n-m}{m},-\frac{m}{n-m}, \frac{n}{n-m}, \frac{n-m}{n}
have been colored alternately red and blue by (ii) and (iii), so the two end terms have opposite colors.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.