Maths Olympiad Prep

Library / /482 of 520

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it

Let m,n2m, n \geqslant 2 be integers, let XX be a set with nn elements, and let X1,X2,,XmX_{1}, X_{2}, \ldots, X_{m} be pairwise distinct non-empty, not necessarily disjoint subsets of XX. A function f:X{1,2,,n+1}f: X \rightarrow \{1,2, \ldots, n+1\} is called nice if there exists an index kk such that
xXkf(x)>xXif(x) for all ik \sum_{x \in X_{k}} f(x)>\sum_{x \in X_{i}} f(x) \text { for all } i \neq k
Prove that the number of nice functions is at least nnn^{n}. (Germany)

Solution

For a subset YXY \subseteq X, we write f(Y)f(Y) for yYf(y)\sum_{y \in Y} f(y). Note that a function f:X{1,,n+1}f: X \rightarrow \{1, \ldots, n+1\} is nice, if and only if f(Xi)f\left(X_{i}\right) is maximized by a unique index i{1,,m}i \in \{1, \ldots, m\}. We will first investigate the set F\mathcal{F} of functions f:X{1,,n}f: X \rightarrow \{1, \ldots, n\}; note that F=nn|\mathcal{F}|=n^{n}. For every function fFf \in \mathcal{F}, define a corresponding function f+:X{1,2,,n+1}f^{+}: X \rightarrow \{1,2, \ldots, n+1\} in the following way: Pick some set XlX_{l} that maximizes the value f(Xl)f\left(X_{l}\right).

- For all xXlx \in X_{l}, define f+(x)=f(x)+1f^{+}(x)=f(x)+1.
- For all xX\Xlx \in X \backslash X_{l}, define f+(x)=f(x)f^{+}(x)=f(x).

Claim. The resulting function f+f^{+} is nice.

Proof. Note that f+(Xi)=f(Xi)+XiXlf^{+}\left(X_{i}\right)=f\left(X_{i}\right)+\left|X_{i} \cap X_{l}\right| holds for all XiX_{i}. We show that f+(Xi)f^{+}\left(X_{i}\right) is maximized at the unique index i=li=l. Hence consider some arbitrary index jlj \neq l. Then XlXjX_{l} \subset X_{j} is impossible, as this would imply f(Xj)>f(Xl)f\left(X_{j}\right)>f\left(X_{l}\right) and thereby contradict the choice of set XlX_{l}; this in particular yields Xl>XjXl\left|X_{l}\right|>\left|X_{j} \cap X_{l}\right|.

f+(Xl)=f(Xl)+Xlf(Xj)+Xl>f(Xj)+XjXl=f+(Xj) f^{+}\left(X_{l}\right)=f\left(X_{l}\right)+\left|X_{l}\right| \geqslant f\left(X_{j}\right)+\left|X_{l}\right|>f\left(X_{j}\right)+\left|X_{j} \cap X_{l}\right|=f^{+}\left(X_{j}\right)

The first inequality follows since XlX_{l} was chosen to maximize the value f(Xl)f\left(X_{l}\right). The second (strict) inequality follows from Xl>XjXl\left|X_{l}\right|>\left|X_{j} \cap X_{l}\right| as observed above. This completes the proof of the claim.

Next observe that function ff can be uniquely reconstructed from f+f^{+}: the claim yields that f+f^{+} has a unique maximizer XlX_{l}, and by decreasing the value of f+f^{+} on XlX_{l} by 1, we get we can fully determine the values of ff. As each of the nnn^{n} functions fFf \in \mathcal{F} yields a (unique) corresponding nice function f+:X{1,2,,n+1}f^{+}: X \rightarrow \{1,2, \ldots, n+1\}, the proof is complete.

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