Difference between revisions of "2025 USAMO Problems/Problem 5"

(Solution 2 (q-analogue via q-Chu–Vandermonde))
(Solution 2 (q-analogue via q-Chu–Vandermonde))
 
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 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>   
 
 
 
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   
 
 
 
Take <math>n=2</math>.  Then
 
  
 +
Take <math>n=2</math>.  Then 
 
<cmath>
 
<cmath>
A_k(2) = \frac{1 + 2^k + 1}{3} = \frac{2 + 2^k}{3}.
+
A_k(2)=\frac{\binom21^k+\binom22^k+\binom23^k}{3}
 +
=\frac{1+2^k+1}{3}
 +
=\frac{2+2^k}{3}.
 
</cmath>
 
</cmath>
  
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>.
+
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> the example <math>n=2</math> yields a noninteger, so integrality fails.
+
Conclusion 
  
This completes the proof.
+
<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 (ProblemsResources)
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