% © Evan Chen
% Downloaded from https://web.evanchen.cc/

\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
    updated \today}
\title{USAMO 2024 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2024 USAMO.
The ideas of the solution are a mix of my own work,
the solutions provided by the competition organizers,
and solutions found by the community.
However, all the writing is maintained by me.

These notes will tend to be a bit more advanced and terse than the ``official''
solutions from the organizers.
In particular, if a theorem or technique is not known to beginners
but is still considered ``standard'', then I often prefer to
use this theory anyways, rather than try to work around or conceal it.
For example, in geometry problems I typically use directed angles
without further comment, rather than awkwardly work around configuration issues.
Similarly, sentences like ``let $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.

Corrections and comments are welcome!
\end{abstract}

\tableofcontents
\newpage

\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Find all integers $n \geq 3$ such that the following property holds:
if we list the divisors of $n!$ in increasing order
as $1 = d_1 < d_2 < \dots < d_k = n!$, then we have
\[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \]

\item %% Problem 2
Let $S_1$, $S_2$, \dots, $S_{100}$ be finite sets of integers whose intersection is not empty.
For each non-empty $T \subseteq \{S_1, S_2, \ldots, S_{100}\}$,
the size of the intersection of the sets in $T$ is a multiple of $|T|$.
What is the smallest possible number of elements which are in at least $50$ sets?

\item %% Problem 3
Let $(m,n)$ be positive integers with $n \ge 3$ and draw a regular $n$-gon.
We wish to triangulate this $n$-gon into $n-2$ triangles,
each colored one of $m$ colors, so that each color has an equal sum of areas.
For which $(m,n)$ is such a triangulation and coloring possible?

\item %% Problem 4
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)$.

\item %% Problem 5
Point $D$ is selected inside acute triangle $ABC$
so that $\angle DAC = \angle ACB$ and $\angle BDC = 90^\circ + \angle BAC$.
Point $E$ is chosen on ray $BD$ so that $AE = EC$.
Let $M$ be the midpoint of $BC$.
Show that line $AB$ is tangent to the circumcircle of triangle $BEM$.

\item %% Problem 6
Let $n > 2$ be an integer and let $\ell \in \{1, 2,\dots, n\}$.
A collection $A_1$, \dots, $A_k$ of (not necessarily distinct) subsets of
$\{1, 2,\dots, n\}$ is called $\ell$-large if $|A_i| \ge \ell$ for all $1 \le i \le k$.
Find, in terms of $n$ and $\ell$, the largest real number $c$ such that the inequality
\[ \sum_{i=1}^k\sum_{j=1}^k x_ix_j \frac{|A_i\cap A_j|^2}{|A_i|\cdot|A_j|}
  \ge c\left(\sum_{i=1}^k x_i\right)^2 \]
holds for all positive integer $k$,
all nonnegative real numbers $x_1$, $x_2$, \dots, $x_k$,
and all $\ell$-large collections $A_1$, $A_2$, \dots, $A_k$
of subsets of $\{1,2,\dots,n\}$.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{USAMO 2024/1, proposed by Luke Robitaille}
\textsl{Available online at \url{https://aops.com/community/p30216459}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all integers $n \geq 3$ such that the following property holds:
if we list the divisors of $n!$ in increasing order
as $1 = d_1 < d_2 < \dots < d_k = n!$, then we have
\[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \]
\end{mdframed}
The answer is $n \in \{3,4\}$. These can be checked by listing all the divisors:
\begin{itemize}
  \ii For $n=3$ we have $(1,2,3,6)$.
  \ii For $n=4$ we have $(1,2,3,4,6,8,12,24)$.
\end{itemize}

We prove these are the only ones.

The numbers $5 \le n \le 12$ all fail because:
\begin{itemize}
  \ii For $n = 5$ we have $20 - 15 > 24 - 20$.
  \ii For $n = 6$ we have $18 - 15 > 20 - 18$.
  \ii For $7 \le n \le 12$ we have because $14-12 > 15-14$ (and $13 \nmid n!$).
\end{itemize}

Now assume $n \ge 13$.
In that case, we have
\[ \left\lfloor \frac n2 \right\rfloor^2 - 1 \ge 2n. \]
So by Bertrand postulate, we can find a prime $p$ such that
\[ n < p < \left\lfloor \frac n2 \right\rfloor^2 - 1. \]
However, note that
\[ \left\lfloor \frac n2 \right\rfloor^2 - 1
  = \left( \left\lfloor \frac n2 \right\rfloor - 1 \right) \left( \left\lfloor \frac n2 \right\rfloor + 1 \right),
  \qquad \left\lfloor \frac n2 \right\rfloor^2
\]
are consecutive integers both dividing $n!$ (the latter number divides
$\left\lfloor \frac n2 \right\rfloor \cdot \left( 2 \left\lfloor \frac n2 \right\rfloor \right)$).
So the prime $p$ causes the desired contradiction.
\pagebreak

\subsection{USAMO 2024/2, proposed by Rishabh Das}
\textsl{Available online at \url{https://aops.com/community/p30216494}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $S_1$, $S_2$, \dots, $S_{100}$ be finite sets of integers whose intersection is not empty.
For each non-empty $T \subseteq \{S_1, S_2, \ldots, S_{100}\}$,
the size of the intersection of the sets in $T$ is a multiple of $|T|$.
What is the smallest possible number of elements which are in at least $50$ sets?
\end{mdframed}
The answer is $50 \binom{100}{50}$.

\paragraph{Rephrasing (cosmetic translation only, nothing happens yet).}
We encode with binary strings $v \in \FF_2^{100}$ of length $100$.
Write $v \subseteq w$ if $w$ has $1$'s in every component $v$ does,
and let $|v|$ denote the number of $1$'s in $v$.

Then for each $v$, we let $f(v)$ denote the number of elements $x \in \bigcup S_i$
such that $x \in S_i \iff v_i = 1$.
For example,
\begin{itemize}
  \ii $f(1\dots1)$ denotes $|\bigcap_1^{100} S_i|$,
  so we know $f(1 \dots 1) \equiv 0 \pmod{100}$.
  \ii $f(1\dots10)$ denotes the number of elements in $S_1$ through $S_{99}$
  but not $S_{100}$
  so we know that $f(1 \dots 1) + f(1 \dots 10) \equiv 0 \pmod{99}$.
  \ii \dots And so on.
\end{itemize}
So the problem condition means that $f(v)$ translates to the statement
\[ P(u): \qquad |u| \text{ divides } \sum_{v \supseteq u} f(v) \]
for any $u \neq 0\dots0$, plus one extra condition $f(1\dots1) > 0$.
And the objective function is to minimize the quantity
\[ A \coloneqq \sum_{|v| \ge 50} f(v). \]
So the problem is transformed into an system of equations over $\ZZ_{\ge 0}$
(it's clear any assignment of values of $f(v)$
can be translated to a sequence $(S_1, \dots, S_{100})$ in the
original notation).

Note already that:
\begin{claim*}
  It suffices to assign $f(v)$ for $|v| \ge 50$.
\end{claim*}
\begin{proof}
  If we have found a valid assignment of values to $f(v)$ for $|v| \ge 50$,
  then we can always arbitrarily assign values of $f(v)$ for $|v| < 50$ by downwards
  induction on $|v|$ to satisfy the divisibility condition (without changing $M$).
\end{proof}
Thus, for the rest of the solution, we altogether ignore $f(v)$ for $|v| < 50$
and only consider $P(u)$ for $|u| \ge 50$.

\paragraph{Construction.}
Consider the construction
\[ f_0(v) = 2 |v| - 100. \]
This construction is valid since if $|u| = 100-k$ for $k \le 50$ then
\begin{align*}
  \sum_{v \supseteq u} f_0(v)
  &= \binom{k}{0} \cdot 100 + \binom{k}{1} \cdot 98 + \binom{k}{2} \cdot 96
  + \dots + \binom{k}{k} \cdot (100-2k) \\
  &= (100-k) \cdot 2^k = |u| \cdot 2^k
\end{align*}
is indeed a multiple of $|u|$, hence $P(u)$ is true.
In that case, the objective function is
\[ A = \sum_{i=50}^{100} \binom{100}{i} (2i-100) = 50\binom{100}{50} \]
as needed.
\begin{remark*}
  This construction is the ``easy'' half of the problem because it
  coincides with what you get from a greedy algorithm by downwards induction on $|u|$
  (equivalently, induction on $k = 100-|u| \ge 0$).
  To spell out the first three steps,
  \begin{itemize}
    \ii We know $f(1\dots1)$ is a nonzero multiple of $100$,
    so it makes sense to guess $f(1\dots1) = 100$.
    \ii Then we have $f(1\dots10) + 100 \equiv 0 \pmod{99}$,
    and the smallest multiple of $99$ which is at least $100$ is $198$.
    So it makes sense to guess $f(1\dots10) = 98$, and similarly guess $f(v) = 98$
    whenever $|v| = 99$.
    \ii Now when we consider, say $v= 1 \dots 100$ with $|v| = 98$, we get
    \[ f(1\dots100) + \underbrace{f(1\dots101)}_{=98} + \underbrace{f(1\dots110)}_{=98}
      + \underbrace{f(1\dots111)}_{=100} \equiv 0 \pmod{98}. \]
    we obtain $f(1\dots100) \equiv 96 \pmod{98}$.
    That makes $f(1\dots100) = 96$ a reasonable guess.
  \end{itemize}
  Continuing in this way gives the construction above.
\end{remark*}

\paragraph{Proof of bound.}
We are going to use a smoothing argument:
if we have a general working assignment $f$, we will mold it into $f_0$.

We define a \textbf{push-down on $v$} as the following operation:
\begin{itemize}
  \ii Pick any $v$ such that $|v| \ge 50$ and $f(v) \ge |v|$.
  \ii Decrease $f(v)$ by $|v|$.
  \ii For every $w$ such that $w \subseteq v$ and $|w| = |v| - 1$,
  increase $f(w)$ by $1$.
\end{itemize}
\begin{claim*}
  Apply a push-down preserves the main divisibility condition.
  Moreover, it doesn't change $A$ unless $|v| = 50$, where it decreases $A$ by $50$ instead.
\end{claim*}
\begin{proof}
  The statement $P(u)$ is only affected when $u \subseteq v$:
  to be precise, one term on the right-hand side of $P(u)$ increases by $|v|$,
  while $|v|-|u|$ terms decrease by $1$, for a net change of $+|u|$.
  So $P(u)$ still holds.

  To see $A$ doesn't change for $|v| > 50$,
  note $|v|$ terms increase by $1$ while one term decreases by $-|v|$.
  When $|v| = 50$, only $f(v)$ decreases by $50$.
\end{proof}
Now, given a valid assignment, we can modify it as follows:
\begin{itemize}
  \ii First apply pushdowns on $1\dots1$ until $f(1\dots1) = 100$;
  \ii Then we may apply pushdowns on each $v$ with $|v| = 99$ until $f(v) < 99$;
  \ii Then we may apply pushdowns on each $v$ with $|v| = 98$ until $f(v) < 98$;
  \ii \dots and so on, until we have $f(v) < 50$ for $|v| = 50$.
\end{itemize}
Hence we get $f(1\dots1) = 100$ and $0 \le f(v) < |v|$ for all $50 \le |v| \le 100$.
However, by downwards induction on $|v| = 99, 98, \dots, 50$, we also have
\[ f(v) \equiv f_0(v) \pmod{|v|} \implies f(v) = f_0(v) \]
since $f_0(v)$ and $f(v)$ are both strictly less than $|v|$.
So in fact $f = f_0$, and we're done.

\begin{remark*}
  The fact that push-downs actually don't change $A$
  shows that the equality case we described is far from unique:
  in fact, we could have made nearly arbitrary sub-optimal
  decisions during the greedy algorithm and still ended up with an equality case.
  For a concrete example, the construction
  \[
    f(v) = \begin{cases}
      500 & |v| = 100 \\
      94 & |v| = 99 \\
      100-2|v| & 50 \le |v| \le 98
    \end{cases}
  \]
  works fine as well (where we arbitrarily chose $500$ at the start,
  then used the greedy algorithm thereafter).
\end{remark*}
\pagebreak

\subsection{USAMO 2024/3, proposed by Krit Boonsiriseth}
\textsl{Available online at \url{https://aops.com/community/p30216513}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $(m,n)$ be positive integers with $n \ge 3$ and draw a regular $n$-gon.
We wish to triangulate this $n$-gon into $n-2$ triangles,
each colored one of $m$ colors, so that each color has an equal sum of areas.
For which $(m,n)$ is such a triangulation and coloring possible?
\end{mdframed}
The answer is if and only if $m$ is a proper divisor of $n$.

Throughout this solution, we let $\omega = \exp\left( 2 \pi i / n \right)$
and let the regular $n$-gon have vertices $1$, $\omega$, \dots, $\omega^{n-1}$.
We cache the following frequent calculation:
\begin{lemma*}
  The triangle with vertices $\omega^k$, $\omega^{k+a}$, $\omega^{k+b}$ has signed area
  \[ T(a,b) \coloneqq \frac{(\omega^a-1)(\omega^b-1)(\omega^{-a}-\omega^{-b})}{2i}. \]
\end{lemma*}
\begin{proof}
  Rotate by $\omega^{-k}$ to assume WLOG that $k=0$.
  Apply complex shoelace to the triangles with vertices $1$, $\omega^a$, $\omega^b$ to get
  \[
    \frac{1}{2i}
    \det \begin{bmatrix}
      1 & 1 & 1 \\
      \omega^a & \omega^{-a} & 1 \\
      \omega^b & \omega^{-b} & 1 \\
    \end{bmatrix}
    =
    \frac{1}{2i}
    \det \begin{bmatrix}
      0 & 0 & 1 \\
      \omega^a-1 & \omega^{-a}-1 & 1 \\
      \omega^b-1 & \omega^{-b}-1 & 1 \\
    \end{bmatrix}
  \]
  which equals the above.
\end{proof}

\paragraph{Construction.}
It suffices to actually just take all the diagonals from the vertex $1$,
and then color the triangles with the $m$ colors in cyclic order.
For example, when $n = 9$ and $m = 3$, a coloring with red, green, blue would be:
\begin{center}
\begin{asy}
  size(6cm);
  pair A(int i) { return dir(40*i); }
  pen[] fillcolors = {palered, palegreen, palecyan};
  pen[] labelcolors = {brown, darkgreen, deepblue};
  string[] labels = {"R", "Green", "Blue", "Red", "Green", "Blue", "R"};
  for (int i=0; i<=6; ++i) {
    filldraw(A(0)--A(i+1)--A(i+2)--cycle, fillcolors[i-3*(i#3)], black+1.5);
    label(labels[i], incenter(A(0),A(i+1),A(i+2)),
      labelcolors[i-3*(i#3)] + fontsize(14pt));
  }
\end{asy}
\end{center}
To see this works one can just do the shoelace calculation:
for a given residue $r \bmod m$, we get an area
\begin{align*}
  \sum_{j \equiv r \bmod m} \opname{Area}(\omega^j, \omega^0, \omega^{j+1})
  &= \sum_{j \equiv r \bmod m} T(-j, 1) \\
  &= \sum_{j \equiv r \bmod m} \frac{(\omega^{-j}-1)(\omega^1-1)(\omega^j-\omega^{-1})}{2i} \\
  &= \frac{\omega-1}{2i} \sum_{j \equiv r \bmod m} (\omega^{-j}-1)(\omega^j-\omega^{-1}) \\
  &= \frac{\omega-1}{2i} \left( \frac{n}{m} \left( 1 + \omega\inv \right)
    + \sum_{j \equiv r \bmod m} (\omega^{-j}-\omega^j) \right).
\end{align*}
(We allow degenerate triangles where $j \in \{-1,0\}$ with area zero.)
However, if $m$ is a proper divisor of $m$, then
$\sum_{j \equiv r \bmod m} \omega^j
= \omega^r(1+\omega^m+\omega^{2m}+\dots+\omega^{n-m}) = 0$.
Similarly, $\sum_{j \equiv r \bmod m} \omega^{-j} = 0$.
So the inner sum vanishes, and the total area of the $m$th color equals
\[ \frac nm \frac{(\omega-1)(\omega^{-1}+1)}{2i} \]
which does not depend on the residue $r$, proving the coloring works.

\paragraph{Proof of necessity.}
It's obvious that $m < n$ (in fact $m \le n-2$).
So we focus on just showing $m \mid n$.

Repeating the same calculation as above, we find that if there was a valid
triangulation and coloring, the total area of each color would equal
\[ S \coloneqq \frac nm \frac{(\omega-1)(\omega^{-1}+1)}{2i}. \]
However:
\begin{claim*}
  The number $2i \cdot S$ is not an algebraic integer when $m \nmid n$.
\end{claim*}
\begin{proof}
  This is easiest to see if one knows the advanced result that
  $K \coloneqq \QQ(\omega)$ is a number field
  whose ring of integers is known to be $\mathcal{O}_K = \ZZ[\omega]$.
  Hence if one takes $(\omega^{-1}, \omega^0, \omega^1, \dots, \omega^{n-2})$ as a
  $\QQ$-basis of $K$, then $\OO_K$ is the subset where each coefficient is integer.
\end{proof}
However, each of the quantities $T(a,b)$ is $\frac{1}{2i}$ times an algebraic integer.
Since a finite sum of algebraic integers is also an algebraic integer,
such areas can never sum to $S$.

\begin{remark*}
  If one wants to avoid citing the fact that $\mathcal{O}_K = \ZZ[\omega]$,
  then one can instead note that $T(a,b)$ is actually always divisible by
  $(\omega-1)(\omega^{-1}+1)$ over the algebraic integers
  (at least one of $\{\omega^a-1, \omega^b-1, \omega^{-a} - \omega^{-b}\}$
  is a multiple of $\omega+1$, by casework on $a,b \bmod 2$).
  Then one using $\frac{2i}{(\omega-1)(\omega^{-1}+1)}$ as the scaling factor
  instead of $2i$, one sees that we actually need $\frac nm$ to be an algebraic integer,
  which happens only when $m$ divides $n$.
\end{remark*}
\pagebreak

\section{Solutions to Day 2}
\subsection{USAMO 2024/4, proposed by Rishabh Das}
\textsl{Available online at \url{https://aops.com/community/p30227198}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
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)$.
\end{mdframed}
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.
\pagebreak

\subsection{USAMO 2024/5, proposed by Anton Trygub}
\textsl{Available online at \url{https://aops.com/community/p30227196}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Point $D$ is selected inside acute triangle $ABC$
so that $\angle DAC = \angle ACB$ and $\angle BDC = 90^\circ + \angle BAC$.
Point $E$ is chosen on ray $BD$ so that $AE = EC$.
Let $M$ be the midpoint of $BC$.
Show that line $AB$ is tangent to the circumcircle of triangle $BEM$.
\end{mdframed}
This problem has several approaches and we showcase a collection of them.

\paragraph{The author's original solution.}
Complete isosceles trapezoid $ABQC$ (so $D \in \ol{AQ}$).
Reflect $B$ across $E$ to point $F$.
\begin{center}
\begin{asy}
size(7cm);
pair A = dir(185);
pair C = dir(355);
pair B = dir(115);
pair Q = A*C/B;
pair X = extension(A, B, Q, C);
pair Y = 2*X-A;
filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
draw(unitcircle, red);
pair D = IP(A--Q, circumcircle(B, C, Y));
pair N = midpoint(A--C);
pair M = midpoint(B--C);
draw(A--Q, mediumblue);
pair E = extension(N, origin, B, D);
pair F = 2*E-B;
draw(F--B, deepgreen);
pair S = dir(90);
draw(S--N, brown);
draw(F--Q, brown);
draw(M--E, grey);
draw(F--C--Q, grey);
filldraw(circumcircle(Q, D, C), opacity(0.1)+yellow, orange);
markangle(n=2, radius=6, M, E, B, deepgreen);
markangle(n=2, radius=6, C, F, B, deepgreen);
markangle(n=1, radius=6, D, Q, C, deepgreen);
markangle(n=1, radius=6, A, B, C, deepgreen);

dot("$A$", A, dir(225));
dot("$C$", C, dir(315));
dot("$B$", B, dir(160));
dot("$Q$", Q, dir(100));
dot("$D$", D, dir(180));
dot(N);
dot("$M$", M, dir(90));
dot("$E$", E, dir(225));
dot("$F$", F, dir(F));

/* -----------------------------------------------------------------+
|                 TSQX: by CJ Quines and Evan Chen                  |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(7cm);
A 225 = dir 185
C 315 = dir 355
B 160 = dir 115
Q 100 = A*C/B
X := extension A B Q C
Y := 2*X-A
A--B--C--cycle / 0.1 lightred / red
unitcircle / red
D 180 = IP A--Q (circumcircle B C Y)
N = midpoint A--C
M 90 = midpoint B--C
A--Q / mediumblue
E 225 = extension N origin B D
F = 2*E-B
F--B / deepgreen
S := dir 90
S--N / brown
F--Q / brown
M--E / grey
F--C--Q / grey
circumcircle Q D C / 0.1 yellow / orange
!markangle(n=2, radius=6, M, E, B, deepgreen);
!markangle(n=2, radius=6, C, F, B, deepgreen);
!markangle(n=1, radius=6, D, Q, C, deepgreen);
!markangle(n=1, radius=6, A, B, C, deepgreen);
*/
\end{asy}
\end{center}
\begin{claim*}
  We have $DQCF$ is cyclic.
\end{claim*}
\begin{proof}
  Since $EA=EC$, we have $\ol{QF} \perp \ol{AC}$
  as line $QF$ is the image of the perpendicular bisector of $\ol{AC}$
  under a homothety from $B$ with scale factor $2$.
  Then
  \begin{align*}
  \dang FDC &= -\dang CDB = 180\dg - (90\dg + \dang CAB) = 90\dg - \dang CAB \\
    &= 90\dg - \dang QCA = \dang FQC. \qedhere
  \end{align*}
\end{proof}
To conclude, note that
\[ \dang BEM = \dang BFC = \dang DFC = \dang DQC = \dang AQC = \dang ABC = \dang ABM. \]

\begin{remark*}
  [Motivation]
  Here is one possible way to come up with the construction of point $F$
  (at least this is what led Evan to find it).
  If one directs all the angles in the obvious way,
  there are really two points $D$ and $D'$ that are possible,
  although one is outside the triangle;
  they give corresponding points $E$ and $E'$.
  The circles $BEM$ and $BE'M$ must then actually coincide since they
  are both alleged to be tangent to line $AB$.
  See the figure below.
  \begin{center}
  \begin{asy}
    size(11cm);
    pair A = dir(185);
    pair C = dir(355);
    pair B = dir(115);
    pair Q = A*C/B;
    pair X = extension(A, B, Q, C);
    pair Y = 2*X-A;
    filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
    draw(unitcircle, red);
    draw(circumcircle(B, C, Y), grey);
    pair D = IP(A--Q, circumcircle(B, C, Y));
    pair D_prime = -D+2*foot(circumcenter(B, C, Y), A, D);
    pair N = midpoint(A--C);
    pair M = midpoint(B--C);
    draw(A--D_prime, mediumblue);
    pair E = extension(N, origin, B, D);
    pair E_prime = extension(N, origin, B, D_prime);
    pair F = 2*E-B;
    pair F_prime = 2*E_prime-B;
    draw(F--B--D_prime, deepgreen);
    draw(E_prime--N, brown);
    draw(F--F_prime, brown);

    filldraw(circumcircle(B, E, E_prime), opacity(0.2)+grey, red+1.1);

    filldraw(M--E--E_prime--cycle, opacity(0.1)+yellow, brown+1.1);
    filldraw(D--C--D_prime--cycle, opacity(0.1)+cyan, heavycyan+1.1);
    filldraw(F--C--F_prime--cycle, opacity(0.1)+yellow, brown+1.1);

    dot("$A$", A, dir(225));
    dot("$C$", C, dir(315));
    dot("$B$", B, dir(160));
    dot("$Q$", Q, dir(130));
    dot("$D$", D, dir(180));
    dot("$D'$", D_prime, dir(D_prime));
    dot(N);
    dot("$M$", M, dir(65));
    dot("$E$", E, dir(225));
    dot("$E'$", E_prime, dir(E_prime));
    dot("$F$", F, dir(F));
    dot("$F'$", F_prime, dir(F_prime));

    /* -----------------------------------------------------------------+
    |                 TSQX: by CJ Quines and Evan Chen                  |
    | https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
    +-------------------------------------------------------------------+
    !size(11cm);
    A 225 = dir 185
    C 315 = dir 355
    B 160 = dir 115
    Q 130 = A*C/B
    X := extension A B Q C
    Y := 2*X-A
    A--B--C--cycle / 0.1 lightred / red
    unitcircle / red
    circumcircle B C Y / grey
    D 180 = IP A--Q (circumcircle B C Y)
    D' = -D+2*foot (circumcenter B C Y) A D
    N .= midpoint A--C
    M 65 = midpoint B--C
    A--D' / mediumblue
    E 225 = extension N origin B D
    E' = extension N origin B D'
    F = 2*E-B
    F' = 2*E'-B
    F--B--D' / deepgreen
    E'--N / brown
    F--F' / brown
    circumcircle E B E' / 0.2 grey / red 1.1
    M--E--E'--cycle / 0.1 yellow / brown 1.1
    D--C--D'--cycle / 0.1 cyan / heavycyan 1.1
    F--C--F'--cycle / 0.1 yellow / brown 1.1
    */
  \end{asy}
  \end{center}
  One can already prove using angle chasing that $\ol{AB}$ is tangent to $(BEE')$.
  So the point of the problem is to show that $M$ lies on this circle too.
  However, from looking at the diagram, one may realize that in fact it seems
  \[ \triangle MEE' \overset{+}{\sim} \triangle CDD' \]
  is going to be true from just those marked in the figure
  (and this would certainly imply the desired concyclic conclusion).
  Since $M$ is a midpoint, it makes sense to dilate $\triangle EME'$
  from $B$ by a factor of $2$ to get $\triangle FCF'$
  so that the desired similarity is actually a spiral similarity at $C$.
  Then the spiral similarity lemma says that the desired similarity
  is equivalent to requiring $\ol{DD'} \cap \ol{FF'} = Q$
  to lie on both $(CDF)$ and $(CD'F')$.
  Hence the key construction and claim from the solution are both discovered naturally,
  and we find the solution above.
  (The points $D'$, $E'$, $F'$ can then be deleted to hide the motivation.)
\end{remark*}

\paragraph{Another short solution.}
Let $Z$ be on line $BDE$ such that $\angle BAZ = 90\dg$.
This lets us interpret the angle condition as follows:
\begin{claim*}
  Points $A$, $D$, $Z$, $C$ are cyclic.
\end{claim*}
\begin{proof}
  Because $\dang ZAC = 90\dg - A = 180\dg - \dang CDB = \dang ZDC$.
\end{proof}

\begin{center}
\begin{asy}
size(8cm);
pair A = dir(185);
pair C = dir(355);
pair B = dir(110);
pair Q = A*C/B;
pair X = extension(A, B, Q, C);
pair Y = 2*X-A;
filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
draw(unitcircle, red);
pair D = IP(A--Q, circumcircle(B, C, Y));
pair N = midpoint(A--C);
pair M = midpoint(B--C);
draw(A--Q, mediumblue);
pair E = extension(N, origin, B, D);
pair S = dir(90);
draw(S--N, brown);
draw(M--E, blue);
pair Z = extension(B, D, A, -B);
draw(A--Z--B, deepgreen);
filldraw(circumcircle(A, D, Z), opacity(0.1)+palecyan, deepgreen);
pair W = midpoint(B--Z);
pair O = origin;
draw(M--W--O--cycle, deepgreen);

filldraw(circumcircle(E, O, M), opacity(0.1)+palecyan, deepgreen);

dot("$A$", A, dir(180));
dot("$C$", C, dir(0));
dot("$B$", B, dir(140));
dot("$D$", D, dir(160));
dot("$N$", N, dir(N));
dot("$M$", M, dir(90));
dot("$E$", E, dir(225));
dot("$Z$", Z, dir(Z));
dot("$W$", W, dir(250));
dot("$O$", O, dir(180));

/* -----------------------------------------------------------------+
|                 TSQX: by CJ Quines and Evan Chen                  |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(8cm);
A 180 = dir 185
C 0 = dir 355
B 140 = dir 110
Q := A*C/B
X := extension A B Q C
Y := 2*X-A
A--B--C--cycle / 0.1 lightred / red
unitcircle / red
D 160 = IP A--Q (circumcircle B C Y)
N = midpoint A--C
M 90 = midpoint B--C
A--Q / mediumblue
E 225 = extension N origin B D
S := dir 90
S--N / brown
M--E / blue
Z = extension B D A -B
A--Z--B / deepgreen
circumcircle A D Z / 0.1 palecyan / deepgreen
W 250 = midpoint B--Z
O 180 = origin
M--W--O--cycle / deepgreen
circumcircle E O M / 0.1 palecyan / deepgreen
*/
\end{asy}
\end{center}

Define $W$ as the midpoint of $\ol{BZ}$, so $\ol{MW} \parallel \ol{CZ}$.
And let $O$ denote the center of $(ABC)$.

\begin{claim*}
  Points $M$, $E$, $O$, $W$ are cyclic.
\end{claim*}
\begin{proof}
  Note that
  \begin{align*}
    \dang MOE
    &= \dang(\ol{OM},\ol{BC}) + \dang(\ol{BC},\ol{AC}) + \dang(\ol{AC},\ol{OE}) \\
    &= 90\dg + \dang BCA + 90\dg \\
    &= \dang BCA = \dang CAD = \dang CZD = \dang MWD = \dang MWE. \qedhere
  \end{align*}
\end{proof}
To finish, note
\begin{align*}
  \dang MEB &= \dang MEW = \dang MOW \\
  &= \dang(\ol{MO}, \ol{BC}) + \dang(\ol{BC}, \ol{AB}) + \dang(\ol{AB}, \ol{OW}) \\
  &= 90\dg + \dang CBA + 90\dg = \dang CBA = \dang MBA.
\end{align*}
This implies the desired tangency.

\paragraph{A Menelaus-based approach (Kevin Ren).}
Let $P$ be on $\ol{BC}$ with $AP=PC$.
Let $Y$ be the point on line $AB$ such that $\angle ACY = 90\dg$;
as $\angle AYC = 90\dg - A$ it follows $BDYC$ is cyclic.
Let $K = \ol{AP} \cap \ol{CY}$,
so $\triangle ACK$ is a right triangle with $P$ the midpoint of its hypotenuse.

\begin{center}
\begin{asy}
size(12cm);
pair A = dir(185);
pair C = dir(355);
pair B = dir(115);
pair Q = A*C/B;
pair X = extension(A, B, Q, C);
pair Y = 2*X-A;
filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
draw(unitcircle, red);
filldraw(circumcircle(B, C, Y), opacity(0.1)+palecyan, deepcyan);
pair D = IP(A--Q, circumcircle(B, C, Y));
pair N = midpoint(A--C);
pair M = midpoint(B--C);
pair E = extension(N, origin, B, D);
pair P = extension(A, Q, B, C);
pair Y = extension(A, B, C, -A);
draw(B--Y--C, red);
pair K = extension(A, P, C, Y);
draw(A--K, blue);
filldraw(B--E--M--cycle, opacity(0.1)+yellow, deepgreen);
filldraw(Y--D--C--cycle, opacity(0.1)+yellow, deepgreen);
draw(Y--P, grey);
draw(P--N, brown);

dot("$A$", A, dir(225));
dot("$C$", C, dir(315));
dot("$B$", B, dir(160));
dot(Q);
dot("$D$", D, dir(180));
dot(N);
dot("$M$", M, dir(35));
dot("$E$", E, dir(225));
dot("$P$", P, dir(100));
dot("$Y$", Y, dir(Y));
dot("$K$", K, dir(20));

/* -----------------------------------------------------------------+
|                 TSQX: by CJ Quines and Evan Chen                  |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(11cm);
A 225 = dir 185
C 315 = dir 355
B 160 = dir 115
Q 130 .= A*C/B
X := extension A B Q C
Y := 2*X-A
A--B--C--cycle / 0.1 lightred / red
unitcircle / red
circumcircle B C Y / 0.1 palecyan / deepcyan
D 180 = IP A--Q (circumcircle B C Y)
N .= midpoint A--C
M 35 = midpoint B--C
E 225 = extension N origin B D
P 100 = extension A Q B C
Y = extension A B C -A
B--Y--C / red
K 20 = extension A P C Y
A--K blue
B--E--M--cycle / 0.1 yellow / deepgreen
Y--D--C--cycle / 0.1 yellow / deepgreen
Y--P / grey
P--N / brown
*/
\end{asy}
\end{center}

\begin{claim*}
  Triangles $BPE$ and $DYK$ are similar.
\end{claim*}
\begin{proof}
  We have $\dang MPE = \dang CPE = \dang KCP = \dang PKC$
  and $\dang EBP = \dang DBC = \dang DYC = \dang DYK$.
\end{proof}
\begin{claim*}
  Triangles $BEM$ and $YDC$ are similar.
\end{claim*}
\begin{proof}
  By Menelaus $\triangle PCK$ with respect to collinear points $A$, $B$, $Y$ that
  \[ \frac{BP}{BC} \frac{YC}{YK} \frac{AK}{AP} = 1. \]
  Since $AK/AP = 2$ (note that $P$ is the midpoint of the hypotenuse of right triangle $ACK$)
  and $BC = 2BM$, this simplifies to
  \[ \frac{BP}{BM} = \frac{YK}{YC}. \qedhere \]
\end{proof}
To finish, note that
\[ \dang DBA = \dang DBY = \dang DCY = \dang BME \]
implying the desired tangency.

\paragraph{A spiral similarity approach (Hans Yu).}
As in the previous solution,
let $Y$ be the point on line $AB$ such that $\angle ACY = 90\dg$;
so $BDYC$ is cyclic.
Let $\Gamma$ be the circle through $B$ and $M$ tangent to $\ol{AB}$,
and let $\Omega \coloneqq (BCYD)$.
We need to show $E \in \Gamma$.

\begin{center}
\begin{asy}
size(11cm);
pair A = dir(185);
pair C = dir(355);
pair B = dir(110);
pair Q = A*C/B;
pair H = extension(A, B, Q, C);
pair Y = 2*H-A;
filldraw(A--B--C--cycle, opacity(0.1)+lightred, red);
draw(unitcircle, red);
filldraw(circumcircle(B, C, Y), opacity(0.1)+palecyan, deepcyan+1.2);
pair D = IP(A--Q, circumcircle(B, C, Y));
pair N = midpoint(A--C);
pair M = midpoint(B--C);
pair E = extension(N, origin, B, D);
pair P = extension(A, Q, B, C);
pair Y = extension(A, B, C, -A);
draw(C--Y, grey);
draw(B--Y, red);
draw(A--Q, red);
filldraw(circumcircle(B, M, E), opacity(0.1)+palecyan, deepcyan+1.2);
draw(B--E, red);
pair S = -B+2*foot(B, circumcenter(B, M, E), circumcenter(B, C, Y));
pair O = circumcenter(A, B, C);
filldraw(O--B--M--cycle, opacity(0.2)+yellow, deepgreen+1.2);
draw(P--O, red);
pair O_1 = circumcenter(B, M, E);
pair O_2 = circumcenter(B, C, Y);
label("$\Gamma$", O_1+abs(O_1-B)*dir(80), dir(80), deepcyan);
label("$\Omega$", O_2+abs(O_2-B)*dir(320), dir(320), deepcyan);

dot("$A$", A, dir(225));
dot("$C$", C, dir(315));
dot("$B$", B, dir(160));
dot(Q);
dot("$D$", D, dir(80));
dot("$M$", M, dir(20));
dot("$E$", E, dir(290));
dot("$P$", P, dir(90));
dot("$Y$", Y, dir(Y));
dot("$S$", S, dir(80));
dot("$O$", O, dir(180));

/* -----------------------------------------------------------------+
|                 TSQX: by CJ Quines and Evan Chen                  |
| https://github.com/vEnhance/dotfiles/blob/main/py-scripts/tsqx.py |
+-------------------------------------------------------------------+
!size(11cm);
A 225 = dir 185
C 315 = dir 355
B 160 = dir 110
Q 130 .= A*C/B
H := extension A B Q C
Y := 2*H-A
A--B--C--cycle / 0.1 lightred / red
unitcircle / red
circumcircle B C Y / 0.1 palecyan / deepcyan 1.2
D 80 = IP A--Q (circumcircle B C Y)
N := midpoint A--C
M 20 = midpoint B--C
E 290 = extension N origin B D
P 90 = extension A Q B C
Y = extension A B C -A
C--Y / grey
B--Y / red
A--Q / red
circumcircle B M E / 0.1 palecyan / deepcyan 1.2
B--E / red
S 80 = -B+2*foot B (circumcenter B M E) (circumcenter B C Y)
O 180 = circumcenter A B C
O--B--M--cycle / 0.2 yellow / deepgreen 1.2
P--O / red
O_1 := circumcenter B M E
O_2 := circumcenter B C Y
!label("$\Gamma$", O_1+abs(O_1-B)*dir(80), dir(80), deepcyan);
!label("$\Omega$", O_2+abs(O_2-B)*dir(320), dir(320), deepcyan);
*/
\end{asy}
\end{center}

Denote by $S$ the second intersection of $\Gamma$ and $\Omega$.
The main idea behind is to consider the spiral similarity
\[ \Psi : \Omega \to \Gamma \qquad C \mapsto M \text{ and } Y \mapsto B \]
centered at $S$ (due to the spiral similarity lemma), and show that $\Psi(D) = E$.
The spiral similarity lemma already promises $\Psi(D)$ lies on line $BD$.
\begin{claim*}
  We have $\Psi(A) = O$, the circumcenter of $ABC$.
\end{claim*}
\begin{proof}
  Note $\triangle OBM \overset{+}{\sim} \triangle AYC$;
  both are right triangles with $\dang BAC = \dang BOM$.
\end{proof}
\begin{claim*}
  $\Psi$ maps line $AD$ to line $OP$.
\end{claim*}
\begin{proof}
  If we let $P$ be on $\ol{BC}$ with $AP=PC$ as before,
  \[ \dang(\ol{AD}, \ol{OP}) = \dang APO = \dang OPC = \dang YCP = \dang(\ol{YC}, \ol{BM}). \]
  As $\Psi$ maps line $YC$ to line $BM$ and $\Psi(A) = O$, we're done.
\end{proof}
Hence $\Psi(D)$ should not only lie on $BD$ but also line $OP$.
This proves $\Psi(D) = E$, so $E \in \Gamma$ as needed.
\pagebreak

\subsection{USAMO 2024/6, proposed by Titu Andreescu and Gabriel Dospinescu}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n > 2$ be an integer and let $\ell \in \{1, 2,\dots, n\}$.
A collection $A_1$, \dots, $A_k$ of (not necessarily distinct) subsets of
$\{1, 2,\dots, n\}$ is called $\ell$-large if $|A_i| \ge \ell$ for all $1 \le i \le k$.
Find, in terms of $n$ and $\ell$, the largest real number $c$ such that the inequality
\[ \sum_{i=1}^k\sum_{j=1}^k x_ix_j \frac{|A_i\cap A_j|^2}{|A_i|\cdot|A_j|}
  \ge c\left(\sum_{i=1}^k x_i\right)^2 \]
holds for all positive integer $k$,
all nonnegative real numbers $x_1$, $x_2$, \dots, $x_k$,
and all $\ell$-large collections $A_1$, $A_2$, \dots, $A_k$
of subsets of $\{1,2,\dots,n\}$.
\end{mdframed}
The answer turns out to be
\[ c = \frac{n+\ell^2-2\ell}{n(n-1)}. \]
Throughout this solution, we work with vectors in $\RR^{n^2}$.
The entries will be indexed by ordered pairs $(p,q) \in \{1, \dots, n\}^2$;
the notation
$\left< \bullet,\bullet \right>$ denotes dot product,
and $\lVert \bullet \rVert$ the vector norm.

\paragraph{Rewriting as a dot product.}
For $i=1,\dots,n$ define $\mathbf{v}_i$ by
\[ \mathbf{v}_i[p,q] \coloneqq \begin{cases}
  \frac{1}{|A_i|} & p \in A_i \text{ and } q \in A_i \\
  0 & \text{otherwise};
  \end{cases}
  \qquad \mathbf{v} \coloneqq \sum_i x_i \mathbf{v}_i
\]
Then
\begin{align*}
  \sum_i \sum_j x_ix_j \frac{|A_i\cap A_j|^2}{|A_i||A_j|}
  &= \sum_i \sum_j x_ix_j \left< \mathbf{v}_i, \mathbf{v}_j\right> \\
  &= \left< \sum_i x_i \mathbf{v}_i, \sum_j x_i \mathbf{v}_i \right>
  = \left\lVert \sum_i x_i \mathbf{v}_i \right\rVert^2 =
  \left\lVert \mathbf{v} \right\rVert^2.
\end{align*}

\paragraph{Proof of the inequality for the claimed value of $c$.}
We define two more vectors $\mathbf{e}$ and $\mathbf{1}$;
the vector $\mathbf{e}$ has $1$ in the $(p,q)$\ts{th} component if $p=q$, and $0$
otherwise, while $\mathbf{1}$ has all-ones.
In that case, note that
\begin{align*}
  \left< \mathbf{e}, \mathbf{v} \right> &= \sum_i x_i \left< \mathbf{e}, \mathbf{v}_i \right> = \sum_i x_i \\
  \left< \mathbf{1}, \mathbf{v} \right> &= \sum_i x_i \left< \mathbf{1}, \mathbf{v}_i \right> = \sum_i x_i |A_i|.
\end{align*}
That means for any positive real constants $\alpha$ and $\beta$,
by Cauchy-Schwarz for vectors, we should have
\begin{align*}
  \left\lVert \alpha \mathbf{e} + \beta \mathbf{1} \right\rVert \left\lVert \mathbf{v} \right\rVert
  &\ge \left< \alpha \mathbf{e} + \beta \mathbf{1}, \mathbf{v} \right>
  = \alpha \left< \mathbf{e}, \mathbf{v}\right> + \beta \left< \mathbf{1}, \mathbf{v} \right> \\
  &= \alpha \cdot \sum x_i + \beta \cdot \sum x_i |A_i| \\
  &\ge (\alpha + \ell \beta) \sum x_i.
\end{align*}
Set $\mathbf{w} \coloneqq \alpha \mathbf{e} + \beta \mathbf{1}$ for brevity.
Then
\[ \mathbf{w}[p,q] =
  \begin{cases}
    \alpha + \beta & \text{if } p = q \\
    \beta & \text{if }p \neq q
  \end{cases}
\]
so
\[ \left\lVert \mathbf{w} \right\rVert = \sqrt{n \cdot (\alpha + \beta)^2 + (n^2-n) \cdot \beta^2}. \]
Therefore, we get an lower bound
\[ \frac{\left\lVert \mathbf{v} \right\rVert}{\sum x_i}
  \ge \frac{\alpha + \ell \beta}{\sqrt{n \cdot (\alpha + \beta)^2 + (n^2-n) \cdot \beta^2}} \]
Letting $\alpha = n - \ell$ and $\beta = \ell-1$ gives a proof that the constant
\[ c = \frac{((n-\ell)+\ell(\ell-1))^2}{n \cdot (n-1)^2 + (n^2-n) \cdot (\ell-1)^2}
  = \frac{(n+\ell^2-2\ell)^2}{n(n-1)\left( n+\ell^2-2\ell \right)}
  = \frac{n+\ell^2-2\ell}{n(n-1)} \]
makes the original inequality always true.
(The choice of $\alpha:\beta$ is suggested by the example below.)

\paragraph{Example showing this $c$ is best possible.}
Let $k = \binom{n}{\ell}$, let $A_i$ run over all $\binom{n}{\ell}$
subsets of $\{1, \dots, n\}$ of size $\ell$, and let $x_i = 1$ for all $i$.
We claim this construction works.

To verify this, it would be sufficient to show that $\mathbf{w}$
and $\mathbf{v}$ are scalar multiples, so that the above Cauchy-Schwarz is equality.
However, we can compute
\[
  \mathbf{w}[p,q] =
  \begin{cases}
    n-1 & \text{if } p = q \\
    \ell-1 & \text{if }p \neq q
  \end{cases},
  \qquad
  \mathbf{v}[p,q] =
  \begin{cases}
    \binom{n-1}{\ell-1} \cdot \frac{1}{\ell} & \text{if } p = q \\
    \binom{n-2}{\ell-2} \cdot \frac{1}{\ell} & \text{if } p \neq q
  \end{cases}
\]
which are indeed scalar multiples, finishing the proof.
\pagebreak


\end{document}
