IMO 2001 SL C4

Origin: NZL | Category: Combinatorics

Problem

A set of three nonnegative integers {x, y, z} with x < y < z is called historic if {z −y, y −x} = {1776, 2001}. Show that the set of all nonnegative integers can be written as the union of disjoint historic sets.

Solution

For convenience let us write a = 1776, b = 2001, 0 < a < b. There are two types of historic sets: (1) {x, x + a, x + a + b} and (2) {x, x + b, x + a + b}. We construct a sequence of historic sets H1, H2, H3, . . . inductively as follows:

(i) H1 = {0, a, a + b}, and (ii) Let yn be the least nonnegative integer not occurring in Un = H1 \cap \cdot \cdot \cdot \capHn. We take Hn+1 to be {yn, yn + a, yn + a + b} if yn + a ̸\inUn, and {yn, yn + b, yn + a + b} otherwise. It remains to show that this construction never fails. Suppose that it failed at the construction of Hn+1. The element yn + a + b is not contained in Un, since by the construction the smallest elements of H1, . . . , Hn are all less than yn. Hence the reason for the failure must be the fact that both yn + a and yn + b are covered by Un. Further, yn + b must have been the largest element of its set Hk, so the smallest element of Hk equals yn −a. But since yn is not covered, we conclude that Hk is of type (2). This is a contradiction, because yn was free, so by the algorithm we had to choose for Hk the set of type (1) (that is, {yn −a, yn, yn + b}) first.