The Minimum Number Of Subsets

Discrete Mathematics Level 5

Find the last three digits of the smallest positive integer \(n\) with the following property:

Let \(\mathcal{S}\) be any set containing \(n\) elements. Partition the \(5\) element subsets of \(\mathcal{S}\) into two partitions. Then, at least one of the partitions must contain \(2014\) pairwise disjoint sets.

Details and assumptions

  • Sets \(A_1, A_2, \cdots , A_k\) are called pairwise disjoint if \(|A_i \cap A_j| = 0\) for all \(i \neq j.\)

  • This condition must hold for all sets \(\mathcal{S}\) containing \(n\) elements and all partitions of its \(5\) element subsets.

  • This problem is a generalization of an old USAMO problem.

  • If the last three digits of \(n\) are \(012,\) enter \(12\) as your answer.


Problem Loading...

Note Loading...

Set Loading...