IMO 1990 SL 28

Origin: USS

Problem

Prove that on the coordinate plane it is impossible to draw a closed broken line such that (i) the coordinates of each vertex are rational; (ii) the length each of its edges is 1; (iii) the line has an odd number of vertices.

Solution

Let us first prove the following lemma. Lemma. Let (b′/a′, d′/c′) and (b′′/a′′, d′′/c′′) be two points with rational coordinates where the fractions given are irreducible. If both a′ and c′ are odd and the distance between the two points is 1 then it follows that a′′ and c′′ are odd, and that b′ + d′ and b′′ + d′′ are of a different parity. Proof. Let b/a and d/c be irreducible fractions such that b′/a′ −b′′/a′′ = b/a and d′/c′ −d′′/c′′ = d/c. Then it follows that b2/a2 + d2/c2 = 1 ⇒b2c2 + a2d2 = a2c2. Since (a, b) = 1 and (c, d) = 1 it follows that a | c, c | a and hence a = c. Consequently b2 + d2 = a2. Since a is mutually co-prime to b and d it follows that a and b+d are odd. From b′′/a′′ = b/a + b′/a′ we get that a′′ | aa′, so a′′ is odd. Similarly, c′′ is

odd as well. Now it follows that b′′ \equivb + b′ and similarly d′′ \equivd + d′ (mod 2). Hence b′′ + d′′ \equivb′ + d′ + b + d \equivb′ + d′ + 1 (mod 2), from which it follows that b′ + d′ and b′′ + d′′ are of a different parity. Without loss of generality we start from the origin of the coordinate sys- tem (0/1, 0/1). Initially b + d = 0 and after moving to each subsequent point along the broken line b + d changes parity by the lemma. Hence it will not be possible to return to the origin after an odd number of steps since b + d will be odd.