[freemind]

In the Cartesian coordinate plane define the strips , and color each strip black or white. Prove that any rectangle which is not a square can be placed in the plane so that its vertices have the same color.

IMO Shortlist 2007 Problem C5 as it appears in the official booklet:

In the Cartesian coordinate plane define the strips for every integer Assume each strip is colored either red or blue, and let and be two distinct positive integers. Prove that there exists a rectangle with side length and such that its vertices have the same color.

Edited by Orlando Döhring

Author: Radu Gologan and Dan Schwarz, Romania

[The QuattoMaster 6000]

Solution

Assume there exists a rectangle that contradicts the problem statement. Let the side lengths of the rectangle be and , let the rectangle be , with , .

Lemma 1: and are integers.

We consider parallel to the y-Axis and parallel for the x-Axis in the proof of the lemma. If either or is not an integer, without loss of generality, let it be . Take two strips, and that are not the same color, say that is black and is white. Consider . It must be white since or else we may put and on and and on , thereby creating a rectangle with all verticies of the same color. However, shifting and so that they lie on will still force and to be in the white strip, but and will now be in , a white strip as well. Hence, we have a contradiction and thus and are integers.

Lemma 2:

Now, say that strip is black. Then, strip is white since otherwise, we may put and in and and in . By similar logic, must be white. Hence, is black if and only if is even and is black if and only if is even. Now, if , we see that is black since is even. However, is odd, so is also white, which is a contradiction, so .

Let , , and . Let and be so that . By Lemma 2, we see that and are odd, so is odd, meaning that if is black, then is white. This forces that is black, and the colors cycle in lengths of . Now, inscribe in a rectangle , with parallel to the x-Axis, parallel to the y-Axis, so that is on , is on , is on , and is on . Let . Since and are odd, we have that , so we may force . This means that as well. By the Pythagorean Theorem, we get that . Furthermore, since , we see that . This means that

Let the projection from onto be and that from to be . This means that since is odd, does not have an integer length. Hence, by Lemma 1, we can shift so that , , , and are be the same color (recall that has its sides parallel to the axes and is parallel to the x-Axis). Since and have a horizontal distance of , we see that and are the same color. Similarly, and are the same color. Since and are the same color, we see that all verticies of are the same color. Hence, we have a contradiction and no such rectangle exists.