Difference between revisions of "2016 USAMO Problems/Problem 2"
m (→Solution 1) |
m (→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}</cmath> |
<cmath>N = \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>N = \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> |
Revision as of 08:30, 5 May 2016
Problem
Prove that for any positive integer is an integer.
Solution 1
Define for all rational numbers and primes , where if , then , and is the greatest power of that divides for integer . Note that the expression(that we're trying to prove is an integer) is clearly rational, call it .
, by Legendre. Clearly, , and , where is the remainder function(we take out groups of which are just permutations of numbers to until there are less than left, then we have distinct values, which the minimum sum is attained at to ). Thus, , as the term in each summand is a sum of floors also and is clearly an integer.
Solution 2 (Controversial)
Consider an grid, which is to be filled with the integers through 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 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 for convenience) is: Now, we do some simple rearrangement: This is exactly the expression given in the problem! Since the expression given in the problem equals the number of distinct standard Young tableaux, it must be an integer, so 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 |