Let $d$ be a real number such that $d^2=r^2+s^2$, where $r$ and $s$ are rational numbers. Prove that we can color all points of the plane with rational coordinates with two different colors such that the points with distance $d$ have different colors.
Problem
Source: Iran Third Round MO 1997, Exam 2, P3
Tags: analytic geometry, number theory, least common multiple, combinatorics unsolved, combinatorics
30.06.2012 22:30
Lemma. Let $ n \in \mathbb{N} $ is an even number, $a_i, b_i \in \mathbb{Q},\, i=1,2,\ldots, n$ and $a_i^2+b_i^2=r, i=1,2,\ldots,n$. Then $\left(\sum_{i=1}^{n} a_i \right)^2 + \left(\sum_{i=1}^{n} b_i \right)^2 \neq r $. Proof. We can assume that $a_i,b_i \in \mathbb{N}$, because otherwise we can multiply by the $lcm$ of all denominators of $a_i, b_i$. Now assume on the contrary that $r= \left(\sum_{i=1}^{n} a_i \right)^2 + \left(\sum_{i=1}^{n} b_i \right)^2 $. We have: $ r= \left(\sum_{i=1}^{n} a_i \right)^2 + \left(\sum_{i=1}^{n} b_i \right)^2 = \sum_{i=1}^n (a_i^2 + b_i^2) + 2\sum_{i<j} (a_i a_j + b_i b_j) \, \Rightarrow $ (1) $ \,\, -(n-1)r = 2\sum_{i<j} (a_i a_j + b_i b_j) $ Notice that there are 3 possible resedues of $r \mod (4)$: $0,1,2$. If $a_i^2+b_i^2 \equiv 0 \mod (4)$ then $2|a_i,\, 2| b_i $ so we can divide all $a_i,b_i$ by $2$ till $4$ does not divide $r$. Case $a_i^2 + b_i^2 \equiv 1 \mod (4)$ is impossible because LHS of (1) would be odd but RHS is even. Case $a_i^2 + b_i^2 \equiv 2 \mod (4)$ is also impossible because $4$ divide RHS of (1) but does not divide LHS. $\square$ Applying the above lemma we get that if $A_1,A_2,\ldots,A_n$ are points in the plane with rational coordinates such that $|A_1A_2|=|A_2A_2|=\ldots = |A_{n-1}A_n|=|A_nA_1|$ then $n$ must be even. Now, let enumerate all points in the plane with rational coordinates by $A_1,A_2,\ldots$. We will get an infinite graph $G$ if connect $A_i$ to $A_j$ if and only if $|A_iA_j|=d$. Notice that there is not a finite cycle in this graph with an odd lenght. We can consecutevely add $A_i$ to two sets $M$ and $N$ so that if $A_i,A_j \in M$ or $A_i,A_j \in N$ then $A_i, A_j$ are not connected. (bipartite graph). Finally color all points in $M$ with one color and all points in $N$ with the other and we are done.