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))
 
(4 intermediate revisions 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 roots of unity) ==
+
== Solution 2 (combinatorial via Burnside’s lemma) ==
  
−
Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
+
Let 
−
 
 
−
For any positive integer <math>n</math>, define the <math>q</math>-integer and <math>q</math>-factorial by
 
 
<cmath>
 
<cmath>
−
[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.
+
X=\{(A_1,\dots,A_k):A_j\subseteq\{1,\dots,n\},\;|A_1|=\cdots=|A_k|\}.
 
</cmath>
 
</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
+
Then 
 
<cmath>
 
<cmath>
−
\binom{n}{i}_q := \frac{[n]_q!}{[i]_q! \cdot [n-i]_q!} \in \mathbb Z[q],
+
|X|=\sum_{i=0}^n\binom{n}{i}^k.
 
</cmath>
 
</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>. 
+
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>.
−
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
+
By Burnside’s lemma, 
 
<cmath>
 
<cmath>
−
S_k(n;q) := \sum_{i=0}^n \binom{n}{i}_q^k \in \mathbb Z[q].
+
|X/C_{n+1}|=\frac1{n+1}\sum_{g\in C_{n+1}}|\mathrm{Fix}(g)|.
 
</cmath>
 
</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
+
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>
−
[n+1]_q \mid S_k(n;q) \quad \text{in } \mathbb Z[q],
+
|\mathrm{Fix}(g)|=\sum_{i=0}^n\binom{d}{i}^k.
 
</cmath>
 
</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>.  
+
Thus  
−
We evaluate <math>S_k(n; q)</math> at <math>q = \zeta</math>:
 
 
<cmath>
 
<cmath>
−
T_k(n; \zeta) := S_k(n; \zeta) = \sum_{i=0}^n \binom{n}{i}_\zeta^k.
+
(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>
 
</cmath>
  
−
Now suppose <math>n = d - 1</math>. Then each numerator term in the <math>q</math>-binomial <math>\binom{n}{i}_q</math> becomes <math>1 - q^j</math> with <math>j \in \{1, 2, \dotsc, d - 1\}</math>. Because <math>q = \zeta</math> is a primitive <math>d</math>-th root of unity, we have <math>1 - \zeta^j = -\zeta^j (1 - \zeta^{-j})</math>.
+
Case 1: <math>k=2m</math> even 
  
−
Therefore each numerator factor <math>1 - \zeta^{d - j} = -\zeta^{-(j)} (1 - \zeta^j)</math>. The denominator terms are <math>1 - \zeta^j</math>. All such terms cancel, leaving:
+
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>
−
\binom{d-1}{i}_\zeta = \prod_{j=1}^i (-\zeta^{-j}) = (-1)^i \zeta^{-i(i+1)/2}.
+
d\mid\sum_{i=0}^n\binom{d}{i}^{2m}.
 
</cmath>
 
</cmath>
  
−
Hence
+
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>
−
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}.
+
\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>
 
</cmath>
−
 
+
the entire sum on the right is congruent modulo <math>n+1</math> to 
−
If <math>k</math> is odd, then <math>(-1)^{ik} = (-1)^i</math> and the sum alternates in sign. The exponential phases <math>\zeta^{-k i(i+1)/2}</math> do not cancel this sign pattern. Therefore the sum is nonzero, so <math>\Phi_d(q) \nmid S_k(d - 1; q)</math>, and <math>[d]_q \nmid S_k(d - 1; q)</math>. Thus <math>A_k(d - 1) \notin \mathbb Z</math>.
 
−
 
 
−
If <math>k</math> is even, then <math>(-1)^{ik} = 1</math>, and
 
 
<cmath>
 
<cmath>
−
T_k(d - 1; \zeta) = \sum_{i=0}^{d - 1} \zeta^{-k i(i+1)/2}.
+
\varphi(1)\sum_{i=0}^n\binom{n+1}{i}^{2m}
 +
=1\cdot\sum_{i=0}^n\binom{n+1}{i}^{2m}.
 
</cmath>
 
</cmath>
  
−
We now show this sum is zero. Define the involution <math>i \mapsto d - 1 - i</math>. Then
+
But the left side <math>(n+1)\,|X/C_{n+1}|\equiv0\pmod{n+1}</math>, so 
 
<cmath>
 
<cmath>
−
i(i+1) + (d - 1 - i)(d - i) = d^2 - d \equiv 0 \pmod{2d}.
+
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n+1}{i}^{2m}.
 
</cmath>
 
</cmath>
−
So for even <math>k</math>, the exponent <math>-k i(i+1)/2</math> satisfies
+
 
 +
A re‐index <math>n+1\mapsto n</math> yields 
 
<cmath>
 
<cmath>
−
-\frac{k}{2} i(i+1) \equiv \frac{k}{2} (d - 1 - i)(d - i) \pmod{d},
+
n+1\;\bigm\vert\;\sum_{i=0}^n\binom{n}{i}^{2m},
 
</cmath>
 
</cmath>
−
which means the terms <math>i</math> and <math>d - 1 - i</math> are mapped to opposite powers of <math>\zeta</math>:
+
hence 
 
<cmath>
 
<cmath>
−
\zeta^{-k i(i+1)/2} + \zeta^{-k (d - 1 - i)(d - i)/2} = \zeta^a + \zeta^{-a}.
+
A_{2m}(n)=\frac1{n+1}\sum_{i=0}^n\binom{n}{i}^{2m}\in\mathbb Z.
−
</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>
 
−
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>.
+
Case 2: <math>k</math> odd 
  
−
This holds for all <math>d \mid n+1</math>, so <math>[n+1]_q \mid S_k(n;q)</math> for all <math>n</math> if and only if <math>k</math> is even. Therefore
+
Take <math>n=2</math>. Then 
 
<cmath>
 
<cmath>
−
R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q]
+
A_k(2)=\frac{\binom21^k+\binom22^k+\binom23^k}{3}
−
\quad \iff \quad k \text{ even}.
+
=\frac{1+2^k+1}{3}
 +
=\frac{2+2^k}{3}.
 
</cmath>
 
</cmath>
−
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,
+
If <math>k</math> is odd then <math>2^k\equiv2\pmod3</math>, so <math>2+2^k\equiv4\equiv1\pmod3</math>, whence 
 
<cmath>
 
<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}}.
+
A_k(2)\notin\mathbb Z.
 
</cmath>
 
</cmath>
  
−
~Lopkiloinm
+
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"