Proposed Problem for American Math Monthly

Matthew Baker 1613 6th St. Apt. E Berkeley, CA 94710 (510) 525-2077 baker@math.berkeley.edu

Problem: Let Q^{2} be the set of points in the Euclidean plane R^{2} having rational coordinates. Can one color each point of Q^{2} either red or blue in such a way that no two points of the same color are exactly one unit apart?

Solution:

The answer is yes. In order to give the algorithm, we first prove a lemma about lattice points. First, some notation. We will denote by Z^{2} the set of points in R^{2} with integer coordinates. A path of constant step length n on Z^{2} (resp. Q^{2} ) will mean a set {S_{1}, S_{2}, …, S_{k}} of line segments such that the endpoints of S_{i} are E_{i}, F_{i} ∈ Z^{2} (resp. Q^{2}) with E_{2} = F_{1}, E_{3} = F_{2}, …, E_{k} = F_{k−1}, and d(a_{i}, b_{i}) = n, where d denotes the Euclidean distance on R^{2}. A path is closed if in addition E_{1} = F_{k}, and we will say that the number of steps in a path as above is k.

Lemma: Let n ≥ 1 be an integer. The number of steps in any closed path of constant step length n on Z^{2} is even.

Proof: Suppose first that n is odd. Color the points in Z^{2} black and white in checkerboard fashion; in other words, color (x, y) white if x ≡ y (mod 2) and black if x ≢ y (mod 2). It is clearly enough to show that any point (a, b) exactly n units away from (0, 0) is black. In other words, we want to show that a + b is odd. This follows from the fact that a + b ≡ a^{2} + b^{2} = n^{2} ≡ n (mod 2).

Now suppose n is even. Then any point (a, b) exactly n units from (0, 0) must have a, b both even. For otherwise a^{2} + b^{2} = n^{2} with a, b both odd, but this is absurd since this implies n^{2} ≡ 2 (mod 4). So any counterexample to the lemma, i.e., a closed path X of constant step length n = 2m having an odd number of total steps, yields a counterexample with constant step length m by first translating so that one of the endpoints of X is (0, 0), and then dividing all coordinates by 2. Continuing in this way, we reduce to the case just established where n is odd.

Q.E.D.

We now use our lemma to solve the problem.

First partition the points in Q^{2} into equivalence classes, where two points are considered equivalent if they can be connected by a path of constant step length 1 on Q^{2}. Then clearly it is enough to give an algorithm for coloring the points in a given equivalence class, for no two points in different classes can be 1 unit apart. So pick one equivalence class S, pick a reference point P in S, and color it white. For any Q ∈ S, connect P and Q by a path T of constant step length 1. If the number of steps in T is even, color Q white; if odd, color Q black. If this is well-defined, then it clearly solves the problem. And it is well-defined, because if there were paths T, T′ from P to Q whose lengths had opposite parity, this would imply the existence of a closed path of constant step length 1 on Q^{2} with an odd number of total steps. Let d be the g.c.d. of the denominators of all coordinates of vertices of T, T′. Scaling everything up, we get a closed path of constant step length d on Z^{2} with an odd number of total steps, which contradicts the lemma.

Q.E.D.