Library / /12 of 26

, 1993

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Let $P_{1}, P_{2}, \ldots, P_{1993}=P_{0}$ be distinct points in the $xy$ -plane with the following properties:
(i) both coordinates of $P_{i}$ are integers, for $i=1,2, \ldots, 1993$ ;
(ii) there is no point other than $P_{i}$ and $P_{i+1}$ on the line segment joining $P_{i}$ with $P_{i+1}$ whose coordinates are both integers, for $i=0,1, \ldots, 1992$ .
Prove that for some $i, 0 \leq i \leq 1992$ , there exists a point $Q$ with coordinates ( $q_{x}, q_{y}$ ) on the line segment joining $P_{i}$ with $P_{i+1}$ such that both $2q_{x}$ and $2q_{y}$ are odd integers.

Solution

Call a point $(x, y) \in \mathbb{Z}^{2}$ even or odd according to the parity of $x+y$ . Since there are an odd number of points, there are two points $P_{i}=(a, b)$ and $P_{i+1}=(c, d), 0 \leq i \leq 1992$ with the same parity. This implies that $a+b+c+d$ is even. We claim that the midpoint of $P_{i} P_{i+1}$ is the desired point $Q$ .

In fact, since $a+b+c+d=(a+c)+(b+d)$ is even, $a$ and $c$ have the same parity if and only if $b$ and $d$ also have the same parity. If both happen then the midpoint of $P_{i} P_{i+1}$ , $Q=\left(\frac{a+c}{2}, \frac{b+d}{2}\right)$ , has integer coordinates, which violates condition (ii). Then $a$ and $c$ , as well as $b$ and $d$ , have different parities, and $2q_{x}=a+c$ and $2q_{y}=b+d$ are both odd integers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.