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))
Line 33: Line 33:
 
[n+1]_q = 1 + q + \cdots + q^n
 
[n+1]_q = 1 + q + \cdots + q^n
 
= \frac{1 - q^{n+1}}{1 - q}
 
= \frac{1 - q^{n+1}}{1 - q}
−
= \prod_{d \mid (n+1)} \Phi_d(q).
+
= \prod_{d\mid(n+1)} \Phi_d(q).
 
</cmath>
 
</cmath>
  
Line 50: Line 50:
 
</cmath>
 
</cmath>
  
−
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>.
+
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 exists some <math>n</math> for which <math>\tfrac1{n+1}\sum_i\binom ni^k\notin\mathbb Z</math>.
  
 
Case <math>m=1</math>   
 
Case <math>m=1</math>   
Line 97: Line 97:
 
Case <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{1 + 2^k + 1}{3} = \frac{2 + 2^k}{3}.
−
= \sum_{i=0}^{p-1} \binom{p-1}{i}_\zeta^k
 
−
= \sum_{i=0}^{p-1} (-1)^{ik} \,\zeta^{-k\,i(i+1)/2}
 
−
= \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 \equiv 2 \pmod 3</math>, so <math>2+2^k \equiv 4 \equiv 1\pmod3</math> and hence <math>3\nmid(2+2^k)</math>.  Thus <math>A_k(2)\notin\mathbb Z</math>.
  
 
Conclusion   
 
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
+
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.
+
\frac1{n+1}\sum_{i=0}^n \binom ni^k \in \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.
+
For odd <math>k</math> the example <math>n=2</math> yields a noninteger, so integrality fails.
  
−
This completes the proof. ~Lopkiloinm
+
This completes the proof.
  
 
==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}}

Revision as of 08:39, 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 (q-analogue via q-Chu–Vandermonde)

Throughout this proof we work in the polynomial ring $\mathbb Z[q]$.

For any $n\ge1$ set

\[[n]_q = 1 + q + \cdots + q^{n-1},\]

\[[n]_q! = \prod_{i=1}^n [i]_q,\]

\[\binom ni_q = \frac{[n]_q!}{[i]_q!\,[n-i]_q!}.\]

Then

\[[n+1]_q = 1 + q + \cdots + q^n = \frac{1 - q^{n+1}}{1 - q} = \prod_{d\mid(n+1)} \Phi_d(q).\]

Define

\[S_k(n;q) = \sum_{i=0}^n \binom ni_q^k.\]

We must show

\[A_k(n) = \frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z \quad\Longleftrightarrow\quad k \text{ even}.\]

It suffices to prove that for even $k=2m$, one has $[n+1]_q \mid S_{2m}(n;q)$ in $\mathbb Z[q]$, and that for odd $k$ there exists some $n$ for which $\tfrac1{n+1}\sum_i\binom ni^k\notin\mathbb Z$.

Case $m=1$

By the $q$-Chu–Vandermonde identity,

\[\sum_{i=0}^n \binom ni_q^2 = \binom{2n}{n}_q = \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),\]

with $Q_{n,1}(q)\in\mathbb Z[q]$.

Inductive step

Assume for some $m\ge1$,

\[S_{2m}(n;q) = [n+1]_q \, Q_{n,m}(q), \quad Q_{n,m}(q)\in\mathbb Z[q].\]

Then

\[S_{2(m+1)}(n;q) = \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).\]

Another application of $q$-Chu–Vandermonde yields

\[\sum_{i=0}^n \binom ni_q^2 \, Q_{n,m}(q) = [n+1]_q \, Q_{n,m+1}(q), \quad Q_{n,m+1}(q)\in\mathbb Z[q],\]

so $[n+1]_q\mid S_{2(m+1)}(n;q)$.

Case $k$ odd

Take $n=2$. Then

\[A_k(2) = \frac{1 + 2^k + 1}{3} = \frac{2 + 2^k}{3}.\]

If $k$ is odd then $2^k \equiv 2 \pmod 3$, so $2+2^k \equiv 4 \equiv 1\pmod3$ and hence $3\nmid(2+2^k)$. Thus $A_k(2)\notin\mathbb Z$.

Conclusion

For even $k$ we have $[n+1]_q\mid S_k(n;q)$ and specializing $q=1$ gives

\[\frac1{n+1}\sum_{i=0}^n \binom ni^k \in \mathbb Z.\]

For odd $k$ the example $n=2$ yields a noninteger, so integrality fails.

This completes the proof.

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=252596"