Problem 5

Let

P_1,P_2,\ldots,P_{1993}=P_0

be distinct points in the

xy

-plane with integer coordinates. Assume that no point other than

P_i

and

P_{i+1}

on the segment

P_iP_{i+1}

has both coordinates integers, for

i=0,1,\ldots,1992

. Prove that for some

i

0\le i\le1992

, there is a point

Q=(q_x,q_y)

P_iP_{i+1}

such that both

2q_x

and

2q_y

are odd integers.

Step 3 of 3: Take the midpoint

Previous step Next step

Q=\left(\frac{a+c}{2},\frac{b+d}{2}\right),\qquad 2q_x=a+c,\quad2q_y=b+d

Detailed analysis

Since the two points have the same parity, $a+c$ and $b+d$ have the same parity. If both were even, $Q$ would be an integer point in the interior of the segment, contrary to the hypothesis. Hence both are odd. The midpoint lies on the segment and satisfies $2q_x=a+c$ and $2q_y=b+d$ , both odd integers.