\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USAMO 2024/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 143}
\maketitle

\section*{Problem}
Let $m$ and $n$ be positive integers.
A circular necklace contains $mn$ beads, each either red or blue.
It turned out that no matter how the necklace was cut into $m$ blocks of $n$
consecutive beads, each block had a distinct number of red beads.
Determine, with proof, all possible values of the ordered pair $(m, n)$.

\section*{Video}
\href{https://www.youtube.com/watch?v=ZLOghPRDgoU&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/ZLOghPRDgoU}}

\section*{External Link}
\url{https://aops.com/community/p30227198}

\newpage

\section*{Solution}
The answer is $m \leq n+1$ only.

\paragraph{Proof the task requires $m \le n+1$.}
Each of the $m$ blocks has a red bead count between $0$ and $n$,
each of which appears at most once, so $m \le n+1$ is needed.

\paragraph{Construction when $m=n+1$.}
For concreteness, here is the construction for $n=4$, which obviously generalizes.
The beads are listed in reading order as an array with $n+1$ rows and $n$ columns.
Four of the blue beads have been labeled $B_1$, \dots, $B_n$
to make them easier to track as they move.
\[
  T_0 =
  \begin{bmatrix}
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{blue}B_1} \\
    {\color{red}R} & {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} \\
    {\color{red}R} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} \\
    {\color{blue}B} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4}
  \end{bmatrix}.
\]
To prove this construction works,
it suffices to consider the $n$ cuts $T_0$, $T_1$, $T_2$, \dots, $T_{n-1}$
made where $T_i$ differs from $T_{i-1}$ by having the cuts one bead later
also have the property each row has a distinct red count:
\[
  T_1 =
  \begin{bmatrix}
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\
    {\color{red}R} & {\color{red}R} & {\color{blue}B_1} & {\color{red}R} \\
    {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} & {\color{red}R} \\
    {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} & {\color{blue}B} \\
    {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4} & {\color{red}R}
    \\
  \end{bmatrix}
  \quad
  T_2 =
  \begin{bmatrix}
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\
    {\color{red}R} & {\color{blue}B_1} & {\color{red}R} & {\color{red}R} \\
    {\color{blue}B} & {\color{blue}B_2} & {\color{red}R} & {\color{blue}B} \\
    {\color{blue}B} & {\color{blue}B_3} & {\color{blue}B} & {\color{blue}B} \\
    {\color{blue}B} & {\color{blue}B_4} & {\color{red}R} & {\color{red}R}
  \end{bmatrix}
  \quad
  T_3 =
  \begin{bmatrix}
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\
    {\color{blue}B_1} & {\color{red}R} & {\color{red}R} & {\color{blue}B} \\
    {\color{blue}B_2} & {\color{red}R} & {\color{blue}B} & {\color{blue}B} \\
    {\color{blue}B_3} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B} \\
    {\color{blue}B_4} & {\color{red}R} & {\color{red}R} & {\color{red}R}
  \end{bmatrix}.
\]
We can construct a table showing for each $1 \le k \le n+1$
the number of red beads which are in the $(k+1)$st row of $T_i$ from the bottom:
\[
  \begin{array}{c|cccc}
    k & T_0 & T_1 & T_2 & T_3 \\ \hline
    k=4 & 4 & 4 & 4 & 4 \\
    k=3 & 3 & 3 & 3 & 2 \\
    k=2 & 2 & 2 & 1 & 1 \\
    k=1 & 1 & 0 & 0 & 0 \\
    k=0 & 0 & 1 & 2 & 3
  \end{array}.
\]
This suggests following explicit formula for the entry of the $(i,k)$th cell
which can then be checked straightforwardly:
\[
  \#(\text{red cells in $k$th row of $T_i$})
  =
  \begin{cases}
    k & k > i \\
    k-1 & i \ge k > 0 \\
    i & k = 0.
  \end{cases}
\]
And one can see for each $i$, the counts are all distinct
(they are $(i, 0, 1, \dots, k-1, k+1, \dots, k)$ from bottom to top).
This completes the construction.

\paragraph{Construction when $m < n+1$.}
Fix $m$.
Take the construction for $(m,m-1)$ and add $n+1-m$ cyan beads to the start of each row;
for example, if $n = 7$ and $m = 5$ then the new construction is
\[
  T =
  \begin{bmatrix}
    {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} &
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{red}R} \\
    {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} &
    {\color{red}R} & {\color{red}R} & {\color{red}R} & {\color{blue}B_1} \\
    {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} &
    {\color{red}R} & {\color{red}R} & {\color{blue}B} & {\color{blue}B_2} \\
    {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} &
    {\color{red}R} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_3} \\
    {\color{cyan}C} & {\color{cyan}C}& {\color{cyan}C} &
    {\color{blue}B} & {\color{blue}B} & {\color{blue}B} & {\color{blue}B_4}
  \end{bmatrix}.
\]
This construction still works for the same reason (the cyan beads
do nothing for the first $n+1-m$ shifts, then one reduces to the previous case).
If we treat cyan as a shade of blue, this finishes the problem.

\end{document}
