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 USAMO Problems/Problem 5"

(→‎Solution 1)
(→‎Solution 2 (q-analogue via q-Chu–Vandermonde))
 
(10 intermediate revisions by the same user not shown)
Line 9: Line 9:
  
 
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg
 
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg
 +
 +
== Solution 2 (combinatorial via Burnside’s lemma) ==
 +
 +
Let 
 +
<cmath>
 +
X=\{(A_1,\dots,A_k):A_j\subseteq\{1,\dots,n\},\;|A_1|=\cdots=|A_k|\}.
 +
</cmath>
 +
 +
Then 
 +
<cmath>
 +
|X|=\sum_{i=0}^n\binom{n}{i}^k.
 +
</cmath>
 +
 +
The cyclic group <math>C_{n+1}</math> acts on <math>\{1,\dots,n+1\}</math> by “add 1 mod <math>n+1</math>,” and hence diagonally on <math>X</math>.
 +
 +
By Burnside’s lemma, 
 +
<cmath>
 +
|X/C_{n+1}|=\frac1{n+1}\sum_{g\in C_{n+1}}|\mathrm{Fix}(g)|.
 +
</cmath>
 +
 +
If <math>g</math> has order <math>d\mid(n+1)</math> then <math>\mathrm{Fix}(g)</math> consists of choosing each <math>A_j</math> as a union of the <math>(n+1)/d</math> orbits of <math>g</math>, so 
 +
<cmath>
 +
|\mathrm{Fix}(g)|=\sum_{i=0}^n\binom{d}{i}^k.
 +
</cmath>
 +
 +
Thus 
 +
<cmath>
 +
(n+1)\,|X/C_{n+1}|=\sum_{d\mid(n+1)}\varphi\Bigl(\tfrac{n+1}d\Bigr)\,
 +
\sum_{i=0}^n\binom{d}{i}^k.
 +
</cmath>
 +
 +
Case 1: <math>k=2m</math> even 
 +
 +
We prove by induction on the divisor‐lattice of <math>n+1</math> that for every proper divisor <math>d<n+1</math>, 
 +
<cmath>
 +
d\mid\sum_{i=0}^n\binom{d}{i}^{2m}.
 +
</cmath>
 +
 +
Then each term <math>\varphi\bigl((n+1)/d\bigr)\sum_i\binom{d}{i}^{2m}</math> is divisible by <math>\varphi\bigl((n+1)/d\bigr)\,d</math>, and since 
 +
<cmath>
 +
\sum_{d\mid(n+1),\,d<n+1}\varphi\Bigl(\tfrac{n+1}d\Bigr)\,d
 +
=(n+1)-\varphi(1)\cdot1
 +
=n+1-1,
 +
</cmath>
 +
the entire sum on the right is congruent modulo <math>n+1</math> to 
 +
<cmath>
 +
\varphi(1)\sum_{i=0}^n\binom{n+1}{i}^{2m}
 +
=1\cdot\sum_{i=0}^n\binom{n+1}{i}^{2m}.
 +
</cmath>
 +
 +
But the left side <math>(n+1)\,|X/C_{n+1}|\equiv0\pmod{n+1}</math>, so 
 +
<cmath>
 +
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n+1}{i}^{2m}.
 +
</cmath>
 +
 +
A re‐index <math>n+1\mapsto n</math> yields 
 +
<cmath>
 +
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n}{i}^{2m},
 +
</cmath>
 +
hence 
 +
<cmath>
 +
A_{2m}(n)=\frac1{n+1}\sum_{i=0}^n\binom{n}{i}^{2m}\in\mathbb Z.
 +
</cmath>
 +
 +
Case 2: <math>k</math> odd 
 +
 +
Take <math>n=2</math>.  Then 
 +
<cmath>
 +
A_k(2)=\frac{\binom21^k+\binom22^k+\binom23^k}{3}
 +
=\frac{1+2^k+1}{3}
 +
=\frac{2+2^k}{3}.
 +
</cmath>
 +
 +
If <math>k</math> is odd then <math>2^k\equiv2\pmod3</math>, so <math>2+2^k\equiv4\equiv1\pmod3</math>, whence 
 +
<cmath>
 +
A_k(2)\notin\mathbb Z.
 +
</cmath>
 +
 +
Conclusion 
 +
 +
<math>A_k(n)\in\mathbb Z\text{ for all }n\ge1\iff k\text{ even.}</math>
  
 
==See Also==
 
==See Also==
 
{{USAMO newbox|year=2025|num-b=4|num-a=6}}
 
{{USAMO newbox|year=2025|num-b=4|num-a=6}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 08:49, 28 June 2025

Problem

Determine, with proof, all positive integers $k$ such that\[\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k\]is an integer for every positive integer $n.$

Solution 1

https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_1.jpg

https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg

Solution 2 (combinatorial via Burnside’s lemma)

Let \[X=\{(A_1,\dots,A_k):A_j\subseteq\{1,\dots,n\},\;|A_1|=\cdots=|A_k|\}.\]

Then \[|X|=\sum_{i=0}^n\binom{n}{i}^k.\]

The cyclic group $C_{n+1}$ acts on $\{1,\dots,n+1\}$ by “add 1 mod $n+1$,” and hence diagonally on $X$.

By Burnside’s lemma, \[|X/C_{n+1}|=\frac1{n+1}\sum_{g\in C_{n+1}}|\mathrm{Fix}(g)|.\]

If $g$ has order $d\mid(n+1)$ then $\mathrm{Fix}(g)$ consists of choosing each $A_j$ as a union of the $(n+1)/d$ orbits of $g$, so \[|\mathrm{Fix}(g)|=\sum_{i=0}^n\binom{d}{i}^k.\]

Thus \[(n+1)\,|X/C_{n+1}|=\sum_{d\mid(n+1)}\varphi\Bigl(\tfrac{n+1}d\Bigr)\, \sum_{i=0}^n\binom{d}{i}^k.\]

Case 1: $k=2m$ even

We prove by induction on the divisor‐lattice of $n+1$ that for every proper divisor $d<n+1$, \[d\mid\sum_{i=0}^n\binom{d}{i}^{2m}.\]

Then each term $\varphi\bigl((n+1)/d\bigr)\sum_i\binom{d}{i}^{2m}$ is divisible by $\varphi\bigl((n+1)/d\bigr)\,d$, and since \[\sum_{d\mid(n+1),\,d<n+1}\varphi\Bigl(\tfrac{n+1}d\Bigr)\,d =(n+1)-\varphi(1)\cdot1 =n+1-1,\] the entire sum on the right is congruent modulo $n+1$ to \[\varphi(1)\sum_{i=0}^n\binom{n+1}{i}^{2m} =1\cdot\sum_{i=0}^n\binom{n+1}{i}^{2m}.\]

But the left side $(n+1)\,|X/C_{n+1}|\equiv0\pmod{n+1}$, so \[n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n+1}{i}^{2m}.\]

A re‐index $n+1\mapsto n$ yields \[n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n}{i}^{2m},\] hence \[A_{2m}(n)=\frac1{n+1}\sum_{i=0}^n\binom{n}{i}^{2m}\in\mathbb Z.\]

Case 2: $k$ odd

Take $n=2$. Then \[A_k(2)=\frac{\binom21^k+\binom22^k+\binom23^k}{3} =\frac{1+2^k+1}{3} =\frac{2+2^k}{3}.\]

If $k$ is odd then $2^k\equiv2\pmod3$, so $2+2^k\equiv4\equiv1\pmod3$, whence \[A_k(2)\notin\mathbb Z.\]

Conclusion

$A_k(n)\in\mathbb Z\text{ for all }n\ge1\iff k\text{ even.}$

See Also

2025 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO 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_USAMO_Problems/Problem_5&oldid=252597"