Problem: 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}

Solution: The answer turns out to be
\[ c = \frac{n+\ell^2-2\ell}{n(n-1)}. \]
The following solution using indicator functions was
suggested by the language reasoning system developed by Thang Luong
and the team at Google DeepMind (\url{https://dpmd.ai/imo-silver}).

\paragraph{Rewriting the sum.}
Abbreviate $[n] \coloneq \{1, \dots, n\}$,
and WLOG assume $\sum x_i = 1$.
To prove the bound, we first rewrite the left-hand side using indicator functions
and switch the order of summation as
\begin{align*}
  \text{LHS}
  &= \sum_{i=1}^k\sum_{j=1}^k \frac{x_i}{|A_i|} \frac{x_j}{|A_j|} |A_i\cap A_j|^2 \\
  &= \sum_{i=1}^k\sum_{j=1}^k \frac{x_i}{|A_i|} \frac{x_j}{|A_j|}
  \left( \sum_{p \in [n]} \sum_{q \in [n]} \mathbf{1}_{p \in A_i} \mathbf{1}_{q \in A_j} \right) \\
  &= \sum_{p \in [n]} \sum_{q \in [n]} \sum_{i=1}^k\sum_{j=1}^k
  \frac{x_i \mathbf{1}_{p \in A_i}}{|A_i|} \cdot \frac{x_j \mathbf{1}_{q \in A_j}}{|A_j|}.
\end{align*}
Hence, if we define the $n^2$ variables
\[ v_{p,q} \coloneq \sum_{i : p,q \in A_i} \frac{x_i}{|A_i|} \]
for each $(p,q) \in [n]^2$
then the previous expression simplifies to just
\[ \text{LHS} = \sum_{p \in [n]} \sum_{q \in [n]} v_{p,q}^2. \]

\paragraph{Proof of bound.}
We split the sum into $p=q$ versus $p \neq q$ and bound by QM-AM
separately in the obvious way.
For the terms $p=q$,
\begin{align*}
  \sum_{p \in [n]} v_{p,p}
    &= \sum_{i=1}^k |A_i| \cdot \frac{x_i}{|A_i|} = \sum_{i=1}^k x_i = 1 \\
  \implies \sum_{p \in [n]} v_{p,p}^2
    &\ge \frac{\left( \sum_{p \in [n]} v_{p,p} \right)^2}{n} = \frac 1n.
\end{align*}
When $p \neq q$ we instead have
\begin{align*}
  \sum_{p \neq q \in [n]} v_{p,q}
    &= \sum_{i=1}^k 2 \binom{|A_i|}{2} \cdot \frac{x_i}{|A_i|}
    = \sum_{i=1}^k (|A_i|-1) x_i \ge \sum_{i=1}^k (\ell-1) x_i = \ell-1 \\
  \implies \sum_{p \neq q \in [n]} v_{p,q}^2
    &\ge \frac{\left( \sum_{p \neq q \in [n]} v_{p,q} \right)^2}{n(n-1)}
    \ge \frac{(\ell-1)^2}{n(n-1)}.
\end{align*}
Combining the two bounds gives
\[ \text{LHS} \ge \frac 1n + \frac{(\ell-1)^2}{n(n-1)} = \frac{n+\ell^2-2\ell}{n(n-1)} \]
which matches the answer claimed above.

\paragraph{Construction.}
Equality occurs if $v_{p,p}$ is the same for all $p$
and $v_{p,q}$ is the same for all $p \neq q$,
and $|A_i| = \ell$ for all $i$.
This occurs if one takes, say, $k = \binom{n}{\ell}$ and $A_i$ to be
all the subsets of size $\ell$ each exactly once.


\begin{remark*}
  Originally, the write-up I used considered vectors in $\RR^{n^2}$
  where entries will be indexed by ordered pairs $(p,q) \in \{1, \dots, n\}^2$.
  It was equivalent to the solution above, but looking back,
  I think this makes the problem look harder than it actually is.

  For comparison, here is how the notation with vectors works, using
  $\left< \bullet,\bullet \right>$ for dot product, and $\lVert \bullet \rVert$ for the vector norm.
  For $i=1,\dots,n$ define $\mathbf{v}_i$ by
  \[ \mathbf{v}_i[p,q] \coloneq \begin{cases}
    \frac{1}{|A_i|} & p \in A_i \text{ and } q \in A_i \\
    0 & \text{otherwise};
    \end{cases}
    \qquad \mathbf{v} \coloneq \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< \mathbf{v}, \mathbf{v} \right> = \left\lVert \mathbf{v} \right\rVert^2.
  \end{align*}
  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} \coloneq \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}
    \implies \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.)

  Meanwhile, for the construction (where $k = \binom{n}{\ell}$, etc.)
  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.
\end{remark*}