Competition problem — Combinatorics

Combinatorics Difficulty 6.2 National Olympiad Prove it Switzerland

Problem:

For a positive integer $m$ , we denote by $[m]$ the set $\{1,2, \ldots, m\}$ . Let $n$ be a positive integer and let $\mathcal{S}$ be a non-empty collection of subsets of $[n]$ . A function $f:[n] \rightarrow [n+1]$ is called kawaii if there exists $A \in \mathcal{S}$ such that for all $B \in \mathcal{S}$ with $A \neq B$ we have
$\sum_{a \in A} f(a) > \sum_{b \in B} f(b)$
Prove that there are always at least $n^{n}$ kawaii functions, irrespective of $\mathcal{S}$ .

Solution

Solution:

We will prove there is an injection from functions $f:[n] \rightarrow [n]$ and kawaii functions.

Let $f$ be an arbitrary function in the latter set. Let $S$ be any set in $\mathcal{S}$ whose sum of images is larger or equal to all other sums of images over sets in $\mathcal{S}$ . Now, add $1$ to the image of every element of $S$ . You now obtain a function that is forcibly kawaii, irrespective of whether $f$ was kawaii. Furthermore, this function is clearly invertible from the image back to the domain and therefore an injection.

Note that several equivalent approaches are possible, for example considering functions whose images are $2, \ldots, n+1$ and then taking away $1$ from the images of elements not in a maximal set.

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.