Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 USAJMO Problems/Problem 4"

(→‎Solution: Edited cyc to sym in sum)
(→‎Solution 2)
 
(One intermediate revision by the same user not shown)
Line 4: Line 4:
 
Let <math>n</math> be a positive integer, and let <math>a_0,\,a_1,\dots,\,a_n</math> be nonnegative integers such that <math>a_0\ge a_1\ge \dots\ge a_n.</math> Prove that<cmath>\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.</cmath>Note: <math>\binom{k}{2}=\frac{k(k-1)}{2}</math> for all nonnegative integers <math>k</math>.
 
Let <math>n</math> be a positive integer, and let <math>a_0,\,a_1,\dots,\,a_n</math> be nonnegative integers such that <math>a_0\ge a_1\ge \dots\ge a_n.</math> Prove that<cmath>\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}.</cmath>Note: <math>\binom{k}{2}=\frac{k(k-1)}{2}</math> for all nonnegative integers <math>k</math>.
  
−
== Solution ==
+
== Solution 1 ==
  
 
By Vandermonde's,
 
By Vandermonde's,
Line 10: Line 10:
  
 
~rhydon516 (sol credits to leo)
 
~rhydon516 (sol credits to leo)
 +
 +
== Solution 2 ==
 +
 +
We proceed by induction.
 +
 +
Base case: <math>n=1</math>. Note that <math>\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</math>
 +
 +
Inductive Hypothesis: Assume <math>\sum_{i=0}^n i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_n}{2}</math>
 +
 +
Inductive Step: We try to show it works for <math>n+1</math>: <math>\sum_{i=0}^{n+1} i\binom{a_i}{2}\le\frac{1}{2}\binom{a_0+a_1+\dots+a_{n+1}}{2}</math>
 +
 +
By the Inductive Hypothesis all we need to show is <math>(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}</math>
 +
 +
Let <math>s=a_0+a_1+..+a_n</math> and <math>c=a_{n+1}</math>. Now we need <math>(n+1)\binom{c}{2}\le \frac{1}{2}\binom{s+c}{2}-\frac{1}{2}\binom{s}{2}</math>. The LHS is <math>\frac{1}{2}(n+1)(c)(c-1)</math> the RHS is <math>\frac{1}{4}(2sc+c^2-c)</math>. If <math>c=0</math> we're done, otherwise we divide by <math>c</math> and multiply by <math>4</math> to get <math>2(n+1)(c-1)=2nc+2c-2n-2</math> which we are trying to show is <math>\le 2s+c-1</math>. Note that <math>s\ge (n+1)c</math> by the problem statement condition. So it simplifies to <math>2nc+2c-2n-2 \le 2nc+3c-1</math> which is obvious.
  
 
==See Also==
 
==See Also==

Latest revision as of 16:54, 7 August 2025

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.

See Also

https://artofproblemsolving.com/community/c5h3532101_bombardiro_crocodilo_vs_tralalero_tralala

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAJMO_Problems/Problem_4&oldid=256755"