Maths Olympiad Prep

Library / /466 of 520

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

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.

Solution

### Part (a)

1. Initial Assumption and Setup:
Assume that no single student's list is a good list. This means that for any student x x , there exists at least one school that is not included in x x 's list.

2. Existence of Disjoint Lists:
Consider two students x x and y y whose lists do not share any common schools. Let X X and Y Y be the sets of schools listed by x x and y y , respectively. Since each list contains 12 schools and there are 2006 schools in total, it is possible to find such disjoint lists.

3. Partitioning the Lists:
Split X X and Y Y into two sets of size 6 each:
X=ACandY=BD X = A \cup C \quad \text{and} \quad Y = B \cup D
where A=B=C=D=6 |A| = |B| = |C| = |D| = 6 .

4. Constructing Potential Good Lists:
Consider the following lists:
X,Y,AB,AD,BC,CD X, Y, A \cup B, A \cup D, B \cup C, C \cup D
We claim that at least one of these lists is a good list.

5. Contradiction Argument:
Assume for contradiction that none of these lists is a good list. This means that for each of these lists, there exists a set of 6 students such that no school in the list is included in all 6 students' lists.

6. Applying the Problem's Condition:
Take sets S1,S2,S3,S4 S_1, S_2, S_3, S_4 such that they are disjoint with AB,BC,CD,DA A \cup B, B \cup C, C \cup D, D \cup A respectively. According to the problem's condition, for any 6 students, there must be at least two schools that are included in the lists of all 6 students.

7. Contradiction:
Since X X and Y Y are disjoint, and each Si S_i is disjoint with one of the combined sets, it is impossible for all 6 students to avoid having at least one school from X X or Y Y in their lists. This leads to a contradiction.

8. Conclusion:
Therefore, at least one of the lists X,Y,AB,AD,BC,CD X, Y, A \cup B, A \cup D, B \cup C, C \cup D must be a good list.

\blacksquare

### Part (b)

1. Initial Setup:
Consider the total number of possible 12-element subsets of a set of 23 schools. This number is given by the binomial coefficient:
(2312) \binom{23}{12}
which is less than 2006000.

2. Constructing the Lists:
First, take (2312)\binom{23}{12} students and let their lists be all possible 12-element subsets of a set of 23 schools. Then, add 2006000(2312)2006000 - \binom{23}{12} other students with their lists being arbitrary subsets of the same 23 schools.

3. Ensuring No Shorter List is Good:
We need to show that no 11-element subset of schools can be a good list. Consider any 6 subsets A,B,C,D,E,F[23] A, B, C, D, E, F \subset [23] each of size 12. Notice that any two of them must have a common element.

4. Common Element Argument:
If some four of these subsets had a common element, we would be done. Suppose A,B,C,D A, B, C, D had a common element e e . Then, we can take the two-element subset containing e e and an arbitrary element in EF E \cap F .

5. Existence of Common Element:
The total number of elements in A,B,C,D,E,F A, B, C, D, E, F is 12×6=72 12 \times 6 = 72 . Since 72>3×23 72 > 3 \times 23 , by the pigeonhole principle, some element 1i23 1 \le i \le 23 must be in at least four of the subsets A,B,C,D,E,F A, B, C, D, E, F .

6. Conclusion:
This construction ensures that no 11-element subset of schools can be a good list, as required.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.