2025 USAJMO Problems/Problem 4

Problem

Let $n$ be a positive integer, and let $a_0,\,a_1,\dots,\,a_n$ be nonnegative integers such that $a_0\ge a_1\ge \dots\ge a_n.$ Prove that $\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.$ Note: $\binom{k}{2}=\frac{k(k-1)}{2}$ for all nonnegative integers $k$ .

Solution 1

By Vandermonde's, $\frac 12\binom{\sum a_i}2=\frac 12\left(\sum\binom{a_i}2+\sum_\text{sym}a_ia_j\right)\ge\frac 12\sum ia_i^2\ge\sum i\binom{a_i}2,$ with equality at $a_0=0,1$ and $a_i=0$ for $i>0.~\square$

~rhydon516 (sol credits to leo)

Solution 2

We proceed by induction.

Base case: $n=1$ . Note that $\frac{1}{2}\binom{a_0+a_1}{2} \ge \frac{1}{2}\binom{a_1+a_1}{2} = 2a_1(2a_1-1)/4 \ge a_1(a_1-1)/2 = \binom{a_1}2$

Inductive Hypothesis: Assume $\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}$

Inductive Step: We try to show it works for $n+1$ : $\sum_{i=0}^{n+1} i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_{n+1}}{2}$

By the Inductive Hypothesis all we need to show is $(n+1)\binom{a_{n+1}}{2}\le \frac{1}{2}\binom{a_0+a_1+\dots+a_{n+1}}{2}-\frac{1}{2}\binom{a_0+a_1+\dots+a_{n}}{2}$

Let $s=a_0+a_1+..+a_n$ and $c=a_{n+1}$ . Now we need $(n+1)\binom{c}{2}\le \frac{1}{2}\binom{s+c}{2}-\frac{1}{2}\binom{s}{2}$ . The LHS is $\frac{1}{2}(n+1)(c)(c-1)$ the RHS is $\frac{1}{4}(2sc+c^2-c)$ . If $c=0$ we're done, otherwise we divide by $c$ and multiply by $4$ to get $2(n+1)(c-1)=2nc+2c-2n-2$ which we are trying to show is $\le 2s+c-1$ . Note that $s\ge (n+1)c$ by the problem statement condition. So it simplifies to $2nc+2c-2n-2 \le 2nc+3c-1$ which is obvious.

2025 USAJMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2025 USAJMO Problems/Problem 4

Contents

Problem

Solution 1

Solution 2

See Also