Berkeley Math Circle

Solution:

There are $n!$ such functions. If $g$ is any bijective map from $S$ to itself (i.e. a permutation of $S$), then the function $f: T \rightarrow S$ defined by $f(A)=g(|A|)$ (here $|A|$ is the cardinality of set $A$) is garish. To see this, just note that if $A$ is a proper subset of $B$, then $|A|<|B|$, so $g(|A|) \neq g(|B|)$. There are $n!$ possible choices of the map $g$, and all of them give different maps $f$ (this follows from the fact that every element of $S$ is the cardinality of some set in $T$), so we get $n!$ garish functions this way. We now wish to show that every garish function is of this form.

Let $f$ be garish; our crucial observation is the following: If $a_{1}, a_{2}, \ldots, a_{n}$ are the elements of $S$ in some order, we shall say that this ordering "produces" a sequence of $n$ values $f\left(\{a_{1}\}\right), f\left(\{a_{1}, a_{2}\}\right), \ldots, f\left(\{a_{1}, a_{2}, \ldots, a_{n}\}\right)$. These values are all different, since, of any two of these sets, one is properly contained in the other. But there are exactly $n$ possible values for $f$, namely $1,2, \ldots, n$, so any produced sequence consists of exactly these in some order.

Now choose any integer $k$, $1 \leq k \leq n$. We will show that $f$ has the same value on all $k$-element sets. We can assume $k<n$ (otherwise there is only one $k$-element set). First consider any two sets that differ by at most one element; let them be $\{a_{1}, a_{2}, \ldots, a_{k}\}$ and $\{a_{1}, a_{2}, \ldots, a_{k-1}, b\}$. Assume $a_{k} \neq b$. Let the remaining elements of $S$ (if there are any) be $a_{k+2}, a_{k+3}, \ldots, a_{n}$ in any order. Consider the sequences produced from the two orderings $a_{1}, a_{2}, \ldots, a_{k-1}, a_{k}, b, a_{k+2}, \ldots, a_{n}$ and $a_{1}, a_{2}, \ldots, a_{k-1}, b, a_{k}, a_{k+2}, \ldots, a_{n}$. From the above, each produced sequence contains every element of $S$ exactly once. But these two sequences are identical except that the first has $f\left(\{a_{1}, \ldots, a_{k}\}\right)$ where the second has $f\left(\{a_{1}, \ldots, a_{k-1}, b\}\right)$, so we conclude that these two values of $f$ are identical. Also, if $a_{k}=b$, then the two values are equal (trivially).

This shows that $f$ has the same value on two $k$-element sets differing by $\leq 1$ element. Now if $\{a_{1}, \ldots, a_{k}\}$ and $\{b_{1}, \ldots, b_{k}\}$ are any two sets in $T$, we have (applying this repeatedly) that
$$f\left(\{a_{1}, a_{2}, \ldots, a_{k}\}\right)=f\left(\{b_{1}, a_{2}, \ldots, a_{k}\}\right)=f\left(\{b_{1}, b_{2}, a_{3}, \ldots, a_{k}\}\right)=\cdots=f\left(\{b_{1}, b_{2}, \ldots, b_{k}\}\right).$$
So $f$ is constant over all $k$-element sets. Thus we can define the function $g: S \rightarrow S$ by letting $g(k)$ be the value of $f$ on any $k$-element set, and $g$ uniquely determines $f$ since $f(A)=g(|A|)$ for all $A \in T$. Moreover, if $g(k)=g(l)$ for some $k<l$, then letting $A=\{1,2, \ldots, k\}, B=\{1,2, \ldots, l\}$, we have $f(A)=f(B)$, a contradiction since $A$ is a proper subset of $B$. Thus, $g$ is one-one; but since it maps the finite set $S$ to itself, it is actually bijective. Thus all garish functions are indeed in the form claimed above.

Alternate Solution:

We observe that $n!$ garish functions can be constructed, precisely as described in the first solution, and we wish to show that all garish functions are of this form. We use induction on $n$. In the base case $n=1$, there is only one possible function, given by $f(\{1\})=1$, and it is garish. Now consider any $n$, and suppose the statement is true for $n-1$. If $f$ is a garish function, let $a_{k}=f(\{1,2, \ldots, k\})$ for each $k=1,2, \ldots, n$. Then all $a_{k}$ are different: if $a_{k}=a_{l}$ for some $k<l$, then $f$ would not be garish, since $\{1,2, \ldots, k\}$ is a proper subset of $\{1,2, \ldots, l\}$. Thus, the elements $a_{1}, \ldots, a_{n}$ equal $1, \ldots, n$ in some order. Partition $T$ into three subsets: let $T_{1}$ consist of the nonempty subsets of $\{1,2, \ldots, n-1\}$, let $T_{2}=\{S\}$, and let $T_{3}$ be the rest of $T$ (the proper subsets of $S$ containing $n$). We claim that, if $A \in T_{1}$, then $f(A)=a_{|A|}$. This follows from the induction hypothesis. Formally, we first observe that $f(A) \neq a_{n}$ for $A \in T_{1}$ since $A \subset S$. Then, if we define $h:\{a_{1}, a_{2}, \ldots, a_{n-1}\} \rightarrow \{1,2, \ldots, n-1\}$ by $h(a_{k})=k$ (and this is well-defined since $a_{1}, \ldots, a_{n-1}$ are distinct), then the composite $h \circ f$ is a garish function from $T_{1}$ to $\{1,2, \ldots, n-1\}$, so, by the induction hypothesis, it takes the same value on all $k$-element sets; since $h$ is injective, $f$ takes the same value on all $k$-element sets, as claimed. Also, if $A \in T_{2}$ (so $A=S$) then $f(A)=a_{n}$, by assumption.

Now consider any set $A \in T_{3}$; we have $|A|<n$. We claim that $f(A)=a_{|A|}$; this will be shown by strong downward induction on the cardinality $|A|$. If $|A|=n-1$, then $A \subset S$ and $f(S)=a_{n}$. On the other hand, the set $A-\{n\}$ has $n-2$ elements and is contained in $T_{1}$; it certainly has subsets $A_{n-2}, A_{n-3}, \ldots, A_{1}$ of respective cardinalities $n-2, n-3, \ldots, 1$, all of which lie in $T_{1}$; thus, $f(A_{i})=a_{i}$ from the previous paragraph. From this, garishness gives $f(A) \neq a_{n}$ and $f(A) \neq a_{1}, a_{2}, \ldots, a_{n-2}$, so $f(A)=a_{n-1}$.

The induction step is similar: suppose we have proven that, for all $A \in T_{3}$ with $|A|>m$, $f(A)=a_{|A|}$, and we wish to move to the case $|A|=m$. By successively adding elements to $A$, we can construct sets $A_{m+1}, A_{m+2}, \ldots, A_{n}=S$ of respective cardinalities $m+1, m+2, \ldots, n$, which all lie in $T_{3}$, except for $A_{n} \in T_{2}$. Also, if $m>1$, then $A-\{n\}$ has $m-1$ elements and lies in $T_{1}$; repeatedly removing elements, we get sets $A_{m-1}, A_{m-2}, \ldots, A_{1} \in T_{1}$ of respective sizes $m-1, m-2, \ldots, 1$. So we have $f(A_{k})=a_{k}$ for $k>m$ by the induction hypothesis, and $f(A_{k})=a_{k}$ for $k<m$ because these sets lie in $T_{1}$. But each of the $A_{k}$ either contains $A$ or is contained in $A$, so $f(A)$ cannot equal any of these $a_{k}$; hence, it must equal $a_{m}$, completing the induction step.

At this point, we have shown that $f(A)=a_{|A|}$ for each $A \in T$, and one sees as in the previous solution that $f(A)=g(|A|)$ for some bijective function $g: S \rightarrow S$, as needed.