IMO 1990 SL 2

Origin: CAN

Problem

Given n countries with three representatives each, m commit- tees A(1), A(2), . . . A(m) are called a cycle if (i) each committee has n members, one from each country; (ii) no two committees have the same membership; (iii) for i = 1, 2, . . . , m, committee A(i) and committee A(i + 1) have no member in common, where A(m + 1) denotes A(1); (iv) if 1 < |i −j| < m −1, then committees A(i) and A(j) have at least one member in common. Is it possible to have a cycle of 1990 committees with 11 countries?

Solution

We will call a cycle with m committees and n countries an (m, n) cycle. We will number the delegates from each country with numbers 1, 2, 3 and denote committees by arrays of these integers (of length n) defining which of the delegates from each country is in the committee. We will first devise methods of constructing larger cycles out of smaller cycles. Let A1, . . . , Am be an (m, n) cycle, where m is odd. Then the following is a (2m, n + 1) cycle: (A1, 1), (A2, 2), . . . , (Am, 1), (A1, 2), (A2, 1), . . . , (Am, 2). Also, let A1, . . . , Am be an (m, n) cycle and k \leqm an even integer. Then the cycle (A1, 3), (A2, 1), (A3, 2), . . . , (Ak−2, 1), (Ak−1, 2), (Ak, 3), (Ak−1, 1), (Ak−2, 2), . . . , (A2, 2) is a (2(k −1), n + 1) cycle. Starting from the ((1),(2),(3)) cycle with parameters (3, 1) we can se- quentially construct larger cycles using the shown methods. The obtained cycles have parameters as follows: (6, 2), (10, 3), . . ., (2k + 2, k), . . . , (1026, 10), (1990, 11). Thus there exists a cycle of 1990 committees with 11 countries.