2006 students make a list with 12 schools
Source: Turkey, TST D2, P3
May 10, 2006
combinatorics proposedcombinatorics
Problem Statement
Each one of 2006 students makes a list with 12 schools among 2006. If we take any 6 students, there are two schools which at least one of them is included in each of 6 lists. A list which includes at least one school from all lists is a good list.
a) Prove that we can always find a good list with 12 elements, whatever the lists are;
b) Prove that students can make lists such that no shorter list is good.