Is it possible to color all rational numbers with one of two colors, so that if x,y∈Q, x=y, xy=1 or x+y∈{0,1} then x and y must be colored with different colors.
Solution
Let x∈Q+, x=ba, (a,b)=1, a>0, b>0. Now let us apply Euclid's algorithm for a and b. Here r0=a, r1=b. rj−1=qjrj+rj+1, j=1,2,…,n. There exists n=n(x), such that rn=0 and rn+1=0.
Consider the function f:Q→{−1;1} defined by f(x)=⎩⎨⎧(−1)n(x)1(−1)n(−x)+1x>0x=0x<0
Now let us prove that f(x) satisfies the given condition.
I. Indeed let x+y=0, x=y and x>0,y<0. f(x)=(−1)n(x), f(y)=f(−x)=(−1)n(x)+1=−f(x). Then from this f(x)⋅f(y)=−1, which means x and y have different colors.
II. Let x+y=1, x=y. x,y∈Q. Then at least one of x,y is positive. Let x>0, x=ba. Then y=bb−a. If y<0, then f(y)=(−1)n(−y)+1=(−1)n(ba−b)+1. Considering n(ba)=n(ba−b), we have f(x)⋅f(y)=−1. If y>0, then 0<x<21<y<1. From Euclid's algorithm n(y)=n(x)+1. f(x)⋅f(y)=−1.
III. Let xy=1, then x,y have same sign. In this case n(y)=n(x)+1, that implies f(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.