Maths Olympiad Prep

Library / /54 of 108

Combinatorics Difficulty 6.0 AIME, harder Prove it Mongolia

Is it possible to color all rational numbers with one of two colors, so that if x,yQx, y \in \mathbb{Q}, xyx \neq y, xy=1xy = 1 or x+y{0,1}x + y \in \{0, 1\} then xx and yy must be colored with different colors.

Solution

Let xQ+x \in \mathbb{Q}^+, x=abx = \frac{a}{b}, (a,b)=1(a, b) = 1, a>0a > 0, b>0b > 0. Now let us apply Euclid's algorithm for aa and bb. Here r0=ar_0 = a, r1=br_1 = b. rj1=qjrj+rj+1r_{j-1} = q_j r_j + r_{j+1}, j=1,2,,nj = 1, 2, \dots, n. There exists n=n(x)n = n(x), such that rn0r_n \neq 0 and rn+1=0r_{n+1} = 0.

Consider the function f:Q{1;1}f: \mathbb{Q} \to \{-1; 1\} defined by
f(x)={(1)n(x)x>01x=0(1)n(x)+1x<0 f(x) = \begin{cases} (-1)^{n(x)} & x > 0 \\ 1 & x = 0 \\ (-1)^{n(-x)+1} & x < 0 \end{cases}

Now let us prove that f(x)f(x) satisfies the given condition.

I. Indeed let x+y=0x + y = 0, xyx \neq y and x>0,y<0x > 0, y < 0. f(x)=(1)n(x)f(x) = (-1)^{n(x)}, f(y)=f(x)=(1)n(x)+1=f(x)f(y) = f(-x) = (-1)^{n(x)+1} = -f(x). Then from this f(x)f(y)=1f(x) \cdot f(y) = -1, which means xx and yy have different colors.

II. Let x+y=1x + y = 1, xyx \neq y. x,yQx, y \in \mathbb{Q}. Then at least one of x,yx, y is positive. Let x>0x > 0, x=abx = \frac{a}{b}. Then y=baby = \frac{b-a}{b}. If y<0y < 0, then f(y)=(1)n(y)+1=(1)n(abb)+1f(y) = (-1)^{n(-y)+1} = (-1)^{n(\frac{a-b}{b})+1}. Considering n(ab)=n(abb)n(\frac{a}{b}) = n(\frac{a-b}{b}), we have f(x)f(y)=1f(x) \cdot f(y) = -1. If y>0y > 0, then 0<x<12<y<10 < x < \frac{1}{2} < y < 1. From Euclid's algorithm n(y)=n(x)+1n(y) = n(x) + 1. f(x)f(y)=1f(x) \cdot f(y) = -1.

III. Let xy=1xy = 1, then x,yx, y have same sign. In this case n(y)=n(x)+1n(y) = n(x) + 1, that implies f(x)f(y)=1f(x)f(y) = -1.

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.