Competition problem — Combinatorics

Library / /42 of 299

Combinatorics Difficulty 5.7 AIME, harder Prove it Iran

Let $S$ be a set with $n$ elements and $P(S)$ be the set of all subsets of $S$ . We want to partition $P(S)$ to $m$ parts such that if $A$ , $B$ and $A \cup B$ are in the same part then $A = B$ . Find the minimum value of $m$ so that such a partition exists.

Solution

The answer is $m = n + 1$ . To give an example, for all integers $0 \le i \le n$ define
$A_i = \{E \mid E \subset S, |E| = i\}.$
This partition satisfies the condition of problem, because if $A$ , $B$ and $A \cup B$ are in the same partition it means that they have the same number of elements but $A, B \subset A \cup B$ , so we have $A = A \cup B = B$ .

To prove that it is impossible for $m \le n$ , we give $n + 1$ sets such that no two of them can be in the same part. Assume that $S = \{1, 2, 3, \dots, n\}$ . Consider $A_0 = \emptyset$ and for all integers $1 \le i \le n$ ,
$A_i = \{1, 2, \dots, i\}.$
For $i < j$ we have $A_i \cup A_j = A_j$ so they can not be in the same partition.

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.