Viktor and Natalia bought $2020$ buckets of ice-cream and want to organize a degustation schedule with $2020$ rounds such that: - In every round, both of them try $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, both of them have 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!(2^{1010} + (1010!)^2)$. Proposed by Viktor Simjanoski, Macedonia
Problem
Source: JBMO Shortlist 2020
Tags: Junior, Balkan, shortlist, 2020, combinatorics
Lukaluce
04.07.2021 18:17
This problem was proposed by Macedonia
alchemyst_
02.08.2021 16:35
Firstly note that there are $2020!$ different orders in which Viktor can try the ice creams. Let Victor's $k$th ice cream try be labelled $a_k$ and let Natalia's $k$th ice cream try be labelled $b_k$. We will provide two different arrangements for Natalia's ice creams. Arrangement 1: $(b_1, b_2, b_3,...,b_{1010}) = (a_{1011}, a_{1012}, a_{1013},...,a_{2020})$ (not necessarily in that order) and $(b_{1011}, b_{1012}, b_{1013},...,b_{2020}) = (a_1, a_2, a_3,...,a_{1010})$ There are $(1010!)^2$ ways to arrange $b_i$ this way. Arrangement 2: This is very similar to Arrangement 1 but instead we have divided the set into $4$ categories. So we can have for each $1 \leq i \leq 505, b_i = a_j$ and some $j$ satisfying $506 \leq j \leq 1010$ and for each $506 \leq i \leq 1010, b_i = a_j$ and some $j$ satisfying $1515 \leq j \leq 2020$ and for each $1011 \leq i \leq 1515, b_i = a_j$ and some $j$ satisfying $1 \leq j \leq 505$ and for each $1516 \leq i \leq 2020, b_i = a_j$ and some $j$ satisfying $1011 \leq j \leq 1515$ There are $(505!)^4$ ways to arrange $b_i$ this way. With these $2$ combined, we have counted $2020!((505!)^4 + (1010!)^2)$ so it would suffice to show $(505!)^4 \geq 2^{1010}$ which is true as $505! \geq 2^{253}$ clearly holds.
Zorger74
27.12.2021 05:37
Solved with zhao_andrew.
Label the ice creams with the positive integers from $1$ to $2020$ such that Viktor tries the ice creams in the order $1,2,\dots 2020$. There are $2020!$ ways this can happen, and Natalia has the same number of ways to try her ice creams by symmetry for each order Viktor tries his ice creams in.
The main idea of this solution is to show two non-overlapping methods for Natalia to eat her ice creams.
The first method is that she can take ice creams $1011$ to $2020$ and eat those first in $1010!$ ways, and then eat ice creams $1$ to $1010$ second in another $1010!$ ways for a total of $(1010!)^2$ ways. Both of them are always trying different ice creams at any given time, and both of them try exactly $1010$ ice creams before the other ($1$ through $1010$ for Viktor, $1011$ through $2020$ for Natalia).
The second method is that she can take ice creams $1$ to $4$ and eat those first in any of the orders $3412, 3421, 4312$, or $4321$. Then she can take ice creams $5$ through $8$ and eat those in any of the orders $7856, 7865, 8756$, or $8765$. She can continue this pattern for every $4$ ice creams in order, $505$ times total. There are $4^{505}=2^{1010}$ total ways for her to try the ice creams in this way, and she is never trying any given ice cream at the same time that Viktor is. As well, both Natalia and Viktor try $1010$ ice creams before the other person using this method ($1,2,5,6,9,10,\dots,2017,2018$ for Viktor, $3,4,7,8,\dots,2019,2020$ for Natalia).
It's clearly impossible for Natalia to try the ice creams in the same order in both the first and second ways because she must eat ice cream $1$ in the second half using the first way, and in the first half using the second way.
In total, there are $2020!$ ways that Viktor can try his ice creams. For each of these ways, Natalia has at least $2^{1010}+(1010!)^2$ ways to try her ice creams, so in total the number of fair schedules is strictly larger than $2020!(2^{1010} + (1010!)^2)$.
To show that it's strictly larger, note that Natalia can try the ice creams in the order $2,1,4,3,6,5,\dots,2020,2019$, which isn't included in either way.