We say that a permutation $(a_1, \dots, a_n)$ of $(1, 2, \dots, n)$ is good if the sums $a_1 + a_2 + \dots + a_i$ are all distinct modulo $n$. Prove that there exists a positive integer $n$ such that there are at least $2020$ good permutations of $(1, 2, \dots, n)$.
Proposed by Ariel GarcĂa
A quick solve: how solving a (similar) problem in past experience matters a lot, especially considering the Motivation towards the Solution.
We claim that any even number $n=2k$ with $\varphi(2k) \geq 2020$ works (the sharp reader may solve the problem based on this short statement alone.)
For ease of writeout let $b_i = a_1+a_2+\ldots+a_i \pmod n$, with $1 \leq b_i \leq n$. Note that a permutation $\{a_i\}$ is good iff its respective $\{b_i\}$ is also a permutation of $[n] = \{1,2,\ldots,n\}$.
$\color{green} \rule{25cm}{2pt}$
$\color{green} \textbf{One Blooming Sprout.}$ Any even $n = 2k$ exhibits at least one good permutation.
$\color{green} \rule{25cm}{0.4pt}$
$\color{green} \textbf{Construction.}$ Divide the numbers $(a_1,a_2,\ldots,a_n) = (1,2,\ldots,2k)$ into $(2k); (2k-1); (a,2k-1-a)$ where $a$ is every odd number from $1$ to $2k-2$.
Then set
\[ ([a_1],[a_2,a_3],\ldots,[a_{2k-2},a_{2k-1}],[a_{2k}]) = ([2k],[1,2k-2],[3,2k-4],\ldots,[2k-3,2],[2k-1]) \]with the $i^{\text{th}}$ pair on the left corresponding to the $i^{\text{th}}$ pair of $(a,2k-1-a)$ listed on the first paragraph of this Section. Call this special good configuration $A$.
For example, we'll select the configuration $([6],[1,4],[3,2],[5])$ for $n = 6$.
It's easy to see that its respective $\{b_i\}$ is equal to $(2k,1,2k-1,2,2k-2,\ldots,k-1,k+1,k)$. $\blacksquare$ $\blacksquare$
$\color{red} \rule{25cm}{2pt}$
$\color{red} \textbf{Reverse-Homogenisation: 2020 New Offsprings.}$ <Cringe name, I know> but the finishing is insultingly easy.
For every $g$ coprime with $2k$, we can multiply each number in $\{a_i\} = A$ by $g$; note that no two $g \times a_k$ and $g \times a_l$ ($1 \leq k,l \leq n$) will be equal to each other modulo $n$, and analogously, no two $g \times b_k$ and $g \times b_l$ will be equal to each other modulo $n$.
So by multiplying by $2020$ different $g$s, we will obtain 2020 different permutations $g \times A$ with $\{b_i\}$s also a permutation (implying $g \times A$ good for every $g$). $\blacksquare$ $\blacksquare$ $\blacksquare$
The two problems mentioned are here and here.
Guess it won't be fun if I just blatantly throw that out there without any explanation, so here goes!
$\color{cyan} \rule{25cm}{2pt}$
$\color{green} \text{Sec 1: Zero-Trouble.}$ Seeking good configurations for smaller numbers, $n = 3,4$ for example; I quickly found that
For $n = 3$, very bad things happen. Setting $(a_1,a_2,a_3) = (1,2,3)$ makes $\{b_i\} = (1,3,3)$ as $1 + 2 \equiv 3$, but after trying all $6$ permutation for science's sake there's no way for $1$ and $2$ to $\textit{not make}$ a $3 \pmod 3$.
For $n = 4$, the same problem happens except $4$ is placed first.
Why is this so? After doing the standard manipulation
\[ a_1+a_2+\ldots+a_j \equiv a_1+\ldots+a_i \pmod n \Leftrightarrow a_{i+1}+\ldots+a_j \equiv 0 \pmod n\]any consecutive-sum from $a_2$ onward cannot equal to zero modulo $n$, and simply having zero among $a_2$ until $a_n$ just doesn't cut it. After fixing $a_1 = 4$, I also noticed the invariance of $b_4 = 2$, so $(b_1,b_2,b_3,b_4) = (4,?,?,2)$.
Filling the question marks with numbers fixes the values of $a_2,a_3,a_4$ --- and I also noted that fixing the sequence $\{b_i\}$ will determine the sequence $\{a_i\}$ uniquely: $a_i \equiv b_{i+1}-b_i \pmod n$.
This shouldn't be a groundbreaking observation, but it helps to put into perspective that $\{a_i\}$ and $\{b_i\}$ shouldn't be of much different from each other, after all (bijection foreshadowing?)
$\color{cyan} \rule{25cm}{2pt}$
$\color{green} \text{Sec 2: Multiplication, and (even) handwaving.}$ After skipping $n = 5$ for obvious reasons, I proceeded to $n = 6$ with the standard $\dfrac{n(n+1)}{2}$ doubt: it's never good when you had to rely on the parity of $\dfrac{n(n+1)}{2}$ to yield a configuration. If it had to be done on a particular $x \pmod 4$ (as is usually the case when that sum pops up) it'd be a nightmare!
Discarding the notion, trying to reverse-engineer $\{a_i\}$ from an established $\{b_i\}$ I first tried to put (quite symmetrically)
\[ \begin{tabular}{c|c|c|c|c|c|c|}
$\{b_i\}$&$\color{red} 6$&1&4&2&5&$\color{green}3$ \\ \hline
$\{a_i\}$&$\color{red} 6$&1&3&4&3&4 \\
\end{tabular}\]and it didn't work because the existence of consecutive $(1,4)$ and $(2,5)$ on the $\{b_i\}$. A most tempting idea then came: what if there exists a non-constructive construction using possibly inclusion-exclusion? All I had to do was destroy all sequences where there exists
\[ b_{i+1}-b_i \equiv b_{j+1}-b_j \pmod n \]Unfortunately, this is very hard to count with $\binom{n-1}{2}$ ugly sets to exclude (there are that many forbidden congruences). The probabilistic method/taking means method will most definitely not work either, because the expression has too many exclusions.
A config which had me worked up was $\{b_i\} = (6,4,5,2,1,3)$ which result in $\{a_i\} = (6,4,1,3,5,2)$. They further strengthened my belief that those sequences shouldn't differ from one another, as $\{a_i\}$ can be obtained by fixing the first two terms of $\{b_i\}$ and switching the second pair with the last pair.
Then I started to wonder: do a family of sequences $\{a_i\}$ which are close relatives of each other exist?
Looking back at $n = 4$ gave me the answer: $\{a_i\} = \{4,1,2,3\}$ and $\{a_i\} = \{4,3,2,1\}$ might be opposites of each other, but that exactly meant that $\{4,1,2,3\} \times 3 \equiv \{4,3,2,1\}$. This is further extended in multiplying by any $c$ which is relatively prime with $n$ for uniqueness effects: $c \cdot a \equiv c \cdot b \pmod n$ implies $a \equiv b \pmod n$.
A lesson learnt from LuMaT No.8,
Spoilersan addition problem which is seemingly unrelated with NT: when in doubt with strange additional combinatorics, multiply!
This meant that if for $n$ with lots of rel.prime numbers, then one sprout will be enough. Now it's time to scavenge another problem's idea for making a sequence with a disturbingly uniform and contrasting sum.
$\color{cyan} \rule{25cm}{2pt}$
$\color{green} \text{Sec 3: A Pairing Modification.}$ Then it was left to my creativity to create one good permutation. Drawing inspiration from the RMM problem, the plan was to create $(a_1),(a_2,a_3), \ldots (a_{n-1},a_n)$ as in that problem, with $a_1 = n$ being the decoy and $a_{2i}+a_{2i+1}$ having constant sum.
However, the problems immediately surfaced:
There are $2k$ numbers in total instead of $2k+1$, so another decoy will have to be burnt (either in front of the sequence or at its back);
having pairs of numbers with sum $n$ is strictly prohibited because of the $\color{green} \text{Zero-trouble}$ described in Section 1;
and the remaining degrees of freedom do have to be utilized: how to make $\{b_i\}$ different while keeping the integrity of the pairs (of $\{a_i\}$ being distinct and complete?
This is resolved by tweaking the sequence bit by bit:
The decoy will follow $\{b_i\}$'s invariant last term: at the back. Seeing that I will inevitably create $\color{green} b_{2k} = k$, I tried to push the values of $2k-1$ to $k+1$ in decreasing order from the ($\color{red} \text{also}$) fixed $b_1 = 2k$ as in $\color{green} \text{Sec 2}$;
shamelessly follow that lead and make the pairs sum to $-1$ mod $n$ or exactly $2k-1$ and letting the not-fit-number $2k-1$ to the back, and;
adjusting the remaining degrees of freedom (determining which comes first in the below table) to my liking: making sure that $a_2 \equiv 1-6 \pmod 6$, and $a_4 \equiv 2-5 \pmod 6$.
\[ \begin{tabular}{c|c|c|c}
$\{a_i\}$&$\color{red}6$&$(1,4)(2,3)$&$\color{green}5$ \\ \hline
$\{b_i\}$&$\color{red}6$&1, 5, 2, 4&$\color{green}3$ \\
\end{tabular}\]\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]