Competition problem — Combinatorics

Library / /91 of 377

Combinatorics Difficulty 4.8 AIME Prove it United States

Problem:

Let $S$ be a set of $5$ points in the $2$ -dimensional lattice. Show that we can always choose a pair of points in $S$ whose midpoint is also a lattice point.

Solution

Solution:

Consider the parities of the coordinates. There are four possibilities: $(\text{odd}, \text{odd})$ , $(\text{odd}, \text{even})$ , $(\text{even}, \text{odd})$ , $(\text{even}, \text{even})$ . By the pigeonhole principle, two of the points must have the same parity in both coordinates (i.e., they are congruent modulo $2$ ). Then, the midpoint of these two points must be a lattice point.

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.