IMO 1999 SL C6

Origin: GBR | Category: Combinatorics

Problem

Suppose that every integer has been given one of the colors red, blue, green, yellow. Let x and y be odd integers such that |x| ̸= |y|. Show that there are two integers of the same color whose difference has one of the following values: x, y, x + y, x −y.

Solution

We denote colors by capital initial letters. Let us suppose that there exists a coloring f : Z \to{R, G, B, Y } such that for any a \inZ we have f{a, a + x, a + y, a + x + y} = {R, G, B, Y }. We now define a coloring of an integer lattice g : Z\timesZ \to{R, G, B, Y } by the rule g(i, j) = f(xi+yj). It follows that every unit square in g must have its vertices colored by four different colors. If there is a row or column with period 2, then applying the condition to adjacent unit squares, we get (by induction) that all rows or columns, respectively, have period 2. On the other hand, taking a row to be not of period 2, i.e., containing a sequence of three distinct colors, for example GRY , we get that the next row must contain in these columns Y BG, and the following GRY , and so on. It would follow that a column in this case must have period 2. A similar conclusion holds if we start with an aperiodic column. Hence either all rows or all columns must have period 2. Let us assume w.l.o.g. that all rows have a period of 2. Assuming w.l.o.g. {g(0, 0), g(1, 0)} = {G, B}, we get that the even rows are painted with {G, B} and odd with {Y, R}. Since x is odd, it follows that g(y, 0) and g(0, x) are of different color. However, since g(y, 0) = f(xy) = g(0, x), this is a contradiction. Hence the statement of the problem holds.