In each one of the given $2019$ boxes, there are $2019$ stones numbered as $1,2,...,2019$ with total mass of $1$ kilogram. In all situations satisfying these conditions, if one can pick stones from different boxes with different numbers, with total mass of at least 1 kilogram, in $k$ different ways, what is the maximal of $k$?
Problem
Source: Turkey TST 2019 Day 1 P1
Tags: combinatorics
26.03.2019 21:40
The answer is $2018!$. First, I will prove that for each cyclic permutation $p_1, p_2, \ldots, p_{2019}$ of $1, 2, \ldots, 2019$, there is at least one mapping of boxes $A_1, A_2, \ldots, A_{2019}$ to $p_k, p_{k+1}, \ldots, p_{2019}, p_1, \ldots, p_{k-1}$ for some k, in which we can obtain a total mass greater than $1$ by picking corresponding $p$ from each box $A$. Observe that there are a total of $2019$ different mappings of $A$s to $p$s with no intersection, and the total mass in these mappings is $2019$, thus at least one mapping has total mass $\geq 1$. As there are $2018!$ cyclic permutations, one can pick the stones in at least $2018!$ ways. Now, take the example with $2019$ stones with weight $\frac{1}{2019}$ in first $2018$ boxes and one stone with weight $1-\epsilon$ in box $2019$ with necessarily small $\epsilon$. It is obvious that this stone from box $2019$ must be chosen, and the order with which the stones are chosen from the remaining boxes doesn't matter, so the total number of ways that the stones can be chosen is $2018!$. This completes the proof.