Problem 1522

1. Lemma: Let $n \in \mathbb{N}$ be an even number, and let $a_i, b_i \in \mathbb{Q}$ for $i=1,2,\ldots, n$. Suppose $a_i^2 + b_i^2 = r$ for $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$.

2. Proof of Lemma: Assume $a_i, b_i \in \mathbb{N}$ (we can multiply by the least common multiple of all denominators of $a_i$ and $b_i$ if necessary). Suppose, for contradiction, that $r = \left(\sum_{i=1}^{n} a_i \right)^2 + \left(\sum_{i=1}^{n} b_i \right)^2$. Then:
$$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)$$
This implies:
$$r = nr + 2\sum_{i<j} (a_i a_j + b_i b_j)$$
Rearranging, we get:
$$-(n-1)r = 2\sum_{i<j} (a_i a_j + b_i b_j)$$
Notice that there are three possible residues of $r \mod 4$: $0, 1, 2$.

3. Case Analysis:
- If $a_i^2 + b_i^2 \equiv 0 \mod 4$, then $2 \mid a_i$ and $2 \mid b_i$. We can divide all $a_i$ and $b_i$ by 2 until 4 does not divide $r$.
- If $a_i^2 + b_i^2 \equiv 1 \mod 4$, this is impossible because the left-hand side (LHS) of the equation would be odd, but the right-hand side (RHS) is even.
- If $a_i^2 + b_i^2 \equiv 2 \mod 4$, this is also impossible because 4 divides the RHS but does not divide the LHS.

Therefore, the assumption that $r = \left(\sum_{i=1}^{n} a_i \right)^2 + \left(\sum_{i=1}^{n} b_i \right)^2$ must be false. This completes the proof of the lemma. $\blacksquare$

4. Application of Lemma: If $A_1, A_2, \ldots, A_n$ are points in the plane with rational coordinates such that $|A_1A_2| = |A_2A_3| = \ldots = |A_{n-1}A_n| = |A_nA_1|$, then $n$ must be even.

5. Graph Construction: Enumerate all points in the plane with rational coordinates as $A_1, A_2, \ldots$. Construct an infinite graph $G$ by connecting $A_i$ to $A_j$ if and only if $|A_iA_j| = d$.

6. Graph Properties: Notice that there is no finite cycle in this graph with an odd length. This implies that the graph is bipartite.

7. Coloring the Graph: We can consecutively add $A_i$ to two sets $M$ and $N$ such that if $A_i, A_j \in M$ or $A_i, A_j \in N$, then $A_i$ and $A_j$ are not connected. This is possible because the graph is bipartite.

8. Final Coloring: Color all points in $M$ with one color and all points in $N$ with the other color. This ensures that any two points with distance $d$ have different colors.

$\blacksquare$