Competition problem — Combinatorics

Library / /58 of 105

Combinatorics Difficulty 6.0 AIME, harder Prove it JBMO

Problem:

Viktor and Natalia bought $2020$ buckets of ice-cream and want to organize a degustation schedule with $2020$ rounds such that:
- In every round, each one of them tries $1$ ice-cream, and those $2$ ice-creams tried in a single round are different from each other.
- At the end of the $2020$ rounds, each one of them has tried each ice-cream exactly once.

We will call a degustation schedule fair if the number of ice-creams that were tried by Viktor before Natalia is equal to the number of ice creams tried by Natalia before Viktor.

Prove that the number of fair schedules is strictly larger than $2020!\left(2^{1010}+(1010!)^{2}\right)$ .

Solution

Solution:

If we fix the order in which Natalia tries the ice-creams, we may consider 2 types of fair schedules:

1) Her last $1010$ ice-creams get assigned as Viktor's first $1010$ ice-creams, and vice versa: Viktor's first $1010$ ice-creams are assigned as Natalia's last $1010$ ice-creams. This generates $(1010!)^{2}$ distinct fair schedules by permuting the ice-creams within each group.

2) We divide all ice-creams into disjoint groups of $4$ , and in each group we swap the first $2$ ice-creams with the last $2$ , which gives us $\left((2!)^{2}\right)^{504}=2^{1010}$ distinct schedules.

Now, to make the inequality strict, we consider $1$ more schedule like $2)$ , but with groups of $2$ ice-creams instead of $4$ .

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.