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 "2016 USAMO Problems/Problem 2"

m (→‎Solution 1)
 
(9 intermediate revisions by 7 users not shown)
Line 6: Line 6:
 
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.
 
Define <math>v_p(N)</math> for all rational numbers <math>N</math> and primes <math>p</math>, where if <math>N=\frac{x}{y}</math>, then <math>v_p(N)=v_p(x)-v_p(y)</math>, and <math>v_p(x)</math> is the greatest power of <math>p</math> that divides <math>x</math> for integer <math>x</math>. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it <math>N</math>.
  
−
<math>v_p(N)=\sum_{i=1}^\infty \lfloor \frac{k^{2}}{p^{i}} \rfloor+\sum_{j=0}^{k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}}\rfloor-\sum_{j=k}^{2k-1} \sum_{i=1}^\infty \lfloor \frac{j}{p^{i}} \rfloor</math>, by Legendre. Clearly, <math>\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <math>m</math> which are just permutations of numbers <math>1</math> to <math>m</math> until there are less than <math>m</math> left, then we have <math>m</math> distinct values, which the minimum sum is attained at <math>0</math> to <math>k-1</math>). Thus, <math>v_p(N)=\sum_{m=p^{i}, i\in \mathbb{N}_{+}}-\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\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}} \lceil -\frac{k^{2}}{m}+\lfloor{\frac{k^{2}}{m}}\rfloor\rceil \geq 0</math>, as the term in each summand is a sum of floors also and is clearly an integer.
+
<math>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</math>, by Legendre. Clearly, <math>\left\lfloor{\frac{x}{p}}\right\rfloor={\frac{x-r(x,p)}{p}}</math>, and <math>\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2k-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <math>m</math> which are just permutations of numbers <math>1</math> to <math>m</math> until there are less than <math>m</math> left, then we have <math>m</math> distinct values, which the minimum sum is attained at <math>0</math> to <math>k-1</math>). Thus, <math>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</math>, as the term in each summand is a sum of floors also and is clearly an integer.
  
 
==Solution 2 (Controversial)==
 
==Solution 2 (Controversial)==
Line 14: Line 14:
 
<cmath>N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.</cmath>
 
<cmath>N = \frac{\left(k^2\right)!}{\prod_{1\le i, j\le k}(i+j-1)}.</cmath>
 
Now, we do some simple rearrangement:
 
Now, we do some simple rearrangement:
−
<cmath>N = \left(k^2\right)\cdot\prod_{j=1}^{k}\prod_{i=1}^{k}\frac{1}{i+j-1}</cmath>
+
<cmath>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)!}</cmath>  
−
<cmath>N = \left(k^2\right)!\cdot\prod_{j=1}^{k}\frac{\left(j-1\right)!}{\left(j+k-1\right)!}.</cmath>
+
<cmath>= \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.</cmath>
−
<cmath>N = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.</cmath>
 
 
This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct <math>k\times k</math> standard Young tableaux, it must be an integer, so we are done.
 
This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct <math>k\times k</math> standard Young tableaux, it must be an integer, so we are done.
 +
 +
==Solution 3 (Induction)==
 +
Define <cmath>A(k) = \left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}.</cmath> Clearly, <math>A(1) = 1</math> and <math>A(2) = 2.</math>
 +
 +
Then <cmath>\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)!}}.</cmath> Lots of terms cancel, and we are left with <cmath>\frac{A(k+1)}{A(k)} = \frac{(k^2+1)(k^2+2)\cdots(k^2+2k+1)}{2(2k+1)}.</cmath> The numerator has <math>2k+1</math> consecutive positive integers, so one of them must be divisible by <math>(2k+1).</math> Also, there are <math>2k</math> terms left, <math>k</math> of which are even. We can choose one of these to cancel out the <math>2</math> in the denominator. Therefore, the ratio between <math>A(k+1)</math> and <math>A(k)</math> is an integer. By our inductive hypothesis, <math>A(k)</math> is an integer. Therefore, <math>A(k+1)</math> is as well, and we are done.
  
 
==See also==
 
==See also==
 
{{USAMO newbox|year=2016|num-b=1|num-a=3}}
 
{{USAMO newbox|year=2016|num-b=1|num-a=3}}

Latest revision as of 19:59, 8 April 2021

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.

See also

2016 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_2&oldid=151259"