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 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}^{2n-1} r(i,m)</math>, where <math>r(i,m)</math> is the remainder function(we take out groups of <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 \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(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.
  
 
==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:08, 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$ 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 \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(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}+\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=78327"