Problem 2

Let

S=\{1,2,\ldots,2014\}

. For each non-empty subset

T\subseteq S

, one of its members is chosen as its representative. Find the number of ways to assign representatives to all non-empty subsets of

S

so that if

D\subseteq S

is a disjoint union of non-empty subsets

A,B,C\subseteq S

, then the representative of

D

is also the representative of at least one of

A,B,C

Step 2 of 3: Choose the forced chain

Previous step Next step

x_1,x_2,\ldots,x_{2010}:\quad 2014\cdot2013\cdots5

Detailed analysis

There are 2014 choices for $x_1$ . Remove it and repeat the argument on the remaining set, then choose $x_2$ , and so on through $x_{2010}$ . The number of choices is the displayed product; every subset containing the first available $x_i$ has that representative.