Competition problem — Combinatorics

Combinatorics Difficulty 4.9 AIME Prove it Brazil

Let $S$ be a set with $n$ elements. Take a positive integer $k$ . Let $A_1, A_2, \dots, A_k$ be any distinct subsets of $S$ . For each $i$ take $B_i = A_i$ or $B_i = S - A_i$ . Find the smallest $k$ such that we can always choose $B_i$ so that $\bigcup_{1 \le i \le k} B_i = S$ .

Solution

The $2^k$ sets $C_1 \cap C_2 \cap \dots \cap C_k$ , where $C_i = A_i$ or $C_i = S - A_i$ , are all disjoint. If $2^k > n$ , it follows that one of them must be empty. Hence its complement (which is $D_1 \cup D_2 \cup \dots \cup D_k$ , where $D_i = S - A_i$ ), is $S$ .

On the other hand if $2^k = n$ , then we can choose $k$ subsets $A_i$ such that all $2^k$ intersections are non-empty. That means all possible unions are incomplete. Thus the answer is the smallest $k$ such that $2^k > n$ .

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 and solution reproduced as published; topic and difficulty added by this site.