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