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.
Problem
Source: IMO ShortList 1990, Problem 28 (USS 3)
Tags: analytic geometry, vector, number theory, rational number, IMO Shortlist
tjhance
19.08.2008 03:30
Assume one such line exists. First, scale this line so that the the coordinates are integers. Now, we can represent each edge of this broken line as a vector $ (x,y)$ with $ x$ and $ y$ and magnitude $ d$. The sum of all these vectors will be $ (0,0)$. Call these vectors
$ (x_1,y_1),(x_2,y_2),...,(x_n,y_n)$.
where $ n$ is odd. Then $ x_1^2 + y_1^2 = x_2^2 + y_2^2 = ... = x_n^2 + y_n^2 = d^2$.
Suppose that at least one of $ x_1,x_2,...,x_n,y_1,y_2,...,y_n$ is odd. Otherwise, we can divide all of the coordinates and $ d$ by $ 2$. Now, because $ x_1 + x_2 + \cdots + x_n = 0$ and $ y_1 + y_2 + \cdots + y_n = 0$, an even number of $ x_1,x_2,...,x_n$ are odd and an even number of $ y_1,y_2,...,y_n$ are odd.
Now I will show that $ d$ is even. Suppose for the sake of contradiction that $ d$ is odd. Then for each pair $ (x_i,y_i)$, exactly one of $ x_i$ and $ y_i$ is odd. So there are exactly $ n$ coordinates which are odd, which is a contradiction since we showed above that the number of odd coordinates is even. Hence $ d$ is even, so $ d^2\equiv 0\mod 4$.
But we are also assuming that there is at least one odd coordinate, so for some $ i$, we have $ x_i^2 + y_i^2\equiv 1$ or $ 2\mod 4$, a contradiction.
Note this generalizes to where $ d^2$ is any integer, not necessarily that $ d$ is an integer. There is some pair $ (x_i,y_i)$ with $ x_i,y_i$ odd, and there is some pair $ (x_j,y_j)$ (since otherwise every coordinate is odd), so $ x_i^2 + y_i^2\not\equiv x_j^2 + y_j^2\mod 4$.
analytic
19.08.2008 14:54
by graph::
the distance we move away from point = distance coming back
therefore, total distace=d1+d2 ,, let they be expressed in no. of edges
if d1is odd then d2 is odd so, sum is even and same in case of even edges .
hence, no. of edges is even
connecting firt two edges gives 2 vertices and +1 on every subsequent edge, but +-0 on the last edge
hence, +2 on 1st edge and then no. of vertices willbe even on no. of edges as there will be +1 always until last edge . at that time, edge is odd so vertex is even and there will no addition of vertex on last edge.
hence no. of vertices is even.so, this situation aint possible