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"

(Created page with "==Problem== Prove that for any positive integer <math>k,</math> <cmath>\left(k^2\right)!\cdot\prod_{j=0}^{k-1}\frac{j!}{\left(j+k\right)!}</cmath> is an integer. ==Solution== ...")
 
(→‎Solution)
Line 4: Line 4:
 
is an integer.
 
is an integer.
 
==Solution==
 
==Solution==
 +
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>. Note that the expression 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}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function. 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.
 
{{solution}}
 
{{solution}}
  
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 
==See also==
 
==See also==
 
{{USAMO newbox|year=2016|num-b=1|num-a=3}}
 
{{USAMO newbox|year=2016|num-b=1|num-a=3}}

Revision as of 18:03, 28 April 2016

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

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$. Note that the expression is clearly rational, call it $N$.

$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$, by Legendre. Clearly, $\lfloor{\frac{x}{p}}\rfloor={\frac{x-r(x,p)}{p}}$, and $\sum_{i=0}^{k-1} r(i,m)\leq \sum_{i=k}^{2n-1} r(i,m)$, where $r(i,m)$ is the remainder function. Thus, $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$, as the term in each summand is a sum of floors also and is clearly an integer. This problem needs a solution. If you have a solution for it, please help us out by adding it.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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=78322"