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 1)
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 (q-analog roots of unity) ==
 +
 +
Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
 +
 +
For any positive integer <math>n</math>, define the <math>q</math>-integer and <math>q</math>-factorial by
 +
<cmath>
 +
[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.
 +
</cmath>
 +
Each <math>[i]_q</math> is a degree <math>i-1</math> polynomial in <math>\mathbb Z[q]</math>, so <math>[n]_q! \in \mathbb Z[q]</math>. 
 +
Evaluating at <math>q = 1</math> gives <math>\lim_{q \to 1} [n]_q! = n!</math>.
 +
 +
Define the <math>q</math>-binomial coefficient as
 +
<cmath>
 +
\left[ \begin{array}{c} n \\ i \end{array} \right]_q := \frac{[n]_q!}{[i]_q! [n-i]_q!} \in \mathbb Z[q],
 +
</cmath>
 +
which recovers the usual binomial coefficient when <math>q = 1</math>.
 +
 +
Let <math>A_k(n) = \dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k</math>. 
 +
We want to prove that <math>A_k(n) \in \mathbb Z</math> for all <math>n \ge 1</math> if and only if <math>k</math> is even.
 +
 +
Define the <math>q</math>-analogue sum
 +
<cmath>
 +
S_k(n;q) := \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_q^k \in \mathbb Z[q].
 +
</cmath>
 +
Let <math>[n+1]_q = 1 + q + \cdots + q^n = \dfrac{1 - q^{n+1}}{1 - q} = \prod_{d \mid n+1} \Phi_d(q)</math>, 
 +
where <math>\Phi_d(q)</math> is the <math>d</math>-th cyclotomic polynomial.
 +
 +
To prove <math>A_k(n) \in \mathbb Z</math>, it suffices to show
 +
<cmath>
 +
[n+1]_q \mid S_k(n;q) \quad \text{in } \mathbb Z[q],
 +
</cmath>
 +
because evaluating at <math>q = 1</math> yields <math>\dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z</math>.
 +
 +
Suppose <math>q = \zeta</math> is a primitive <math>d</math>-th root of unity with <math>d \mid n+1</math>, so <math>[n+1]_q = 0</math>. 
 +
We evaluate <math>S_k(n; q)</math> at <math>q = \zeta</math>:
 +
<cmath>
 +
T_k(n; \zeta) := S_k(n; \zeta) = \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_\zeta^k.
 +
</cmath>
 +
 +
We now determine when <math>T_k(n; \zeta) = 0</math>. Suppose <math>n = d - 1</math>, the largest index where <math>\zeta^d = 1</math>. 
 +
It is known that
 +
<cmath>
 +
\left[ \begin{array}{c} d - 1 \\ i \end{array} \right]_{\zeta} = (-1)^i \zeta^{-i(i+1)/2}.
 +
</cmath>
 +
Therefore,
 +
<cmath>
 +
T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} (-1)^{ik} \zeta^{-k i(i+1)/2}.
 +
</cmath>
 +
 +
If <math>k</math> is odd, then <math>(-1)^{ik} = (-1)^i</math>, and the sum does not cancel. So <math>T_k(d - 1; \zeta) \ne 0</math>, implying <math>\Phi_d(q) \nmid S_k(d - 1; q)</math>, so <math>[d]_q \nmid S_k(d - 1; q)</math> and <math>A_k(d - 1) \notin \mathbb Z</math>.
 +
 +
If <math>k</math> is even, then <math>(-1)^{ik} = 1</math> for all <math>i</math>, so
 +
<cmath>
 +
T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} \zeta^{-k i(i+1)/2},
 +
</cmath>
 +
which is a quadratic exponential sum over a full residue system modulo <math>d</math>. 
 +
It is known that such sums vanish when <math>k</math> is even and <math>d</math> is odd. 
 +
Hence <math>T_k(d - 1; \zeta) = 0</math>, so <math>\Phi_d(q) \mid S_k(n; q)</math>.
 +
 +
Since this holds for all <math>d \mid n+1</math>, the full factor <math>[n+1]_q = \prod_{d \mid n+1} \Phi_d(q)</math> divides <math>S_k(n; q)</math> for all <math>n</math> if and only if <math>k</math> is even.
 +
 +
Therefore, <math>R_k(q) = \dfrac{S_k(n; q)}{[n+1]_q} \in \mathbb Z[q]</math> if and only if <math>k</math> is even. 
 +
Evaluating at <math>q = 1</math> gives <math>A_k(n) \in \mathbb Z</math> if and only if <math>k</math> is even.
 +
 +
Thus,
 +
<cmath>
 +
\boxed{\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z \quad \text{for all } n \ge 1 \iff k \text{ is even}}.
 +
</cmath>
  
 
==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 06:12, 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-analog roots of unity)

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

For any positive integer $n$, define the $q$-integer and $q$-factorial by \[[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.\] Each $[i]_q$ is a degree $i-1$ polynomial in $\mathbb Z[q]$, so $[n]_q! \in \mathbb Z[q]$. Evaluating at $q = 1$ gives $\lim_{q \to 1} [n]_q! = n!$.

Define the $q$-binomial coefficient as \[\left[ \begin{array}{c} n \\ i \end{array} \right]_q := \frac{[n]_q!}{[i]_q! [n-i]_q!} \in \mathbb Z[q],\] which recovers the usual binomial coefficient when $q = 1$.

Let $A_k(n) = \dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k$. We want to prove that $A_k(n) \in \mathbb Z$ for all $n \ge 1$ if and only if $k$ is even.

Define the $q$-analogue sum \[S_k(n;q) := \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_q^k \in \mathbb Z[q].\] Let $[n+1]_q = 1 + q + \cdots + q^n = \dfrac{1 - q^{n+1}}{1 - q} = \prod_{d \mid n+1} \Phi_d(q)$, where $\Phi_d(q)$ is the $d$-th cyclotomic polynomial.

To prove $A_k(n) \in \mathbb Z$, it suffices to show \[[n+1]_q \mid S_k(n;q) \quad \text{in } \mathbb Z[q],\] because evaluating at $q = 1$ yields $\dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z$.

Suppose $q = \zeta$ is a primitive $d$-th root of unity with $d \mid n+1$, so $[n+1]_q = 0$. We evaluate $S_k(n; q)$ at $q = \zeta$: \[T_k(n; \zeta) := S_k(n; \zeta) = \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_\zeta^k.\]

We now determine when $T_k(n; \zeta) = 0$. Suppose $n = d - 1$, the largest index where $\zeta^d = 1$. It is known that \[\left[ \begin{array}{c} d - 1 \\ i \end{array} \right]_{\zeta} = (-1)^i \zeta^{-i(i+1)/2}.\] Therefore, \[T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} (-1)^{ik} \zeta^{-k i(i+1)/2}.\]

If $k$ is odd, then $(-1)^{ik} = (-1)^i$, and the sum does not cancel. So $T_k(d - 1; \zeta) \ne 0$, implying $\Phi_d(q) \nmid S_k(d - 1; q)$, so $[d]_q \nmid S_k(d - 1; q)$ and $A_k(d - 1) \notin \mathbb Z$.

If $k$ is even, then $(-1)^{ik} = 1$ for all $i$, so \[T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} \zeta^{-k i(i+1)/2},\] which is a quadratic exponential sum over a full residue system modulo $d$. It is known that such sums vanish when $k$ is even and $d$ is odd. Hence $T_k(d - 1; \zeta) = 0$, so $\Phi_d(q) \mid S_k(n; q)$.

Since this holds for all $d \mid n+1$, the full factor $[n+1]_q = \prod_{d \mid n+1} \Phi_d(q)$ divides $S_k(n; q)$ for all $n$ if and only if $k$ is even.

Therefore, $R_k(q) = \dfrac{S_k(n; q)}{[n+1]_q} \in \mathbb Z[q]$ if and only if $k$ is even. Evaluating at $q = 1$ gives $A_k(n) \in \mathbb Z$ if and only if $k$ is even.

Thus, \[\boxed{\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z \quad \text{for all } n \ge 1 \iff k \text{ is 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=252586"