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

Latest revision as of 04:19, 29 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

Let us work in the ring of polynomials $\mathbb{Z}[q]$ . Define $[n]_q = 1 + q + \cdots + q^{n-1}, \qquad [n]_q! = \prod_{i=1}^n [i]_q.$ Since $[n]_q! = \prod_{i=1}^n\frac{1 - q^i}{1 - q} = \prod_{d=1}^n \frac{\Phi_d(q)^{\lfloor n/d\rfloor}}{1 - q},$ we have $\nu_d\bigl([n]_q!\bigr) = \lfloor n/d\rfloor.$

Set $P_k(q) = [k^2]_q!\,\prod_{j=0}^{k-1}\frac{[j]_q!}{[j+k]_q!}.$ Then $\nu_1\bigl(P_k(q)\bigr) = 0$ $\nu_d\bigl(P_k(q)\bigr) = \lfloor k^2/d\rfloor + \sum_{j=0}^{k-1}\lfloor j/d\rfloor - \sum_{j=0}^{k-1}\lfloor (j+k)/d\rfloor.$ Combine the last two sums: $\sum_{j=0}^{k-1}\lfloor j/d\rfloor - \sum_{j=0}^{k-1}\lfloor (j+k)/d\rfloor = -\sum_{j=0}^{k-1}\Bigl(\lfloor (j+k)/d\rfloor - \lfloor j/d\rfloor\Bigr).$ Hence $\nu_d\bigl(P_k(q)\bigr) = \Big\lfloor\frac{k^2}{d}\Big\rfloor - \sum_{j=0}^{k-1}\Bigl(\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor\Bigr).$ But for each $0\le j<k$ , the difference $\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor$ counts the multiples of $d$ in the interval $(j,j+k]$ . As $j$ runs from $0$ to $k-1$ , these $k$ intervals lie inside $\{1,2,\dots,k^2\}$ , so $\sum_{j=0}^{k-1}\Bigl(\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor\Bigr) \;\le\; \Big\lfloor\frac{k^2}{d}\Big\rfloor.$ It follows that $\nu_d(P_k(q))\ge0$ , hence $P_k(q)\in\mathbb{Z}[q]$ . Evaluating at $q=1$ completes the proof.

~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 better organized elements like $\Phi_d(q)$ 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 primes which are less organized. The graded structure of $\mathbb{Z}[q]$ simplifies the analysis, making it a powerful strategy to lift problems into a graded algebra whenever possible.

@@ Line 26: / Line 26: @@
 ==Solution 4==
-Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
+Let us work in the ring of polynomials <math>\mathbb{Z}[q]</math>.  Define
-For any positive integer <math>n</math> define the
-<math>q</math>-integer and the Gaussian factorial (also called <math>q</math>-factorial) by
 <cmath>
-[n]_q := 1 + q + q^{2} + \dots + q^{\,n-1}
+[n]_q = 1 + q + \cdots + q^{n-1},
-\quad\Longrightarrow\quad
+\qquad
-[n]_q! := \prod_{i=1}^{n}[i]_q.
+[n]_q! = \prod_{i=1}^n [i]_q.
 </cmath>
-Because each <math>[i]_q</math> is a polynomial of degree <math>i-1</math> with integer coefficients, <math>[n]_q!</math> is a finite polynomial in <math>q</math>, and evaluating at <math>q=1</math> recovers the ordinary factorial:
+Since
 <cmath>
-\lim_{q\to1}[n]_q! \;=\; n!.
+[n]_q! = \prod_{i=1}^n\frac{1 - q^i}{1 - q}
+      = \prod_{d=1}^n \frac{\Phi_d(q)^{\lfloor n/d\rfloor}}{1 - q},
 </cmath>
-We will form a product/quotient of such Gaussian factorials, show that the resulting expression lies in <math>\mathbb Z[q]</math>, and finally plug in <math>q=1</math> to obtain the desired integer.
+we have
-We want to prove that every factor <math>(1-q^{d})</math> appears with non–negative exponent in
 <cmath>
-P_k(q)= [k^{2}]_q!\,\prod_{j=0}^{k-1}\frac{[j]_q!}{[j+k]_q!},
+\nu_d\bigl([n]_q!\bigr) = \lfloor n/d\rfloor.
 </cmath>
-so that <math>P_k(q)\in\mathbb Z[q]</math>.
-For any <math>n\ge1</math> the Gaussian factorial factors as
+Set
 <cmath>
-[n]_q! \;=\; (1-q)^{-n}\prod_{d\ge1}(1-q^{d})^{\lfloor n/d\rfloor}.
+P_k(q) = [k^2]_q!\,\prod_{j=0}^{k-1}\frac{[j]_q!}{[j+k]_q!}.
 </cmath>
-Let <math>\nu_d(F)</math> be the exponent of <math>(1-q^{d})</math> in a polynomial <math>F</math>; then
+Then
 <cmath>
-\nu_d([n]_q!) = \left\lfloor \frac{n}{d} \right\rfloor .
+\nu_1\bigl(P_k(q)\bigr) = 0
 </cmath>
-Apply this to <math>P_k(q)</math>:
 <cmath>
-\nu_d(P_k(q))
+\nu_d\bigl(P_k(q)\bigr)
-  = \left\lfloor \frac{k^{2}}{d} \right\rfloor
+= \lfloor k^2/d\rfloor
-    + \sum_{j=0}^{k-1}\left\lfloor \frac{j}{d}\right\rfloor
++ \sum_{j=0}^{k-1}\lfloor j/d\rfloor
-    - \sum_{j=0}^{k-1}\left\lfloor \frac{j+k}{d}\right\rfloor .
+- \sum_{j=0}^{k-1}\lfloor (j+k)/d\rfloor.
 </cmath>
+Combine the last two sums:
-Rewrite the last two sums together:
 <cmath>
-\nu_d(P_k(q))
+\sum_{j=0}^{k-1}\lfloor j/d\rfloor
-  = \left\lfloor \frac{k^{2}}{d} \right\rfloor
+- \sum_{j=0}^{k-1}\lfloor (j+k)/d\rfloor
-    - \sum_{j=0}^{k-1}\left(
+= -\sum_{j=0}^{k-1}\Bigl(\lfloor (j+k)/d\rfloor - \lfloor j/d\rfloor\Bigr).
-        \left\lfloor \frac{j+k}{d}\right\rfloor
-        - \left\lfloor \frac{j}{d}\right\rfloor
-      \right).
 </cmath>
+Hence
-We observe that for each <math>j</math>, the difference
-<math>\left\lfloor \frac{j+k}{d}\right\rfloor - \left\lfloor \frac{j}{d}\right\rfloor</math>
-counts the number of multiples of <math>d</math> in the 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 the interval <math>(0,\, k^2]</math> is counted at most once across the sum. Hence the total sum is bounded above by <math>\left\lfloor \frac{k^2}{d} \right\rfloor</math>, and so
 <cmath>
-\nu_d(P_k(q)) \ge 0 \quad \text{for all } d \ge 1.
+\nu_d\bigl(P_k(q)\bigr)
+= \Big\lfloor\frac{k^2}{d}\Big\rfloor
+- \sum_{j=0}^{k-1}\Bigl(\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor\Bigr).
 </cmath>
+But for each <math>0\le j<k</math>, the difference <math>\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor</math> counts the multiples of <math>d</math> in the interval <math>(j,j+k]</math>.  As <math>j</math> runs from <math>0</math> to <math>k-1</math>, these <math>k</math> intervals lie inside <math>\{1,2,\dots,k^2\}</math>, so
-Because every exponent is non–negative, the denominator in the earlier factorial ratio divides the numerator inside <math>\mathbb Z[q]</math>.  Therefore <math>P_k(q)</math> itself lies in <math>\mathbb Z[q]</math>, and evaluating at <math>q=1</math> shows the original product
 <cmath>
-(k^{2})!\,\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}
+\sum_{j=0}^{k-1}\Bigl(\lfloor\tfrac{j+k}{d}\rfloor - \lfloor\tfrac{j}{d}\rfloor\Bigr)
+\;\le\;
+\Big\lfloor\frac{k^2}{d}\Big\rfloor.
 </cmath>
-is an integer. ~Lopkiloinm
+It follows that <math>\nu_d(P_k(q))\ge0</math>
+, hence <math>P_k(q)\in\mathbb{Z}[q]</math>.  Evaluating at <math>q=1</math> completes the proof.
+~Lopkiloinm
-Note: This solution is not the same as the first solution that is only in the integers and not in an integer polynomial field—a distinction which allows us to use <math>d</math> as all integers between 1 and <math>k^2</math>—not forcing us to use the Legendre <math>p</math>-adic valuation (irreducibles only) instead simply the multiplicity of <math>1-q^d</math> (reducibles allowed). This is because <math>\mathbb{Z}[q]</math> is considered a graded algebra whereas <math>\mathbb{Z}</math> is a non-graded algebra. It is a good strategy is to convert all numbers into a graded algebra and perform integrality test there than just staying in the non-graded integers.
+Note: This solution is fundamentally different from the first, which works purely in the integers. Here, we work in the integer polynomial ring <math>\mathbb{Z}[q]</math>—a graded algebra—which allows us to test integrality by tracking the multiplicities of better organized elements like <math>\Phi_d(q)</math> for all integers <math>1 \le d \le k^2</math>. In contrast, working in <math>\mathbb{Z}</math>—a non-graded algebra—requires using <math>p</math>-adic valuations via Legendre’s formula, which only considers primes which are less organized. The graded structure of <math>\mathbb{Z}[q]</math> simplifies the analysis, making it a powerful strategy to lift problems into a graded algebra whenever possible.
 ==See also==
 {{USAMO newbox|year=2016|num-b=1|num-a=3}}

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