Maths Olympiad Prep

Library / /52 of 61

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

Problem:

n>1n > 1 is an integer. DnD_n is the set of lattice points (x,y)(x, y) with x,yn|x|, |y| \leq n. If the points of DnD_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 DnD_n. Show that it is possible to color the points of DnD_n with four colors (one for each point) so that if any line contains just two points of DnD_n then those two points have different colors.

Solution

Solution:

Figure 1

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

The second part is the standard parity argument. Color (x,y)(x, y) with color 1 if xx and yy are both even, 2 if xx is even and yy is odd, 3 if xx is odd and yy is even, and 4 if xx and yy 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 DnD_n on the line.

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.