Maths Olympiad Prep

Library / /94 of 105

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Let S={1,2,,n}S=\{1,2, \ldots, n\}, and let TT be the set consisting of all nonempty subsets of SS. The function f:TSf: T \rightarrow S is "garish" if there do not exist sets A,BTA, B \in T such that AA is a proper subset of BB and f(A)=f(B)f(A)=f(B). Determine, with proof, how many garish functions exist.

Solutions — 2

Solution 1

Solution:

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

Let ff be garish; our crucial observation is the following: If a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} are the elements of SS in some order, we shall say that this ordering "produces" a sequence of nn values f({a1}),f({a1,a2}),,f({a1,a2,,an})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 nn possible values for ff, namely 1,2,,n1,2, \ldots, n, so any produced sequence consists of exactly these in some order.

Now choose any integer kk, 1kn1 \leq k \leq n. We will show that ff has the same value on all kk-element sets. We can assume k<nk<n (otherwise there is only one kk-element set). First consider any two sets that differ by at most one element; let them be {a1,a2,,ak}\{a_{1}, a_{2}, \ldots, a_{k}\} and {a1,a2,,ak1,b}\{a_{1}, a_{2}, \ldots, a_{k-1}, b\}. Assume akba_{k} \neq b. Let the remaining elements of SS (if there are any) be ak+2,ak+3,,ana_{k+2}, a_{k+3}, \ldots, a_{n} in any order. Consider the sequences produced from the two orderings a1,a2,,ak1,ak,b,ak+2,,ana_{1}, a_{2}, \ldots, a_{k-1}, a_{k}, b, a_{k+2}, \ldots, a_{n} and a1,a2,,ak1,b,ak,ak+2,,ana_{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 SS exactly once. But these two sequences are identical except that the first has f({a1,,ak})f\left(\{a_{1}, \ldots, a_{k}\}\right) where the second has f({a1,,ak1,b})f\left(\{a_{1}, \ldots, a_{k-1}, b\}\right), so we conclude that these two values of ff are identical. Also, if ak=ba_{k}=b, then the two values are equal (trivially).

This shows that ff has the same value on two kk-element sets differing by 1\leq 1 element. Now if {a1,,ak}\{a_{1}, \ldots, a_{k}\} and {b1,,bk}\{b_{1}, \ldots, b_{k}\} are any two sets in TT, we have (applying this repeatedly) that
f({a1,a2,,ak})=f({b1,a2,,ak})=f({b1,b2,a3,,ak})==f({b1,b2,,bk}). 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 ff is constant over all kk-element sets. Thus we can define the function g:SSg: S \rightarrow S by letting g(k)g(k) be the value of ff on any kk-element set, and gg uniquely determines ff since f(A)=g(A)f(A)=g(|A|) for all ATA \in T. Moreover, if g(k)=g(l)g(k)=g(l) for some k<lk<l, then letting A={1,2,,k},B={1,2,,l}A=\{1,2, \ldots, k\}, B=\{1,2, \ldots, l\}, we have f(A)=f(B)f(A)=f(B), a contradiction since AA is a proper subset of BB. Thus, gg is one-one; but since it maps the finite set SS to itself, it is actually bijective. Thus all garish functions are indeed in the form claimed above.

Solution 2

Alternate Solution:

We observe that n!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 nn. In the base case n=1n=1, there is only one possible function, given by f({1})=1f(\{1\})=1, and it is garish. Now consider any nn, and suppose the statement is true for n1n-1. If ff is a garish function, let ak=f({1,2,,k})a_{k}=f(\{1,2, \ldots, k\}) for each k=1,2,,nk=1,2, \ldots, n. Then all aka_{k} are different: if ak=ala_{k}=a_{l} for some k<lk<l, then ff would not be garish, since {1,2,,k}\{1,2, \ldots, k\} is a proper subset of {1,2,,l}\{1,2, \ldots, l\}. Thus, the elements a1,,ana_{1}, \ldots, a_{n} equal 1,,n1, \ldots, n in some order. Partition TT into three subsets: let T1T_{1} consist of the nonempty subsets of {1,2,,n1}\{1,2, \ldots, n-1\}, let T2={S}T_{2}=\{S\}, and let T3T_{3} be the rest of TT (the proper subsets of SS containing nn). We claim that, if AT1A \in T_{1}, then f(A)=aAf(A)=a_{|A|}. This follows from the induction hypothesis. Formally, we first observe that f(A)anf(A) \neq a_{n} for AT1A \in T_{1} since ASA \subset S. Then, if we define h:{a1,a2,,an1}{1,2,,n1}h:\{a_{1}, a_{2}, \ldots, a_{n-1}\} \rightarrow \{1,2, \ldots, n-1\} by h(ak)=kh(a_{k})=k (and this is well-defined since a1,,an1a_{1}, \ldots, a_{n-1} are distinct), then the composite hfh \circ f is a garish function from T1T_{1} to {1,2,,n1}\{1,2, \ldots, n-1\}, so, by the induction hypothesis, it takes the same value on all kk-element sets; since hh is injective, ff takes the same value on all kk-element sets, as claimed. Also, if AT2A \in T_{2} (so A=SA=S) then f(A)=anf(A)=a_{n}, by assumption.

Now consider any set AT3A \in T_{3}; we have A<n|A|<n. We claim that f(A)=aAf(A)=a_{|A|}; this will be shown by strong downward induction on the cardinality A|A|. If A=n1|A|=n-1, then ASA \subset S and f(S)=anf(S)=a_{n}. On the other hand, the set A{n}A-\{n\} has n2n-2 elements and is contained in T1T_{1}; it certainly has subsets An2,An3,,A1A_{n-2}, A_{n-3}, \ldots, A_{1} of respective cardinalities n2,n3,,1n-2, n-3, \ldots, 1, all of which lie in T1T_{1}; thus, f(Ai)=aif(A_{i})=a_{i} from the previous paragraph. From this, garishness gives f(A)anf(A) \neq a_{n} and f(A)a1,a2,,an2f(A) \neq a_{1}, a_{2}, \ldots, a_{n-2}, so f(A)=an1f(A)=a_{n-1}.

The induction step is similar: suppose we have proven that, for all AT3A \in T_{3} with A>m|A|>m, f(A)=aAf(A)=a_{|A|}, and we wish to move to the case A=m|A|=m. By successively adding elements to AA, we can construct sets Am+1,Am+2,,An=SA_{m+1}, A_{m+2}, \ldots, A_{n}=S of respective cardinalities m+1,m+2,,nm+1, m+2, \ldots, n, which all lie in T3T_{3}, except for AnT2A_{n} \in T_{2}. Also, if m>1m>1, then A{n}A-\{n\} has m1m-1 elements and lies in T1T_{1}; repeatedly removing elements, we get sets Am1,Am2,,A1T1A_{m-1}, A_{m-2}, \ldots, A_{1} \in T_{1} of respective sizes m1,m2,,1m-1, m-2, \ldots, 1. So we have f(Ak)=akf(A_{k})=a_{k} for k>mk>m by the induction hypothesis, and f(Ak)=akf(A_{k})=a_{k} for k<mk<m because these sets lie in T1T_{1}. But each of the AkA_{k} either contains AA or is contained in AA, so f(A)f(A) cannot equal any of these aka_{k}; hence, it must equal ama_{m}, completing the induction step.

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

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 reproduced verbatim; metadata (topic, difficulty) added by this project.