IMO 2022 Shortlist C5
Let m,n ě 2 be integers, let X be a set with n elements, and let X1,X2,...,Xm be pairwise distinct non-empty, not necess...
Category: Combinatorics
Problem
Let m,n ě 2 be integers, let X be a set with n elements, and let X1,X2,...,Xm be pairwise distinct non-empty, not necessary disjoint subsets of X. A function f : X Ñ t1,2,...,n ` 1u is called nice if there exists an index k such that ÿ xPXk fpxq ą ÿ xPXi fpxq for all i ‰ k. Prove that the number of nice functions is at least nn . (Germany)