Maths Olympiad Prep

Library / /97 of 105

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

The manager of Chez Gastropod wants to write a menu consisting of 15 dishes. A "meal" is defined to be a subset of this menu (possibly empty), but some meals are legal and others are not. The manager may choose which meals are legal, but there is a requirement that the intersection of any two legal meals should still be legal. He wants there to be exactly 2001 legal meals. Can he do it?

Solution

Solution:

The answer is yes. Take any arbitrary 15-element set (menu), and call a collection of subsets (meals) "valid" if the intersection of any two sets in the collection is again in the collection. Thus, the objective is to show that there exists a valid collection containing exactly 2001 sets. We will show, by downward induction, that there exists a valid collection with exactly nn sets for each nn, 0n215=327680 \leq n \leq 2^{15} = 32768.

The base case n=215n = 2^{15} is clear: the collection of all subsets of the menu is certainly valid. For the induction step, suppose that there is a valid collection CC of nn subsets (1n327681 \leq n \leq 32768); we will show that there is a valid collection of n1n-1 subsets. Choose a subset in CC of maximum possible size, and remove it; let CC' denote the remaining collection, so that it consists of n1n-1 subsets. We claim CC' is still valid. Indeed, if S,TCS, T \in C', then the removed subset cannot be contained within either SS or TT (because of maximality), hence it certainly cannot equal their intersection. But STS \cap T was in CC; hence, it is also in CC', as needed. Thus, the claim holds. Now, let n=2001n = 2001, and the problem is solved.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.