MathDB
Is a cycle of 1990 committees possible with 11 countries?

Source: IMO ShortList 1990, Problem 2 (CAN 1)

August 15, 2008
combinatoricsSet systemsgraph theoryExtremal combinatoricsIMO Shortlist

Problem Statement

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