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"

(→‎Solution)
(→‎Solution)
Line 7: Line 7:
  
 
<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.
 
<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}}
 
−
 
−
{{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:04, 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.

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