Competition problem — Combinatorics

Library / /258 of 348

Combinatorics Difficulty 5.0 AIME, harder Find the answer

Let $S=\{1,2, \ldots, 2013\}$ . Find the number of ordered triples $(A, B, C)$ of subsets of $S$ such that $A \subseteq B$ and $A \cup B \cup C=S$ .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let $n=2013$ . Each of the $n$ elements can be independently placed in 5 spots: there are $2^{3}-1$ choices with element $x$ in at least one set, and we subtract the $2^{1}$ choices with element $x$ in set $A$ but not $B$ . Specifying where the elements go uniquely determines $A, B, C$ , so there are $5^{n}=5^{2013}$ ordered triples.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.