Let \(m,n \geqslant 2\) be integers, let \(X\) be a set with \(n\) elements, and let \(X_1,X_2,\ldots,X_m\) be pairwise distinct non-empty, not necessary disjoint subset of \(X\). A function \(f \colon X \to \{1,2,\ldots,n+1\}\) is called nice if there exists an index \(k\) such that
\[\sum_{x \in X_k} f(x)>\sum_{x \in X_i} f(x) \quad \text{for all } i \ne k.\]
Prove that the number of nice functions is at least \(n^n\).For a subset \(Y \subseteq X\), we write \(f(Y)\) for \(\sum_{y \in Y} f(y)\). Note that a function \(f: X \rightarrow\) \(\{1, \ldots, n+1\}\) is nice, if and only if \(f\left(X_{i}\right)\) is maximized by a unique index \(i \in\{1, \ldots, m\}\).
We will first investigate the set \(\mathcal{F}\) of functions \(f: X \rightarrow\{1, \ldots, n\}\); note that \(|\mathcal{F}|=n^{n}\). For every function \(f \in \mathcal{F}\), define a corresponding function \(f^{+}: X \rightarrow\{1,2, \ldots, n+1\}\) in the following way: Pick some set \(X_{l}\) that maximizes the value \(f\left(X_{l}\right)\).
Claim: The resulting function \(f^{+}\) is nice.
Proof: Note that \(f^{+}\left(X_{i}\right)=f\left(X_{i}\right)+\left|X_{i} \cap X_{l}\right|\) holds for all \(X_{i}\). We show that \(f^{+}\left(X_{i}\right)\) is maximized at the unique index \(i=l\). Hence consider some arbitrary index \(j \neq l\). Then \(X_{l} \subset X_{j}\) is impossible, as this would imply \(f\left(X_{j}\right)>f\left(X_{l}\right)\) and thereby contradict the choice of set \(X_{l}\); this in particular yields \(\left|X_{l}\right|>\left|X_{j} \cap X_{l}\right|\).
\[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 \(X_{l}\) was chosen to maximize the value \(f\left(X_{l}\right)\). The second (strict) inequality follows from \(\left|X_{l}\right|>\left|X_{j} \cap X_{l}\right|\) as observed above. This completes the proof of the claim. \(\square\) Next observe that function \(f\) can be uniquely reconstructed from \(f^{+}\): the claim yields that \(f^{+}\) has a unique maximizer \(X_{l}\), and by decreasing the value of \(f^{+}\)on \(X_{l}\) by \(1\), we get we can fully determine the values of \(f\). As each of the \(n^{n}\) functions \(f \in \mathcal{F}\) yields a (unique) corresponding nice function \(f^{+}: X \rightarrow{1,2, \ldots, n+1}\), the proof is complete.