Library / Iberoamerican Mathematical Olympiad /49 of 57

Iberoamerican Mathematical Olympiad

Combinatorics Difficulty 6.5 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:

$n > 1$ is an integer. $D_n$ is the set of lattice points $(x, y)$ with $|x|, |y| \leq n$ . If the points of $D_n$ are colored with three colors (one for each point), show that there are always two points with the same color such that the line containing them does not contain any other points of $D_n$ . Show that it is possible to color the points of $D_n$ with four colors (one for each point) so that if any line contains just two points of $D_n$ then those two points have different colors.

Solution

Solution:

Consider the 4 points shown in the diagram. In each case the segment joining them is the diagonal of an $m \times 1$ parallelogram or rectangle, so it cannot contain any other lattice points. The next points along each line are obviously outside set $D_n$ . That proves the first part.

The second part is the standard parity argument. Color $(x, y)$ with color 1 if $x$ and $y$ are both even, 2 if $x$ is even and $y$ is odd, 3 if $x$ is odd and $y$ is even, and 4 if $x$ and $y$ are both odd. Then if two points are the same color, that means the first coordinates are the same parity and their second coordinates are the same parity. Hence the midpoint of the segment joining them is also a lattice point and they are not the only two points of $D_n$ on the line.

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

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