Maths Olympiad Prep

Library / /23 of 63

, 2019

Combinatorics Difficulty 8.0 Shortlist Prove it Turkey

There are 20192019 bags: each bag contains 20192019 beads with total weight 11 kg. In each bag the beads are numbered by 1,2,,20191, 2, \ldots, 2019. A proper collection is a collection of differently numbered beads containing at most one bead from each bag and having total weight not less than 11 kg. Find the maximal possible value of kk, if always there are at least kk different proper collections.

Solution

A good collection is a collection of differently numbered beads containing exactly one bead from each bag. Let (σ1,σ2,,σ2019)(\sigma_1, \sigma_2, \dots, \sigma_{2019}) be a good collection, where for each i=1,2,,2019i = 1, 2, \dots, 2019, σi\sigma_i is a number of the bead taken from ii-th bag. We say that two good collections (σ1,σ2,,σ2019)(\sigma'_1, \sigma'_2, \dots, \sigma'_{2019}) and (σ1,σ2,,σ2019)(\sigma''_1, \sigma''_2, \dots, \sigma''_{2019}) are equivalent if for some integer kk and for each i=1,2,,2019i = 1, 2, \dots, 2019 we have σi+k=σi(mod2019)\sigma'_i + k = \sigma''_i \pmod{2019}. Clearly, each good collection is equivalent to exactly 20182018 other good collections and the set of all 2019!2019! good collections can be partitioned into 2019!2019=2018!\frac{2019!}{2019} = 2018! equivalence classes. The total weight of all 20192019 collections belonging to any fixed equivalence class is equal to 120191 \cdot 2019 kg, since the sum representing the total weight contains the weight of each bead exactly once. Therefore, in each equivalence class there is at least one good collection with total weight not less than 20192019. Thus, in each equivalence class there is at least one proper collection and consequently there are at least 2018!2018! distinct proper collections.

Now we give an example when the total number of proper collections is exactly 2018!2018!. Suppose that the weights of the beads of first bag are
12019+201820192,12019120192,12019120192,,12019120192 \frac{1}{2019} + \frac{2018}{2019^2}, \frac{1}{2019} - \frac{1}{2019^2}, \frac{1}{2019} - \frac{1}{2019^2}, \dots, \frac{1}{2019} - \frac{1}{2019^2}
respectively and the weights of all other beads are equal to 12019\frac{1}{2019}. Now note that

(†) any proper collection should contain the first bead of the first bag, since otherwise its total weight is at most 1120192<11 - \frac{1}{2019^2} < 1

(††) any proper collection should contain 20192019 beads, since otherwise its total weight is at most
12019+201820192+201712019=1120192<1 \frac{1}{2019} + \frac{2018}{2019^2} + 2017 \cdot \frac{1}{2019} = 1 - \frac{1}{2019^2} < 1
Therefore, any proper collection contains the first bead of the first bag and 20182018 additional beads and the total number of proper collections is 2018!2018!

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 and solution reproduced as published; topic and difficulty added by this site.