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 , there exists at least one school that is not included in 's list.
2. Existence of Disjoint Lists:
Consider two students and whose lists do not share any common schools. Let and be the sets of schools listed by and , 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 and into two sets of size 6 each:
where .
4. Constructing Potential Good Lists:
Consider the following lists:
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 such that they are disjoint with 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 and are disjoint, and each is disjoint with one of the combined sets, it is impossible for all 6 students to avoid having at least one school from or in their lists. This leads to a contradiction.
8. Conclusion:
Therefore, at least one of the lists must be a good list.
### 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:
which is less than 2006000.
2. Constructing the Lists:
First, take students and let their lists be all possible 12-element subsets of a set of 23 schools. Then, add 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 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 had a common element . Then, we can take the two-element subset containing and an arbitrary element in .
5. Existence of Common Element:
The total number of elements in is . Since , by the pigeonhole principle, some element must be in at least four of the subsets .
6. Conclusion:
This construction ensures that no 11-element subset of schools can be a good list, as required.