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 2 (q-analogue roots of unity))
(→‎Solution 2 (q-analogue via q-Chu–Vandermonde))
 
(One intermediate revision by the same user not shown)
Line 10: Line 10:
 
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 (q-analogue via q-Chu–Vandermonde) ==
+
== Solution 2 (combinatorial via Burnside’s lemma) ==
  
−
Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
+
Let 
−
 
+
<cmath>
−
For any <math>n\ge1</math> set
+
X=\{(A_1,\dots,A_k):A_j\subseteq\{1,\dots,n\},\;|A_1|=\cdots=|A_k|\}.
 +
</cmath>
  
 +
Then 
 
<cmath>
 
<cmath>
−
[n]_q = 1 + q + \cdots + q^{n-1},
+
|X|=\sum_{i=0}^n\binom{n}{i}^k.
 
</cmath>
 
</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>
 
<cmath>
−
[n]_q! = \prod_{i=1}^n [i]_q,
+
|X/C_{n+1}|=\frac1{n+1}\sum_{g\in C_{n+1}}|\mathrm{Fix}(g)|.
 
</cmath>
 
</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>
 
<cmath>
−
\binom ni_q = \frac{[n]_q!}{[i]_q!\,[n-i]_q!}.
+
|\mathrm{Fix}(g)|=\sum_{i=0}^n\binom{d}{i}^k.
 
</cmath>
 
</cmath>
  
−
Then
+
Thus 
−
 
 
 
<cmath>
 
<cmath>
−
[n+1]_q = 1 + q + \cdots + q^n
+
(n+1)\,|X/C_{n+1}|=\sum_{d\mid(n+1)}\varphi\Bigl(\tfrac{n+1}d\Bigr)\,
−
= \frac{1 - q^{n+1}}{1 - q}
+
\sum_{i=0}^n\binom{d}{i}^k.
−
= \prod_{d \mid (n+1)} \Phi_d(q).
 
 
</cmath>
 
</cmath>
  
−
Define
+
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>
 
<cmath>
−
S_k(n;q) = \sum_{i=0}^n \binom ni_q^k.
+
d\mid\sum_{i=0}^n\binom{d}{i}^{2m}.
 
</cmath>
 
</cmath>
  
−
We must show
+
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>
 
<cmath>
−
A_k(n) = \frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z
+
\sum_{d\mid(n+1),\,d<n+1}\varphi\Bigl(\tfrac{n+1}d\Bigr)\,d
−
\quad\Longleftrightarrow\quad
+
=(n+1)-\varphi(1)\cdot1
−
k \text{ even}.
+
=n+1-1,
 
</cmath>
 
</cmath>
−
 
+
the entire sum on the right is congruent modulo <math>n+1</math> to  
−
It suffices to prove that for even <math>k=2m</math>, one has <math>[n+1]_q \mid S_{2m}(n;q)</math> in <math>\mathbb Z[q]</math>, and that for odd <math>k</math> there is some divisor of <math>n+1</math> at which <math>S_k(n;q)\neq0</math>.
 
−
 
 
−
Case <math>m=1</math>  
 
−
 
 
−
By the <math>q</math>-Chu–Vandermonde identity,
 
−
 
 
 
<cmath>
 
<cmath>
−
\sum_{i=0}^n \binom ni_q^2
+
\varphi(1)\sum_{i=0}^n\binom{n+1}{i}^{2m}
−
= \binom{2n}{n}_q
+
=1\cdot\sum_{i=0}^n\binom{n+1}{i}^{2m}.
−
= \frac{[2n]_q!}{[n]_q!^2}
 
−
= \frac{[n+1]_q\,[2n]_q!}{[n+1]_q\,[n]_q!^2}
 
−
= [n+1]_q \, Q_{n,1}(q),
 
 
</cmath>
 
</cmath>
  
−
with <math>Q_{n,1}(q)\in\mathbb Z[q]</math>.
+
But the left side <math>(n+1)\,|X/C_{n+1}|\equiv0\pmod{n+1}</math>, so  
−
 
 
−
Inductive step  
 
−
 
 
−
Assume for some <math>m\ge1</math>,
 
−
 
 
 
<cmath>
 
<cmath>
−
S_{2m}(n;q) = [n+1]_q \, Q_{n,m}(q),
+
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n+1}{i}^{2m}.
−
\quad
 
−
Q_{n,m}(q)\in\mathbb Z[q].
 
 
</cmath>
 
</cmath>
  
−
Then
+
A re‐index <math>n+1\mapsto n</math> yields 
−
 
 
 
<cmath>
 
<cmath>
−
S_{2(m+1)}(n;q)
+
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n}{i}^{2m},
−
= \sum_{i=0}^n \binom ni_q^2 \,\binom ni_q^{2m}
 
−
= \sum_{i=0}^n \binom ni_q^2 \,[n+1]_q \, Q_{n,m}(q).
 
 
</cmath>
 
</cmath>
−
 
+
hence 
−
Another application of <math>q</math>-Chu–Vandermonde yields
 
−
 
 
 
<cmath>
 
<cmath>
−
\sum_{i=0}^n \binom ni_q^2 \, Q_{n,m}(q)
+
A_{2m}(n)=\frac1{n+1}\sum_{i=0}^n\binom{n}{i}^{2m}\in\mathbb Z.
−
= [n+1]_q \, Q_{n,m+1}(q),
 
−
\quad
 
−
Q_{n,m+1}(q)\in\mathbb Z[q],
 
 
</cmath>
 
</cmath>
  
−
so <math>[n+1]_q\mid S_{2(m+1)}(n;q)</math>.
+
Case 2: <math>k</math> odd   
−
 
 
−
Case <math>k</math> odd   
 
−
 
 
−
Let <math>k=2m+1</math> and pick a prime <math>p>2</math> with <math>p\nmid k</math>.  Take <math>n=p-1</math> and let <math>\zeta</math> be a primitive <math>p</math>-th root of unity.  Then
 
  
 +
Take <math>n=2</math>.  Then 
 
<cmath>
 
<cmath>
−
S_k(p-1;\zeta)
+
A_k(2)=\frac{\binom21^k+\binom22^k+\binom23^k}{3}
−
= \sum_{i=0}^{p-1} \binom{p-1}{i}_\zeta^k
+
=\frac{1+2^k+1}{3}
−
= \sum_{i=0}^{p-1} (-1)^{ik} \,\zeta^{-k\,i(i+1)/2}
+
=\frac{2+2^k}{3}.
−
= \zeta^a \sum_{l\!\!\!\!\pmod p} \zeta^{-k\,l^2},
 
 
</cmath>
 
</cmath>
  
−
for some integer <math>a</math>.  The inner sum is a quadratic Gauss sum of magnitude <math>\sqrt p \neq 0</math>, so <math>S_k(p-1;\zeta)\neq0</math>.  Hence <math>\Phi_p(q)\nmid S_k(n;q)</math> and <math>[n+1]_q\nmid S_k(n;q)</math>.
+
If <math>k</math> is odd then <math>2^k\equiv2\pmod3</math>, so <math>2+2^k\equiv4\equiv1\pmod3</math>, whence  
−
 
 
−
Conclusion  
 
−
 
 
−
For even <math>k</math> we have <math>[n+1]_q\mid S_k(n;q)</math>, and specializing <math>q=1</math> gives
 
−
 
 
 
<cmath>
 
<cmath>
−
\frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z.
+
A_k(2)\notin\mathbb Z.
 
</cmath>
 
</cmath>
  
−
For odd <math>k</math> we exhibited a <math>p\mid(n+1)</math> with <math>S_k(n;q)\neq0</math>, so integrality fails.
+
Conclusion 
  
−
This completes the proof. ~Lopkiloinm
+
<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"