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 roots of unity))
Line 68: Line 68:
 
</cmath>
 
</cmath>
  
−
We now show this sum is zero. Define the map <math>f(i) = d - 1 - i</math>. Then
+
We now show this sum is zero. Define the involution <math>i \mapsto d - 1 - i</math>. Then
 
<cmath>
 
<cmath>
−
f(i)(f(i) + 1) = (d - 1 - i)(d - i) = i(i+1) \mod 2d,
+
i(i+1) + (d - 1 - i)(d - i) = d^2 - d \equiv 0 \pmod{2d}.
 
</cmath>
 
</cmath>
−
because <math>k</math> is even and <math>d</math> is odd, so <math>k i(i+1)/2 \equiv k f(i)(f(i)+1)/2 \mod d</math>.
+
So for even <math>k</math>, the exponent <math>-k i(i+1)/2</math> satisfies
−
 
+
<cmath>
−
So the terms in the sum occur in symmetric pairs <math>i</math> and <math>d - 1 - i</math> with equal exponents. The exponents match but the base <math>\zeta</math> is a nontrivial root of unity, so the sum pairs up into complex conjugate directions around the circle and sums to zero. Therefore
+
-\frac{k}{2} i(i+1) \equiv \frac{k}{2} (d - 1 - i)(d - i) \pmod{d},
 +
</cmath>
 +
which means the terms <math>i</math> and <math>d - 1 - i</math> are mapped to opposite powers of <math>\zeta</math>:
 +
<cmath>
 +
\zeta^{-k i(i+1)/2} + \zeta^{-k (d - 1 - i)(d - i)/2} = \zeta^a + \zeta^{-a}.
 +
</cmath>
 +
Each such pair adds up to <math>2 \cos(2\pi a/d)</math>, and as <math>i</math> runs from <math>0</math> to <math>d - 1</math>, the values <math>a \mod d</math> cancel in symmetric pairs. Therefore the sum vanishes:
 
<cmath>
 
<cmath>
−
T_k(d - 1; \zeta) = 0,
+
T_k(d - 1; \zeta) = \sum_{i=0}^{d - 1} \zeta^{-k i(i+1)/2} = 0.
 
</cmath>
 
</cmath>
 +
 
so <math>\Phi_d(q) \mid S_k(d - 1; q)</math>.
 
so <math>\Phi_d(q) \mid S_k(d - 1; q)</math>.
  

Revision as of 07:02, 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 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 \[\binom{n}{i}_q := \frac{[n]_q!}{[i]_q! \cdot [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 \binom{n}{i}_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 \binom{n}{i}_\zeta^k.\]

Now suppose $n = d - 1$. Then each numerator term in the $q$-binomial $\binom{n}{i}_q$ becomes $1 - q^j$ with $j \in \{1, 2, \dotsc, d - 1\}$. Because $q = \zeta$ is a primitive $d$-th root of unity, we have $1 - \zeta^j = -\zeta^j (1 - \zeta^{-j})$.

Therefore each numerator factor $1 - \zeta^{d - j} = -\zeta^{-(j)} (1 - \zeta^j)$. The denominator terms are $1 - \zeta^j$. All such terms cancel, leaving: \[\binom{d-1}{i}_\zeta = \prod_{j=1}^i (-\zeta^{-j}) = (-1)^i \zeta^{-i(i+1)/2}.\]

Hence \[T_k(d-1;\zeta) = \sum_{i=0}^{d-1} \left( (-1)^i \zeta^{-i(i+1)/2} \right)^k = \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 alternates in sign. The exponential phases $\zeta^{-k i(i+1)/2}$ do not cancel this sign pattern. Therefore the sum is nonzero, so $\Phi_d(q) \nmid S_k(d - 1; q)$, and $[d]_q \nmid S_k(d - 1; q)$. Thus $A_k(d - 1) \notin \mathbb Z$.

If $k$ is even, then $(-1)^{ik} = 1$, and \[T_k(d - 1; \zeta) = \sum_{i=0}^{d - 1} \zeta^{-k i(i+1)/2}.\]

We now show this sum is zero. Define the involution $i \mapsto d - 1 - i$. Then \[i(i+1) + (d - 1 - i)(d - i) = d^2 - d \equiv 0 \pmod{2d}.\] So for even $k$, the exponent $-k i(i+1)/2$ satisfies \[-\frac{k}{2} i(i+1) \equiv \frac{k}{2} (d - 1 - i)(d - i) \pmod{d},\] which means the terms $i$ and $d - 1 - i$ are mapped to opposite powers of $\zeta$: \[\zeta^{-k i(i+1)/2} + \zeta^{-k (d - 1 - i)(d - i)/2} = \zeta^a + \zeta^{-a}.\] Each such pair adds up to $2 \cos(2\pi a/d)$, and as $i$ runs from $0$ to $d - 1$, the values $a \mod d$ cancel in symmetric pairs. Therefore the sum vanishes: \[T_k(d - 1; \zeta) = \sum_{i=0}^{d - 1} \zeta^{-k i(i+1)/2} = 0.\]

so $\Phi_d(q) \mid S_k(d - 1; q)$.

This holds for all $d \mid n+1$, so $[n+1]_q \mid S_k(n;q)$ for all $n$ if and only if $k$ is even. Therefore \[R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q] \quad \iff \quad k \text{ 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}}.\]

~Lopkiloinm

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