Track / Stage 5 / 388 of 400 #1468 of 2444

Problem 1468

AIME late

Combinatorics Difficulty 6.0 Prove it Junior Balkan Mathematical Olympiad · JBMO

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)$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.