Difference between revisions of "2016 USAMO Problems/Problem 2"

Revision as of 02:13, 28 June 2025

Problem

Prove that for any positive integer $k,$ $\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}$ is an integer.

Solution 1

Define $v_p(N)$ for all rational numbers $N$ and primes $p$ , where if $N=\frac{x}{y}$ , then $v_p(N)=v_p(x)-v_p(y)$ , and $v_p(x)$ is the greatest power of $p$ that divides $x$ for integer $x$ . Note that the expression(that we're trying to prove is an integer) is clearly rational, call it $N$ .

$v_p(N)=\sum_{i=1}^\infty \left\lfloor \frac{k^{2}}{p^{i}} \right\rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \left\lfloor \frac{j}{p^{i}}\right\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \left\lfloor \frac{j}{p^{i}} \right\rfloor$ , by Legendre. Clearly, $\left\lfloor{\frac{x}{p}}\right\rfloor={\frac{x-r(x,p)}{p}}$ , and $\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)$ , where $r(i,m)$ is the remainder function(we take out groups of $m$ which are just permutations of numbers $1$ to $m$ until there are less than $m$ left, then we have $m$ distinct values, which the minimum sum is attained at $0$ to $k-1$ ). Thus, $v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}_{+}}-\frac{k^{2}}{m}+\left\lfloor{\frac{k^{2}}{m}}\right\rfloor-\frac{\sum_{i=0}^{k-1} r(i,m)-\sum_{i=k}^{2k-1} r(i,m)}{m} \geq \sum_{m=p^{i}, i\in \mathbb{N}} \left\lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\right\rceil \geq 0$ , as the term in each summand is a sum of floors also and is clearly an integer.

Solution 2 (Controversial)

Consider an $k\times k$ grid, which is to be filled with the integers $1$ through $k^2$ such that the numbers in each row are in increasing order from left to right, and such that the numbers in each column are in increasing order from bottom to top. In other words, we are creating an $k\times k$ standard Young tableaux.

The Hook Length Formula is the source of the controversy, as it is very powerful and trivializes this problem. The Hook Length Formula states that the number of ways to create this standard Young tableaux (call this $N$ for convenience) is: $N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.$ Now, we do some simple rearrangement: $N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\prod_{i=1}^{k}\frac{1}{i+j-1} = \left(k^2\right)!\cdot\prod_{j=1}^{k}\frac{\left(j-1\right)!}{\left(j+k-1\right)!}$ $= \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.$ This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct $k\times k$ standard Young tableaux, it must be an integer, so we are done.

Solution 3 (Induction)

Define $A(k) = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.$ Clearly, $A(1) = 1$ and $A(2) = 2.$

Then $\frac{A(k+1)}{A(k)} = \frac{\left(k^2+2k+1\right)!\cdot\prod_{j=0}^{k}\frac{j!}{\left(j+k+1\right)!}}{\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}}.$ Lots of terms cancel, and we are left with $\frac{A(k+1)}{A(k)} = \frac{(k^2+1)(k^2+2)\cdots(k^2+2k+1)}{2(2k+1)}.$ The numerator has $2k+1$ consecutive positive integers, so one of them must be divisible by $(2k+1).$ Also, there are $2k$ terms left, $k$ of which are even. We can choose one of these to cancel out the $2$ in the denominator. Therefore, the ratio between $A(k+1)$ and $A(k)$ is an integer. By our inductive hypothesis, $A(k)$ is an integer. Therefore, $A(k+1)$ is as well, and we are done.

Note: This is incorrect.

Solution 4

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 expression $P_k(q) := [k^2]_q! \cdot \prod_{j = 0}^{k - 1} \frac{[j]_q!}{[j + k]_q!}.$

Let $\nu_d(F)$ denote the exponent of $(1 - q^d)$ in a polynomial $F$ . We use the identity $\nu_d([n]_q!) = \sum_{i = 1}^{n} \left\lfloor \frac{i}{d} \right\rfloor - n \cdot \delta_{d, 1},$ where $\delta_{d,1} = 1$ if $d = 1$ and $0$ otherwise.

Apply this to $P_k(q)$ : $\nu_d(P_k(q)) = \nu_d([k^2]_q!) + \sum_{j = 0}^{k - 1} \nu_d([j]_q!) - \sum_{j = 0}^{k - 1} \nu_d([j + k]_q!).$

We now expand each term using the formula:

\begin{aligned}
\nu_d(P_k(q)) &= \left( \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor - k^2 \delta_{d,1} \right) \\
&\quad + \sum_{j = 0}^{k - 1} \left( \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor - j \delta_{d,1} \right) \\
&\quad - \sum_{j = 0}^{k - 1} \left( \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor - (j + k) \delta_{d,1} \right).
\end{aligned} (Error compiling LaTeX. Unknown error_msg)

Now handle the $\delta_{d,1}$ terms separately:

\begin{aligned}
\text{Total coefficient of } \delta_{d,1} &= -k^2 - \sum_{j=0}^{k-1} j + \sum_{j=0}^{k-1}(j + k) \\
&= -k^2 - \frac{k(k-1)}{2} + \left( \frac{k(k-1)}{2} + k^2 \right) = 0.
\end{aligned} (Error compiling LaTeX. Unknown error_msg)

Therefore, we have $\nu_d(P_k(q)) = \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor + \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor - \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.$

We simplify by combining the last two double sums: $\sum_{j = 0}^{k - 1} \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor - \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor = \sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.$

Thus we obtain $\nu_d(P_k(q)) = \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor - \sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.$

We now observe that for each $j$ , the inner sum over $i$ from $j+1$ to $j+k$ covers a block of $k$ consecutive integers. As $j$ ranges from $0$ to $k-1$ , the total set of $i$ values in these blocks is contained in $(0, k^2]$ . So each $i$ appears at most once in the total sum. Hence, $\sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor \le \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor,$ which implies $\nu_d(P_k(q)) \ge 0 \quad \text{for all } d \ge 1.$

Since each exponent of $(1 - q^d)$ is non-negative, the denominator divides the numerator in $\mathbb Z[q]$ . Therefore $P_k(q) \in \mathbb Z[q]$ , and evaluating at $q = 1$ gives $P_k(1) = (k^2)! \cdot \prod_{j = 0}^{k - 1} \frac{j!}{(j + k)!} \in \mathbb Z,$ as desired. ~Lopkiloinm

Note: This solution is fundamentally different from the first, which works purely in the integers. Here, we work in the integer polynomial ring $\mathbb{Z}[q]$ —a graded algebra—which allows us to test integrality by tracking the multiplicities of reducible elements like $1 - q^d$ for all integers $1 \le d \le k^2$ . In contrast, working in $\mathbb{Z}$ —a non-graded algebra—requires using $p$ -adic valuations via Legendre’s formula, which only considers irreducibles (primes). The graded structure of $\mathbb{Z}[q]$ simplifies the analysis, making it a powerful strategy to lift problems into a graded setting whenever possible.

@@ Line 26: / Line 26: @@
 ==Solution 4==
-Throughout this proof we work in the polynomial ring <math>\mathbb{Z}[q]</math>.
+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 Gaussian factorial (also called <math>q</math>-factorial) by
+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 + \dots + q^{n-1},
+[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.
-\qquad
-[n]_q! := \prod_{i=1}^{n}[i]_q.
 </cmath>
-Each <math>[i]_q</math> is a polynomial of degree <math>i-1</math>, so <math>[n]_q! \in \mathbb{Z}[q]</math>.  Evaluating at <math>q=1</math> recovers the ordinary factorial:
+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 expression
+<cmath>
+P_k(q) := [k^2]_q! \cdot \prod_{j = 0}^{k - 1} \frac{[j]_q!}{[j + k]_q!}.
+</cmath>
+Let <math>\nu_d(F)</math> denote the exponent of <math>(1 - q^d)</math> in a polynomial <math>F</math>.
+We use the identity
+<cmath>
+\nu_d([n]_q!) = \sum_{i = 1}^{n} \left\lfloor \frac{i}{d} \right\rfloor - n \cdot \delta_{d, 1},
+</cmath>
+where <math>\delta_{d,1} = 1</math> if <math>d = 1</math> and <math>0</math> otherwise.
+Apply this to <math>P_k(q)</math>:
 <cmath>
-\lim_{q\to1}[n]_q! \;=\; n!.
+\nu_d(P_k(q)) = \nu_d([k^2]_q!)
++ \sum_{j = 0}^{k - 1} \nu_d([j]_q!)
+- \sum_{j = 0}^{k - 1} \nu_d([j + k]_q!).
 </cmath>
-Consider
+We now expand each term using the formula:
 <cmath>
-P_k(q) := [k^2]_q! \,\prod_{j=0}^{k-1}\frac{[j]_q!}{[j+k]_q!},
+\begin{aligned}
+\nu_d(P_k(q)) &= \left( \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor - k^2 \delta_{d,1} \right) \\
+&\quad + \sum_{j = 0}^{k - 1} \left( \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor - j \delta_{d,1} \right) \\
+&\quad - \sum_{j = 0}^{k - 1} \left( \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor - (j + k) \delta_{d,1} \right).
+\end{aligned}
 </cmath>
-and set <math>\nu_d(F)</math> to be the exponent of <math>(1-q^d)</math> in a polynomial <math>F</math>.
-For every <math>n\ge1</math> one has
+Now handle the <math>\delta_{d,1}</math> terms separately:
 <cmath>
-\nu_d([n]_q!) \;=\; \sum_{i=1}^{n}\Bigl\lfloor \tfrac{i}{d}\Bigr\rfloor \;-\; n\,\delta_{d=1},
+\begin{aligned}
+\text{Total coefficient of } \delta_{d,1} &= -k^2 - \sum_{j=0}^{k-1} j + \sum_{j=0}^{k-1}(j + k) \\
+&= -k^2 - \frac{k(k-1)}{2} + \left( \frac{k(k-1)}{2} + k^2 \right) = 0.
+\end{aligned}
 </cmath>
-where <math>\delta_{d=1}</math> is the Kronecker delta.  Applying this to each factorial gives
+Therefore, we have
 <cmath>
-\nu_d(P_k(q))
+\nu_d(P_k(q)) = \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor
-=\Bigl(\sum_{i=1}^{k^2}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor-k^{2}\delta_{d=1}\Bigr)
++ \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor
-\;+\;\sum_{j=0}^{k-1}\Bigl(\sum_{i=1}^{j}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor-j\delta_{d=1}\Bigr)
+- \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.
-\;-\;\sum_{j=0}^{k-1}\Bigl(\sum_{i=1}^{j+k}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor-(j+k)\delta_{d=1}\Bigr).
 </cmath>
-Because
-<math>\displaystyle \sum_{j=0}^{k-1}j=\frac{k(k-1)}{2}</math> and
+We simplify by combining the last two double sums:
-<math>\displaystyle \sum_{j=0}^{k-1}(j+k)=\frac{k(k-1)}{2}+k^{2}</math>,
-the <math>\delta_{d=1}</math> terms cancel.  Hence
 <cmath>
-\nu_d(P_k(q))
+\sum_{j = 0}^{k - 1} \sum_{i = 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor
-=\sum_{i=1}^{k^{2}}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor
+- \sum_{j = 0}^{k - 1} \sum_{i = 1}^{j} \left\lfloor \frac{i}{d} \right\rfloor
-\;+\;\sum_{j=0}^{k-1}\sum_{i=1}^{j}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor
+= \sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.
-\;-\;\sum_{j=0}^{k-1}\sum_{i=1}^{\,j+k}\Bigl\lfloor\tfrac{i}{d}\Bigr\rfloor.
 </cmath>
-\medskip
+Thus we obtain
-\textbf{Boundedness.}
-For fixed <math>d</math>, the inner difference
 <cmath>
-\Bigl\lfloor\tfrac{j+k}{d}\Bigr\rfloor-\Bigl\lfloor\tfrac{j}{d}\Bigr\rfloor
+\nu_d(P_k(q)) = \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor
+- \sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor.
 </cmath>
-counts the number of multiples of <math>d</math> lying in the half-open interval <math>(j,\,j+k]</math>.
-As <math>j</math> ranges from <math>0</math> to <math>k-1</math>, each multiple of <math>d</math> in <math>(0,\,k^{2}]</math> is counted at most once, so
+We now observe that for each <math>j</math>, the inner sum over <math>i</math> from <math>j+1</math> to <math>j+k</math> covers a block of <math>k</math> consecutive integers.
+As <math>j</math> ranges from <math>0</math> to <math>k-1</math>, the total set of <math>i</math> values in these blocks is contained in <math>(0, k^2]</math>.
+So each <math>i</math> appears at most once in the total sum. Hence,
 <cmath>
-\;\le\;
+\sum_{j = 0}^{k - 1} \sum_{i = j + 1}^{j + k} \left\lfloor \frac{i}{d} \right\rfloor \le \sum_{i = 1}^{k^2} \left\lfloor \frac{i}{d} \right\rfloor,
-\sum_{j=0}^{k-1}\!\Bigl(
-\Bigl\lfloor\tfrac{j+k}{d}\Bigr\rfloor-\Bigl\lfloor\tfrac{j}{d}\Bigr\rfloor
-\Bigr)
-\;\le\;
-\Bigl\lfloor\tfrac{k^{2}}{d}\Bigr\rfloor.
 </cmath>
-Therefore
+which implies
 <cmath>
-\nu_d(P_k(q))
+\nu_d(P_k(q)) \ge 0 \quad \text{for all } d \ge 1.
-=\Bigl\lfloor\tfrac{k^{2}}{d}\Bigr\rfloor
-- \sum_{j=0}^{k-1}\!\Bigl(
-\Bigl\lfloor\tfrac{j+k}{d}\Bigr\rfloor-\Bigl\lfloor\tfrac{j}{d}\Bigr\rfloor
-\Bigr)
-\;\ge\;0
-\qquad\text{for every }d\ge1.
 </cmath>
-Since every exponent is non-negative, <math>P_k(q)\in\mathbb{Z}[q]</math>.  Evaluating at <math>q=1</math> gives
+Since each exponent of <math>(1 - q^d)</math> is non-negative, the denominator divides the numerator in <math>\mathbb Z[q]</math>.
+Therefore <math>P_k(q) \in \mathbb Z[q]</math>, and evaluating at <math>q = 1</math> gives
 <cmath>
-P_k(1) \;=\; (k^{2})! \;\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}\in\mathbb{Z},
+P_k(1) = (k^2)! \cdot \prod_{j = 0}^{k - 1} \frac{j!}{(j + k)!} \in \mathbb Z,
 </cmath>
-completing the proof.
+as desired.
 ~Lopkiloinm

2016 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search