Isn't this just isolation lemma?

It was also South Korea TST D1 P2. I will post my solution on the test Let $A=\{f\mid f:X\rightarrow \{1,2,\cdots,n\}\}$, and $B$ be a set of nice function. We will prove that there exists an injective map $\phi:A\rightarrow B$. If $f_0\in A$ is nice, then let $\phi(f_0)=f_0$. If $f_0\in A$ is not nice, then let $M_0=\max_{i=1,2,\cdots,m} \sum_{x\in X_i}f_0(x)$, and $P_0=\{i\mid \sum_{x\in X_i}f_0(x)=M_0\}$. It is obvious that $\lvert P_0\rvert \geq 2$, since $f_0$ is not nice. If $i,j$ are distinct element of $P_0$, then $\sum_{x\in X_i}f_0(x)=\sum_{x\in X_j}f_0(x)$ and $X_i\neq X_j$, so $X_i$ is not a subset of $X_j$ and vice versa. Hence, we can choose $p\in X_{i_0}$ such that there exists $i\in P_0$ which satisfies $p\notin X_i$, where $i_0$ is the smallest element in $P_0$. Let $p_0$ be the smallest $p$. Let $f_1(x)=\begin{cases}n+1&x=p_0\\f_0(x)&x\neq p_0\end{cases}$, and define $M_1, P_1, p_1$ simillarly. For $t\in P_1$, we can easily see that $t\in P_0$ and $p_0\in X_t$. So $P_1\subset P_0$, but $P_1\neq P_0$. $\therefore\lvert P_1\rvert <\lvert P_0\rvert$. Also, for $p\leq p_0$, if $p\in X_{i_0}$ then $p\in X_i$ for all $i\in P_1$, so $p_1>p_0$. If $\lvert P_i\rvert \geq 2$, we can proceed this step. And since $\lvert P_i\rvert$ strictly decreases as we repeat the step, there exists $k$ such that $\lvert P_k\rvert=1$. It implies that $f_k$ is nice, so let $\phi(f_0)=f_k$. To show that $\phi$ is injective, it suffices to show that $\phi$ is injective where $f_0$ is not nice. Let $\phi(f_0)=g$, then for some $s\in X$, $g(s)=n+1$. Let $S=\{s\mid g(s)=n+1\}$. It is easy to see that if $\lvert S\rvert=k$, then $g=f_k$. We will show the injectivity by following the inverse step of constructing $\phi(f_0)$. Let maximum element of $S$ be $u$. Then we can easily see that $f_k(x)=\begin{cases}n+1&x=u\\f_{k-1}(x)&x\neq u\end{cases}$ since $p_i<p_{i+1}$ for all $i$. Therefore, $p_{k-1}=u$. Let $N=\max_{i=1,2,\cdots,m} \sum_{x\in X_i}g(x)$. Clearly, if $\sum_{x\in X_i}g(x)=N$, then $u\in X_i$. Since $P_{k-1}\setminus P_k\neq \emptyset$, there exists $l\in P_{k-1}$ such that $u\notin X_l$. Therefore, when $N'=\max_{u\notin X_i} \sum_{x\in X_i}g(x)$, it is clear that $f_k(u)-f_{k-1}(u)=N-N'$. $\therefore f_{k-1}(u)=f_k(u)-N+N'$ Repeating this procedure, we can uniquely determine $f_{k-1}(x), f_{k-2}(x),\cdots, f_0(x)$. Therefore, $\phi$ is injective. And so, $\lvert B\rvert \geq \lvert A\rvert=n^n$, as desired. $\blacksquare$

CyclicISLscelesTrapezoid wrote: 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$. The question is: How can you get the 2022 ISL problems (or some of them) before it is officially released on the IMO official website?

@above: Through IMO training camp or TSTs.

For any function $g\colon\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$, let $k$ satisfy $$\sum_{x\in X_k}g(x)\geq\sum_{x\in X_i}f(x)$$for all $i$. Then, we claim that $f(x)=g(x)+1$ if $x\in X_k$ and $f(x)=g(x)$ if $x\not\in X_k$ works. If $f$ does not work, then there must exist $j$ such that $X_k\subseteq X_j$, so since $X_i\neq X_j$, we get $X_k\subset X_j$, which contradicts $\displaystyle\sum_{x\in X_k}\geq\sum_{x\in X_j}f(x)$. Now, for any function $f$ generated this way, $k$ can be determined uniquely, so subtracting $1$ from each $f(x)$ for $x$ in $X_k$ gives the unique function $g$. Therefore, there are at least $n^n$ distinct functions $f$ satisfying the conditions since there are $n^n$ possible $g$.

Let $\mathcal F, \mathcal G$ denote sets of nice functions and of functions $X\to \left\{ 1,2,\ldots ,n\right\}.$ For an arbitrary $g\in \mathcal G$ consider function $$f(x)= \begin{cases} g(x)+1, & x \in X_t\\g(x), & x\in X\backslash X_t\end{cases}$$for some $t.$ Note that $f$ is nice, if $|X_t|$ is maximal; thus we may pick the minimal $t,$ for which $f$ is nice. Observe then that by given $f$ we uniquely determine the initial function $g;$ hence by injection $|\mathcal F |\geq |\mathcal G |=n^n$ $\blacksquare$

Here is a different solution using the following lemma. Lemma: Given finite nonempty sets of integers $A_1, \dots A_n$, show that we can pick a set of integers $S$ such that For each integer $1 \le i \le n$, $A_i$ contains an element of $S$. For each $s \in S$, there exists an $i$ such that $s \in A_i$, but $t \notin A_i$ for any other $t \in S$ Proof: Pick the first set disjoint from $S$ and add one of its elements to $S$ (call this $x$). consider some other $s \in S$. If $x$ appears in all sets containing only $s$, then remove $s$, otherwise keep it. We see that this maintains the condition and decreases no. of sets disjoint from $S$, so repeating this algorithm we can construct such a set. Now, consider an arbitrary function $g: X \rightarrow \{2,3,\dots ,n+1\}$. Call one of the $X_k$ maximal if $\sum_{x \in X_k} g(x) \ge \sum_{x \in X_i} g(x)$ for all $i$. Let the maximal sets be $A_1, A_2, \dots, A_j$. Consider the sets $A_2 - A_1, \dots ,A_k - A_1$ (which are nonempty), using the lemma we may pick a set $S$ satisfying the conditions described. Define \[f(x) = \begin{cases} 1, & x \in S\\g(x), & x\notin S\end{cases} \]Observe that the maximum sum of $f$ is the same as $g$, and furthermore, it is achieved by only $A_1$, so $f$ is nice. Now, given such a function $f$, we may reconstruct $g$ as follows: for each $s \in S$, consider the all the sets $X_i$ with $X_i \cap S = \{s\}$, and take the one with the maximum sum. Since this sum must have been the sum of some maximal set of $A$ of $g$ for which $A \cap S = \{s\}$, and the maximum sum of $f$ is the same as that of $g$, we can determine $g(s)$. Since $g$ can be determined from $f$ (assuming such a $g$ exists), this map from $g$ to $f$ is injective and hence the number of nice functions is at least the number of working $g$, which is $n^n$.

Lol I tried inducting $m$ and wasted five hours thinking about $m = 3$ without progress (tbf I was distracted). Then I came back after a long hiatus and instead tried inducting $n$ and solved within ten minutes of inspecting $n = 3$. Just goes to show why jamming to music might not go so well with combo. Pick $f: X \to [n]$. Now we pick $\delta f: X \to [n+1]$ to increase all the elements in some maximal $X_m$ by $1$. Obviously $\delta f$ can be chosen as desired and furthermore it is clearly injective (it's inverse is easy to define), so we are done.

A very beautiful solution to this problem can be seen here: ISL 2022 C5, written by Drago sir. He explains the ideas which one can encounter while trying the problem (about 3 of them) and the third idea is the one that solves this problem. In my opinion, this solution is the most combinatorial solution on the thread because, it encapsulates two strong combinatorial ideas: one is injections and the other one is... well surprisingly, an algorithm! (Not one, infact two, one to construct the nice function from a function that is from $[n]$ to $[n]$ and another to recover the original function from a nice one.)

When seeing the solution, you may feel as if all this is unnecessary, and that the easier solution (ones on the thread) is better, but the reality is, the more ideas we get from a problem, it is better, because it helps us in developing stronger combinatorial intuition. Kudos to Drago sir for finding this solution!

Consider any function $g:X\to\{1,2,\dots,n\}$. We claim that there exists a value $i$ that satisfies the following: Let $f(x)=g(x)+1$ if $x\in X_i$ and $g(x)$ otherwise, then $f$ is nice. Let $S$ be a function on the ordered pair of functions and sets such that \[S(h,T)=\sum_{x \in T} h(x)\]then $S(f,X_k)=S(g,X_k)+|X_k\cap X_i|$. Evidently, if we choose $i$ to maximize $S(g,X_k)$ then \[S(f,X_i)=S(g,X_i)+|X_i|>S(g,X_k)+|X_k\cap X_i|=S(f,X_k)\]as desired. Now, two $g$s cannot result in the same $f$ because then the $X_i$ must both be the same and not be the same, contradiction. We have thus injected from $g$ to $f$, so the number of nice numbers is at least $n^n$.

very interesting problem, it is a little contrived unfortunately did not solve, attempted pie bash / induction for a time and this did not work oh well

First, denote $g(Y) \coloneq \sum_{x \in Y} f(x)$. We prove the following claim. Claim: There exists a bijection from functions $f \colon X \to \{1,2,\ldots,n\}$ to nice functions Take a function $f \colon X \to \{1,2,\ldots,n\}$. If $g(X_i)$ already has a unique maximum over all $i$, then we don't perform any changes as $f$ is already a nice function. However, if not, then pick an index $k$ where $g(X_k)$ is maximized (not necessarily strictly). We perturb $f$ with the following: $$f'(x)= \begin{cases} f(x)+1, & x \in X_k\\f(x), & x\notin X_k\end{cases}$$Now note that $g(X_k)$ is increased the most from this change as there cannot be another set $X_i$ that contains all $x \in X_k$ as either we have $X_i = X_k$ or $X_k \subset X_i$. The first case is contradicted by the problem conditions, while the second case contradicts the maximality of $g(X_k)$ before the change of $f(x)$. Therefore $g(X_k)$ must now be the unique maximum after the change, so we have successfully completed the bijection. Obviously there is $n^n$ functions $f \colon X \to \{1,2,\ldots,n\}$, so we are done.

Absolutely Beautiful Problem! Consider a function $g:X\rightarrow \{1,2,\dots,n\}$. Let $X_k$ be a subset such that, $$\sum_{x\in X_k}g(x)\geq \sum_{x\in X_i}f(x) \text{ for all }i\neq k$$Then the function $f(x)=\biggl\{ \begin{array}{lr} g(x)+1, & \text{if } x\in X_k\\ g(x),& \text{if } x\notin X_k \end{array}\biggl\}$ works because the sum of $X_k$ increase by $|X_k|$, more than any of the other subsets.

The way to approach this is by thinking what could $n^n$ mean in this case, basically it is really hard to try to find a way to determine all possible nice functions so the best way to go is to try to construct at least $n^n$ of such, in this case $n^n$ matters because its the number of functions $g \colon X \to \{1, 2, \ldots, n\}$ (lets call the set of all such functions to be $\mathcal G$), so fix one such function $g$ and let $k$ be the minimal index for which $\sum_{x \in X_k} g(x)$ is maximal, the reason behind this move is that since the inequality is strict there is some $+1$'s among the terms of the sum in order for it to be true, in fact they are related to the index $k$ we choose so among some basic things we can try, this should be one of them: $$f(x)=\begin{cases}g(x)&x \in X \backslash X_k\\g(x)+1&x \in X_k\end{cases}$$Now we claim that such $f$ is nice, indeed by consider any $i \ne k$ then we get: $$\sum_{x \in X_k} f(x)=\sum_{x \in X_k} g(x)+|X_k|>\sum_{x \in X_i} g(x)+|X_i \cap X_k|=\sum_{x \in X_i} f(x)$$Now to finish, note that from each $f$ we have we can construct its $g$ since first by considering all possible $\sum_{x \in X_i} f(x)-|X_i|$ we know what is the minimal index $k$ which makes the sum from earlier maximal and then it shows for which elements we have $f(x)=g(x)$ or $f(x)=g(x)+1$ making this $g$ well-defined entirely from $f$ so we have an injection which means that if $\mathcal F$ is the set of all nice functions then $|\mathcal F| \ge |\mathcal G|=n^n$ thus we are done .

The number of functions $g:X \to \{1, 2, \dots, n\}$ is exactly $n^n$, thus it suffices to prove a bijection between nice functions and the functions $g$. Let $X_j$ be a subset such that: \[\sum_{x \in X_j} g(x)\geq \sum_{x \in X_i} f(x) \quad \text{for all } i \ne k.\]Now for all elements in $X_j$ let $f(x)=g(x)+1$ and for all other elements let $f(x)=g(x)$ clearly we get that this function is nice. This function is unique as we can uniquely determine $X_j$ and thus can also determine $g(x)$.