Let $S = \{1,2,\dots,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 a subset $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 one of $A$, $B$, $C$. Warut Suksompong, Thailand
Problem
Source: APMO 2014 Problem 2
Tags: induction
28.03.2014 07:13
The answer is $2014! \cdot 108$. If $S = \{1,2,\ldots,n\}$ is the set instead, let $a_n$ be the number of assignments. First we'll do the nasty base case and show $a_4 = 4! \cdot 108$. The 1-element subsets each only have one choice. The 3-element subsets cannot be unioned with two other nonempty subsets to make a new one, and the only way to partition them into three nonempty subsets leaves us with the condition always satisfied, so the 4 of them can have their representatives chosen ($3^4$ choices). Suppose the 4-element set chooses $k$ as its representative (4 choices), then the three 2-element sets containing $k$ must choose $k$ as well. The other three 2-element sets can make an arbitrary choice ($2^3$ choices). Combining everything, we have $3^4 \cdot 4 \cdot 2^3$ which is $4! \cdot 108$. We'll now show $a_n = na_{n-1} = n! \cdot 108$ for $n \geq 5$. Suppose the representative of the whole set $S$ is $k$; there are $n$ choices for $k$. If $T$ is a subset of size at most $n-2$ containing $k$, then $S$ is the union of $T$ with two other non-empty subsets, and so $T$'s representative must be $k$. Now suppose $T$ is a subset of size $n-1$ containing $k$ and that its representative is $m \neq k$. $T$ has at least four elements, so it is the union of $\{m,k\}$ together with two other non-empty subsets. Thus $\{m,k\}$'s representative must be $m$, contradicting that we found earlier it must be $k$. We conclude that all subsets containing $k$ chose $k$ as their representative. Remove $k$ from consideration, and we reduce to the $n-1$ case. So $a_n = na_{n-1}$ as desired.
28.03.2014 14:27
Does the $108$ multiplier have an "intuitive" explanation? Thanks!
28.03.2014 17:47
I strongly doubt it. I called it a "nasty base case" for a reason. If the problem had the condition be "union of two non-empty subsets" instead, I believe the answer is just the more natural $n!$. When you do "union of three non-empty subsets" that still gives a way of doing sufficiently large $n$ the same way, but it also complicates small values of $n$ in some weird ways.
01.03.2016 22:57
We claim that the answer is $108\cdot2014!$. To prove this, we will first impose an ordering on the numbers. Let $a_1$ be the representative of $S$, $a_2$ be the representative of $S-\{a_1\}$, $a_3$ be the representative of $S-\{a_1,a_2\}$, and so on. We may without loss of generality suppose that $a_i=2015-i$ for all $i$ and multiply by $2014!$ in the end. Now, we will show that there is only 108 ways to choose the representatives of the remaining subsets. Let $S_k=\{1,2,\ldots,k\}$. Note that all subsets $T$ of $S_k$ containing $k$ with less than $k-1$ elements must have $k$ as their representative because $S_k-T$ has at least two elements and those elements can make two more nonempty subsets $B$ and $C$. Putting $T$, $B$, and $C$ into the condition, $T$ must have $k$ as its representative. Now we claim that for $k>4$ all subsets $T$ of $S_k$ containing $k$ must have $k$ as its representative. We have already taken care of the case where $|T|<k-1$, so now it suffices to prove it for $|T|=k-1$. Suppose for the sake of contradiction that $a\neq k$ is the representative of $T$. Then because $k>4$, $T'=T-\{a,k\}$ has at least two elements that can be split into two nonempty subsets $B$ and $C$. Putting $T$, $B$, and $C$ into the condition, we get a contradiction. Now the only cases remaining are the 3 element subsets of $S_4$ containing 4 and the 2 element subsets of $S_3$ containing 3. We claim that their representatives can be any element they contain, which means that there are $3^3\cdot2^2=108$ ways to choose representatives. Note that any three subsets of $T$ that have $T$ as their disjoint union will trivially satisfy the condition. Furthermore, if $T$ disjointly unions with two other subsets, then their disjoint union will either be $S_4$ with $\{4\}$ being one of the sets or contain a number greater than 4, and by what we have shown in the previous paragraphs the condition will be satisfied. Hence, the answer is $108\cdot2014!$
05.03.2016 21:52
Sorry but what is a disjoint union? The definition given here https://en.wikipedia.org/wiki/Disjoint_union doesn't really match the problem and the usual definition of union gives $2014!$ ways. Thanks!
14.02.2020 00:20
Let $x_n$ be the number of ways for $S=\{1, 2, ..., n\}$. First note that the problem's condition is equivalent to: if $X$ is a subset of $Y$ (both of which are subsets of $S$) with $|X|\le |Y|-2$, then the representative of $X$ is the representative of $Y$. Next, note that for $n=4$, there are 4 ways to choose the representative of $(1, 2, 3, 4)$, which fixes the representative all the 2-element subsets which contain that element. The one element subsets have fixed representatives, but the remaining subsets can have whatever representative they want, so $x_4=4\cdot 2^3\cdot 3^4=108\cdot 4!$. Now, for the inductive step, suppose $n\ge 5$; then, first choose the representative of $(1, 2, ..., n)$, which there are $n$ ways for, and WLOG let it be $n$. Then, all the subsets with size at most $n-2$ and contain $n$ have representative $n$. Now, consider a subset $X$ that has size $n-1$ and contains $n$. Then, if its representative is $k$, then the representative of $(n, k)$ is also $k$, since $2\le n-3$. But the representative of $(n, k)$ is $n$, so thus $k=n$, meaning all subsets of size $n-1$ has representative $n$. This means all subsets containing $n$ has representative $n$, so now it just reduces to the $n-1$ case. Thus, $x_n=nx_{n-1}$ for $n\ge 5$, so $x_n=108\cdot n!$.
10.09.2020 19:28
I like this problem Denote the requisite number for $n$ by $a_n$ . First we do the case $n=4.$ .First note that all the single element sets have their elements as representatives . Next WLOG the set $\{1,2, \dots ,i\}$ for all $1\leq i \leq 4$ has representative $\{i\}$ . (We will multiply by $4!$ later . Next note that all the subsets of size $\leq 2$ , containing $4$ , must have representative $4$. Next note that we have the freedom to choose representatives of the sets $\{13\}$ , $\{23\}$ , $\{124\}$ , $\{134\}$ , $\{234\}$ , which amounts to an answer of $3^3\times 2^2=108$ . Hence $a_4=108 \times 4!$ We now proceed by strong induction for $n\geq 5.$ Using the same adjustment as above (ie let $n$ represent $\{1,2 \dots , n\}$ , we note that we again have that all subsets of size atmost $n-2$ , containing $n$ must have $n$ as their representative. (This is clear for sets of size $n-2$ and then we can induct down .) . Next for subsets of size $n-1$ containing $n$ , we claim that they must have representative $n$ . Otherwise let the representative be $x$ and split the set into $\{n,x\}$ and $\{B\}$ and $\{C\}$ . Note that $B,C$ have atleast one element as $(n-1)-2 \geq 2$ . Next note that the representative must be the same as that of $\{n,x\}$ which is in turn $n$ . This reduces to the $(n-1)$ case and we have $a_n=na_{n-1}.$ We have a final answer of $108 \times 2014!$
20.09.2020 08:08
Solved with eisirrational. We will solve the problem with 2014 replaced by $n$. let $a_n$ be the number of ways. Define $\text{rep } A$ to be the representative of a set $A$. Suppose $n\ge 5$. Let $k=\text{rep } \{1,\ldots,n\}$. Claim: Every subset of $T\subseteq S$ with at most $n-2$ elements that contains $k$ has rep $k$. Proof. Apply the condition to some partition $\{T, B, C\}$ of $S$ to conclude $\text{rep } k \in \{\text{rep } T, \text{rep } B, \text{rep } C\}$. But since $k\not \in B$ and $k\not \in C$, we must have $k = \text{rep } T$. $\blacksquare$ Claim: Every $(n-1)$-subset of $S$ that contains $k$ has rep equal to $k$. Proof. WLOG $k\in \{1,\ldots,n-1\}$. Suppose $\text{rep }\{1,\ldots,n-1\}=k'\not = k$. Apply the condition to some partition $\{ \{k,k'\}, B, C\}$ of $S$ to conclude \[ k \in \{ \text{rep }\{k,k'\}, \ \text{rep } B, \ \text{rep } C\}.\]But since $k\not \in B$ and $k\not \in C$, we must have $k=\text{rep } \{k,k'\}$. But now apply the condition to some partition $\{\{k,k'\}, B',C'\}$ of $\{1,\ldots,n-1\}$ to conclude \[ k' \in \{ \text{rep } \{k,k'\}, \ \text{rep } B', \text{rep } C' \}. \](Note that this step requires $n-1\ge 4$.) Since $k'\not \in B'$ and $k'\not \in C'$, we must have $k' = \text{rep }\{k,k'\}$. This is a contradiction. $\blacksquare$ The above two claims prove that $k$ is the rep of any set that contains $k$. So we can ignore $k$ from $S$ and delete all subsets of $S$ that contain $k$, since their reps are determined to be $k$. This reduces the problem to $S=\{1,\ldots, n\} \setminus \{k\}$ entirely. Since there were $n$ ways to choose $k$, we have $a_n = na_{n-1}$ for $n\ge 5$. Now we compute $a_4$, i.e. for subsets of $\{1,2,3,4\}$. The rep of a singletons is itself. The condition does not restrain 3-subsets in any way, so there are $3^4$ ways for them. Suppose $k=\text{rep } \{1,2,3,4\}$; there are 4 choices for $k$, WLOG $k=1$. By the first lemma, $\text{rep } \{1,2\} = \text{rep } \{1,3\} = \text{rep } \{1,4\} = 1$. It is easy to check that any assignment of reps for the other 3 works. In conclusion, $a_4 = 3^4\cdot 4\cdot 2^3 = 2592 = 108\cdot 4!$. Therefore, $a_n=108\cdot n!$.
23.11.2020 18:51
Funny problem. Let $a_n$ denote the answer to the problem when $2014$ is replaced by $n.$ $\textbf{Lemma: }$ If the representative of $\{1,2,\dots,n\}$ is $k,$ then $k$ is also the representative of any set $S\in\{1,2,\dots,n\}$ satisfying $1\le|S|\le n-2$ and $k\in S.$ $\emph{Proof: }$ The claim is obvious if $|S|=1,$ so assume $2\le|S|\le n-2.$ Notice that for any such $S$, there exist non-empty sets $T,U$ such that $S\sqcup T\sqcup U=\{1,2,\dots,n\}.$ By the given condition, this implies that $k$ is the representative of one of $S,T,U.$ But $k\not\in T,U,$ so $k$ must be the representative of $S.$ $\blacksquare$ $\textbf{Claim: }$ $a_4=108\cdot 4!$ $\emph{Proof: }$ Suppose WLOG that the representative of $\{1,2,3,4\}$ is $1;$ we will multiply our final answer by $4.$ Then, by our lemma, the representative of $\{1,2\},\{1,3\},$ and $\{1,4\}$ must also be $1.$ For each of the other sets, it is easy to see that our choice of representative is independent of other choices. Therefore $a_4=4\cdot 1^4\cdot 2^3\cdot 3^4=108\cdot 4!,$ as desired. $\blacksquare$ $\textbf{Claim: }$ For all $n\ge 5,$ we have $a_n=na_{n-1}$ $\emph{Proof: }$ Suppose WLOG that the representative of $\{1,2,\dots,n\}$ is $1;$ we will multiply our final answer by $n.$ Then, by our lemma, the representative of all $S\in\{1,2,\dots,n\}$ with $1\le |S|\le n-2$ and $1\in S$ must be $1.$ Now consider any set of size $n-1$ containing $1,$ say $\{1,2,\dots,n-1\}.$ If the representative of this set is $m\ne 1,$ then our lemma says that the representative of $\{1,m\}$ must be $m,$ contradiction. Thus, the representative of all subsets of $\{1,2,\dots,n\}$ containing $1$ is $1.$ Since no set containing $1$ is a subset of a set not containing $1,$ we can assign representatives to all other subsets independently. There are exactly $a_{n-1}$ ways to do this, so $a_n=na_{n-1}.$ $\blacksquare$ It follows that the answer is $a_{2014}=\boxed{108\cdot 2014!}$
30.03.2021 23:30
Let $a_n$ denote the desired value for $S=\{ 1,2,3,...,n \}$. We claim $a_{2014}=108 \times 2014!$. We will prove this by induction. Basis: We have $a_4=108 \times 4!$ Inductive step: Let us prove $a_k=ka_{k-1}$ Let $r$ be the representative of $S$. Let $A \subset S$ where $|A| \leq k-2$ and $r \in A$. Clearly $S$ is the union of $A$ and two other subsets so $r$ is the representative of $A$. Now, let $B \subset S$ where $|B|=k-1$ and $r \in B$. Suppose for the sake of contradiction $B$'s representative is $m \not = r$. Clearly, $B$ can be partitioned into three substets, one of which containing both $m$ and $r$. Such a set would have representative $r$ and not $m$ so $B$ cannot have representative $m$. Contradiction. Thus, all sets which contain $r$ must have representative $r$. If we remove $r$ we get the $k-1$ case and there are $k$ ways to choose $r$. So, $a_k=ka_{k-1}$ completing the induction. This implies the result.
14.01.2023 22:30
We find a formula for general $n$. Let $k$ be the signature of $[n]$. Then, observe that all sets that contain $k$ with cardinality at most $n-2$ must have signature $k$. For the sets containing $k$ with cardinality $n-1$, assume for the sake of contradiction that there exists a subset $A$ that has signature not equal to $k$, say equal to $a$. Now, consider the condition $$\{k, a\} \sqcup B \sqcup C = A.$$Because $a \not \in B$ and $a \not \in C$, $a$ cannot be the signature of $A$, contradiction. Thus, in these cases, we can remove all subsets that contain $k$ and reduce the condition to the remaining $2^{n-1}$ subsets; because there are $n$ ways to choose this signature $k$, we have $a_n = na_{n-1}$ for all $n \geq 5$. On the other hand, $a_4 = 4! \cdot 108$ can be determined easily, so $a_{2014} = 108 \cdot 2014!.$
02.04.2023 12:21
We will show that in general for $S=\{1,2\ldots,n\}, n\ge 4$, the answer is: $108\cdot n!$. We now use induction on the largest element. Let $A_k$ be the number of ways to do the assignments for $n=k$ and $R(T)$ be the representive of $T\subseteq S$. Consider the set $T=\{1,2,\ldots,k,k+1\}$ and let $R(T)=r$. Then clearly $R(T')=r$ for all $T'$ such that $|T'|\le k-1$ and $r\in T'$.. Now consider any subset of size $|T'|=k$ that contains $r$, say it misses element $1\le a\le k+1$. Then \begin{align*} T'&=\{1,2,\ldots,a-1,a+1,\ldots,r,\ldots,k+1\}\\ &=\{1\}\cup\{2\}\cup\{3,4,\ldots,a-1,a+1,\ldots,r,\ldots,k+1\}\\ &=\{3\}\cup\{4\}\cup\{1,2,5\ldots,a-1,a+1,\ldots,r\ldots,k+1\}. \end{align*}which requires $k+1\ge 5$. As the size of the last two sets is less than $k$ it must have representative $r$. Now $R(T')$ can only be one of $1,2,3,4,r$, but as $T'$ has only one representative, it cannot be $3$ or $4$ because of the first equality and not $1$ or $2$ because of the second, so in fact $R(T)=r$ as well. Therefore, as we have $k+1$ choices for $r$, we have $A_{k+1}=(k+1)A_k$ for all $k\ge 4$. For the base case $n=4$ notice that $R$ of a single element is itself, so we immediately have $3^4$ choices for the representative of subsets of size $3$. Then as we have seen earlier, each of the $4$ choices for the largest subset uniquely determine the representatives of the subsets of size $2$ that contain the representative of the largest subset, and it is easy to check that any assignement to the other size 3 subsets works out. Therefore, $A_4=3^4\cdot 2^3\cdot 4=108\cdot 4!$, meaning the answer is $A_{2014}= 108\cdot 2014!$.
07.08.2023 19:25
We claim that the answer is $108\cdot 2014!$. Lemma: Note that a set {1,2,...,n} with representative k means that all subsets $s_s:1\le|s_s|\le n-2$ containing k must have representative k; otherwise, combining that subset $s_i$ without representative k and two other subsets (which don't have k) which finish the {1,2,..,n} set, altogether they violate the given condition (none of them has representative k). $\square$ Let $a_n$ be the number of ways we can assign representatives. We'll prove that $a_n=na_{n-1}\forall n\ge 5$, from which it follows that $a_n=a_4\frac{n!}{4!}108=108(n!)$ (will prove $a_4=4!$). First, n=4: WLOG representative of {1,2,3,4} is 1, then {1,2},{1,3},{1,4} must all have representative 1. The rest of them can be assigned arbitrarily, since we know any assignment will satisfy the condition for {1,2,3,4}, while subsets of size three obviously work (condition can only apply for some {j,k,l}={j},{k},{l}), whence there are $4(2^3)3^4=108\cdot 4!$ ways. Next, suppose WLOG the representative of {1,2,...,n} is 1; we'll multiply our ans by n at the end. Now, if any set containing 1 with size n-1 has a representative $r\ne 1$, then by the lemma it implies that the representative of {1,r} must be r, contradiction since it should be 1. Hence all subsets containing 1 must have 1 as the representative. Now notice we can ignore the condition applied to any set containing 1 since one of the three subsets in the condition must have 1 and consequently have representative 1, so there is never any contradiction. Hence we have reduced the problem to looking at {2,3,...,n}, which is just $a_{n-1}$. The answer follows.
10.08.2023 08:13
The answer is $108 \cdot 2014!$ and in general $108 \cdot n!$. We proceed with induction. The base case is $n = 4$. There are 4 ways to pick the representative of $\{1,2,3,4\}$. For subsets with 3 elements, we can freely choose any one of the 3 elements to be representatives. For the subsets with 2 elements, we are forced to pick 1 as the representative if they contain 1 and can freely pick otherwise. Thus, the answer for $n = 4$ is $4 \cdot 3^4 \cdot 2^3 = 2592 = 108 \cdot 4!$ as desired. Assume that the claim is true for $n = k$. Consider the set $S = \{1,2, \ldots ,k+1\}$. There are $k+1$ ways to pick the representative for $S$, WLOG it is $1$. The key observation that we will prove for a general $n$ is that every subset of $S' = \{1,2, \ldots ,n\}$ that contains $1$ needs to have representative $1$. Proof: First, note that if a subset $T$ containing $1$ has at most $n-2$ elements then by letting $A = T$ and $B$ and $C$ be sets such that $A \cup B \cup C = S$ ($B$ and $C$ exist since $|T| \leq n-2$) it follows that the representative of $T$ must be $1$ because $B$ and $C$ don't contain $1$. Now consider the case when $|T| = n-1$. WLOG let $T = \{1,2, \ldots ,n-1\}$. For the sake of contradiction let the representative of $T$ be WLOG $2 \neq 1$. Now WLOG let $A = \{1,2, \ldots , n-2\}$, $B = \{n-1\}$ and $C = \{n\}$. It follows that the representative of $A$ must be $2$, but since $|A| \leq n-2$ the representative must be $1$, a contradiction. Finish: Once we pick the representative for $S = \{1,2, \ldots ,k+1\}$ we just remove it and there are $108 \cdot k!$ ways to work with the other $k$ elements. Thus the number of ways is $(k+1) \cdot 108 \cdot k! = 108 \cdot (k+1)!$ and our induction is complete.
25.11.2023 09:08
Let $a_n$ be the number of assignments for the set $\{1,2,\dots,n\}$. We will prove $a_n = n! \cdot 108$ using induction. For the base case, we will manually calculate $a_4$: The $1$-element subsets must have their representative fixed, and the $3$-element subsets cannot be combined with two other non-empty sets, and the only way it can be a disjoint union is already covered, so we have $81$ choices for the $3$-element subsets. If we choose a representative for the $4$-element subset, $3$ of the two-element subsets are fixed while the other $3$ have $2$ choices each. All of this evaluates to \[3^4 \cdot 4 \cdot 2^3 = 4! \cdot 108.\] For $n \ge 5$, suppose $k$ is the representative of $S$. There are $n$ choices for the value of $k$. Any subset of at most $n-2$ elements containing $k$ can be combined with two other nonempty sets to create $S$, meaning those subsets will have representative $k$. Now, suppose a subset with $n-1$ elements containing $k$ has representative $r \neq k$. Because $n-1 \ge 4$, this subset is the disjoint union of $\{k,r\}$ and two other nonempty sets. This means that $r$ is the representative of $\{k,r\}$ but we already established that all subsets with less than $n-2$ elements containing $k$ have representative $k$. This contradicts our initial assumption that $r \neq k$, meaning that all subsets containing $k$ will have representative $k$. Thus, we can simply remove $k$ from the picture and have reduced it to the $n-1$ case, as well as showing that \[a_n = na_{n-1}.\] Applying this repeatedly yields our desired formula for $a_n$ and plugging in $2014$ gives $\boxed{2014! \cdot 108}$.
07.01.2024 20:07
My proof is similar to those above with a different construction for the edge case. We claim the answer is $108 \cdot 2014!$ Let $a_n$ be the number of ways to assign representatives to the non-empty subsets of $S_n = \{1, 2, \dots, n \}$ subject to the conditions of the problem. We will prove $a_n = 108 \cdot n!$ for integers $n \ge 4$, giving the answer upon substituting $n = 2014.$ It suffices to show that $a_4 = 108 \cdot 4!$ and $a_k = k a_{k - 1}$ for integers $k \ge 5$. For brevity, define $\Delta(X \subseteq S_n)$ for some fixed $n$ as the representative of $X$. To show $a_4 = 108 \cdot 4!$, without loss of generality assume $\Delta(S_4) = 1$. When $|X| = 1$, the representative is fixed. But when $|X| = 2$, observe that it can be unified with two disjoint $1$-element subsets, so if $1 \in X$ we have $\Delta(X) = 1$. Otherwise, there are two options for the representative when $1 \not \in X$. There are $3$ subsets satisfying this property, being $\{2, 3 \}, \{2, 4 \}, \{3, 4 \}$, yielding $2^3$. Now if $|X| = 3$, the representative we choose does not matter, giving $3^4$. At the beginning, we assumed $\Delta(S_4) = 1$ which can be interchanged with any $1, 2, 3, 4$. Collectively we obtain $a_4 = 4 \cdot 2^3 \cdot 3^4 = 108 \cdot 4!$ as desired. Now we prove $a_k = k a_{k - 1}$ for nonnegative integers $k \ge 5$. Again, without loss of generality, assume $\Delta(S_k) = 1$. We claim that if $1 \in X$, we have $\Delta(X) = 1$. Observe that when $|X| \le k - 2$, we have enough "leeway" to fit some subsets, say $P$ and $Q$ such that the disjoint union of $X, P, Q$ is $S_k$, forcing $\Delta(X) = 1$. Call this result (1). But when $|X| = k - 1$, this reasoning fails as $P$ and $Q$ must be non-empty. For the sake of contradiction, assume $\Delta(X) = t \ne 1$. Since $k \ge 5 \implies |X| \ge 4$, we can choose two integers $u, v \in X$ such that $u, v \ne 1, t$. Define $Y$ as the set $X$ when $u, v$ are removed. Then $\{u \}, \{ v \}, Y$ are disjoint, and their union is $X$, forcing $\Delta(Y) = t$. But $|Y| = |X| - 2 = k - 3 \le k - 2$, which by result (1) makes $\Delta(Y) = 1$. Contradiction. Therefore, $\Delta(X) = 1$. Now that we know when $1 \in X$, we have $\Delta(X) = 1$, we can ignore $1$ and we are left with $a_{k - 1}$ ways to assign representatives to the rest of the subsets. However, $1$ is interchangable with any integer $1, 2, \dots, k$, thus the recursion $a_k = ka_{k - 1}$ holds as claimed. Our proof is complete.
12.01.2024 04:16
We claim that the answer is $27 \cdot 4 \cdot 2014!$. We will prove a stronger result that, for $n \ge 5$, we can assign the representative to the set $S$ in $27 \cdot 4 \cdot n!$ ways. Note that: $$a_1 = 1, a_2 = 2, a_3 = 24, a_4 = 27$$ Now, for $n \ge 5$, we can choose the representative of the set $S = {1, 2, \cdots, n}$ in $n$ ways. Thus, we must have (from the 3 disjoint subsets condition) that, for every $T \subseteq S$ that contains $1$ and $|T| \le n-2$, its representative must be $1$. Now, consider a subset $G \subseteq S$ that contains $1$ and $|G| = n-1$. We will prove that its representative is $1$. For the sake of contradiction, assume that its representative is $k$, where $k \neq 1$. But, if we partition $G$ into $3$ disjoint subsets such that: $A = \{1, k \}$, $B = \{b_1, b_2, \cdots, b_s \}$, $C = \{c_1, c_2, \cdots, c_{n-3-b} \} $, then notice that $k$ can't be the representative of $A$, as $1$ is its representative. Also, $k$ can't be the representative of $B$ and $C$ as they don't contain the number $k$. Thus, contradiction. Hence, $1$ must be the representative of $G$. Hence, we must have: $a_n = n a_{n-1}$ Hence, we must have $a_n = 108 \cdot n!$, for all natural numbers $n \ge 5$.
15.01.2024 06:58
The answer is $108 \cdot 2014!$. $\newline$ Let $f(n)$ be the number of ways to represent the subsets of $S$, where $n = |S|$. We will use downwards induction to show that $f(n)$ for $n > 4$ is equal to $n! \cdot 108$. $\newline$ Our base case is $n = 4$. There are $4$ choices for the representative for $S$, and for each set of size $3$, there are no restrictions on the representative(since each are the disjoint union of $3$ distinct elements $\newline$ For sets of size $2$ that have element $r$ in them, their representative must be $r$. This is because $S$ must be the disjoint union of a set of size $2$ and two sets of size $1$, since the sets of size $1$ don't contain $r$. Size $2$ sets not containing $r$ have no restrictions, so our answer for the base case is $4 \cdot 3^4 \cdot 2^3 = 108 \cdot 4!$ as desired. $\newline$ Inductive Step: $\newline$ We assume that $f(n-1) = 108 \cdot (n-1)!$ Let the representative of $S$ be $r$ again. We can prove that if $|X| \leq n - 2$($X \subseteq S$), and $r \in X$ then the representative of $|X|$ is also $r$. We can split $S$ into $3$ disjoint sets, $X$, $Y$, $Z$, with $X$ containing $r$. It follows that $r$ must be the representative of $X$, as the disjoint union of the three sets gives $S$, and the only set containing $r$ is $X$. $\newline$ We can also show that $|W| = n - 1$ has representative $r$ as well, if $r$ is in $W$. FTSOC, assume that the representative of $W$ is $s$, not $r$. Then the disjoint union of $\{r, s\}$, $T$, $U$ is $W$, so $W$ cannot have representative $s$, it must have representative $r$. $\newline$ Thus, all subsets containing $r$ have representative $r$. We can now remove this element from all sets, and we are left with $f(n-1)$. Since there were $n$ choices for $r$, we have $f(n) = nf(n-1) = 108 \cdot n!$. $\newline$ Now, plugging $2014$ for $n$ gives us $f(2014) = 108 \cdot 2014!$, so we are finished. $\blacksquare$
04.03.2024 00:32
Very AIME-esque. For $n \geq 6$, let $a$ be the representative of the universe, then clearly $a$ is the representative of any set of size $\leq n-2$ containing by splitting $n$ into that set and two singletons. Then for any set of size $n - 1$, split it twice into a set of size $n - 3$ containing $a$ and two singletons, so that the two singletons in the two splitting don't match. It follows that $a$ is also its representative. Thus $a$ is the representative of any set containing $a$, so we recognize the structure and reduce down. For $n = 5$, by the same logic, it follows that $a$ represents all sets of size $\leq 3$ containing $a$. For any set of size $4$, WLOG it is $a, b, c, d$, we can pick the splittings $(a, b), c, d$, then $(a, c), b, d$, then $(a, d), b, c$. It follows that the representative of this set is $a$, so the same logic applies and we can recognize the structure and reduce down. For $n = 4$, by analysis, it follows that if $a$ is the representative of the universe, any size $3$ set can freely choose its representative, any size $2$ set containing $a$ is represented by $a$ and otherwise it is free to choose. Hence there are $3^4 \cdot 2^3$ options here. Now reincorporating the choice of $a$ in each step, we get a total of $n! \cdot 108$ as desired.
26.05.2024 20:32
Denote the number of ways to do so for each n by $a_n$. We will firstly check the case n = 4. Obviously all the single element sets have their elements as representatives. Now lets take the set $\{1,2, \cdots ,i\}$ for all $1\leq i \leq 4$ which has i as representative. The number we get for ways should be multiplied with 4! because of this. Now we notice that all the subsets of size $\leq 2$ which have 4 in them, must have 4 as representative. Now we can choose representatives of the sets $\{13\}$, $\{23\}$, $\{124\}$, $\{134\}$, $\{234\}$, which totally gives us an answer of $3^3.2^2=108$ $\Rightarrow$ $a_4=108.4!$ Now we would want to prove that $a_n=na_{n-1}$ by induction. Let $x$ be the representative of S. Let $A \subset S$ where $|A| \leq n-2$ and $x \in A$. Now by definition we have that $S$ is the union of $A$ and two more subsets, which means $x$ is the representative of $A$. Now, let $B \subset S$, $|B|=n-1$ and $x \in B$. Now let $B$'s representative is $y \not = x$. But now $B$ can be tiled into three subsets, one of which has $y$ and $x$ in it. This set will have a representative $x$ and not $y$ $\Rightarrow$ $B$ cant have representative $y$, which is now impossible by the claim $\Rightarrow$ each set that has $x$ in it, must have $x$ for its representative. Now if we delete $x$ we get the $a_{n-1}$ case and there are $n$ ways to choose $x$ $\Rightarrow$ $a_n=na_{n-1}$ which finishes the induction. So now for $a_{2014}$ we get the final answer of $a_{2014} = 2014!.108$, by this recurrence.