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 "1972 IMO Problems/Problem 3"

(→‎Solution)
(→‎Solution)
Line 28: Line 28:
  
 
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html
 
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html
 +
 +
 +
== Solution 2  ==
 +
An alternative solution is nested induction in n and m.
 +
As induction start we have the case <math>n = 0</math>. In that case <math>m!n!(m+n)! = (m!)^2</math> and <math>(2m)!(2n)! = (2m)!</math>.
 +
 +
With induction in <math>m</math> we prove the induction start for <math>n = 0</math> which states that
 +
 +
<math>(2m)!</math> is a multiple of <math>(m!)^2</math> for all natural numbers <math>m</math> (including 0) (Assertion 1):
 +
 +
For <math>m = 0</math> (induction start) we have <math>(2m)! = 1 = (m!)^2</math>. Hence, we can assume that Assertion 1 holds for <math>m - 1</math> and <math>m > 0</math>: That means that <math>(2m-2)!</math> is a multiple of <math>((m-1)!)^2</math>. Division by <math>(m-1)!</math> leads to the result that <math>X:= (m-1)! = 1 \cdot 2 \cdot \ldots (m-1)</math>
 +
is a divisor of <math>M := m \cdot \ldots \cdot (2m-2)</math> and thus <math>X' := mX = 1 \cdot 2 \cdot \ldots m</math>
 +
is a divisor of <math>M' := 2m(2m-1)M = m \cdot \ldots \cdot 2m</math>. And so <math>(m!)^2 = m!X'</math> is a divisor of
 +
<math>m!M' = (2m)!</math>, which is Assertion 1.
 +
 +
Hence, for <math>n = 0</math> as induction start in <math>n</math> the statement holds for all <math>m</math>.
 +
So we assume that the statement also holds for all natural numbers <math>n - 1</math>, where <math>n > 0</math>, and all natural numbers <math>m</math> (including 0), which means that
 +
we assume that <math>m!(n-1)!(m+n-1)!</math> divides <math>(2m)!(2n-2)!</math> for all <math>m</math>. Division by <math>m!(n-1)!</math> leads to the result that <math>X:= (m+n-1)! = 1 \cdot 2 \cdot \ldots (m + n - 1)</math>
 +
is a divisor of <math>M := [(m + 1) \cdot \ldots \cdot 2m] \cdot [n \cdot \ldots \cdot (2n-2)]</math> and thus <math>X' := m!nX = m!(m + n)!</math>
 +
is a divisor of <math>M' := m!2n(2n-1)M</math>. And so <math>n!m!(n+m)! = n!X'</math> is a divisor of <math>n!M' = (2m)!(2n)!</math>, which was to prove.
 +
 +
[[User:Agentmmk|Agentmmk]] ([[User talk:Agentmmk|talk]]) 16:43, 27 October 2015 (EDT)

Revision as of 16:43, 27 October 2015

Let $m$ and $n$ be arbitrary non-negative integers. Prove that \[\frac{(2m)!(2n)!}{m!n!(m+n)!}\] is an integer. ($0! = 1$.)

Solution

Let $f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}$. We intend to show that $f(m,n)$ is integral for all $m,n \geq 0$. To start, we would like to find a recurrence relation for $f(m,n)$.

First, let's look at $f(m,n-1)$:

$f(m,n-1)=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!}=\frac{(2m)!(2n)!(n-1)(m+n-1)}{m!n!(m+n)!(2n-1)(2n-2)}=f(m,n) \frac{(n-1)(m+n-1)}{(2n-1)(2n-2)}=f(m,n) \frac{m+n-1}{2(2n-1)}$

Second, let's look at $f(m+1,n-1)$:

$f(m+1,n-1)=\frac{(2m+2)!(2n-2)!}{(m+1)!(n-1)!(m+n)!}=\frac{(2m)!(2n)!(2m+1)(2m+2)(n-1)}{m!n!(m+n)!(m+1)(2n-1)(2n-2)}=f(m,n) \frac{(2m+1)(2m+2)(n-1)}{(m+1)(2n-1)(2n-2)}=f(m,n) \frac{(2m+1)}{2n-1}$

Combining,

$4f(m,n-1)-f(m+1,n-1)=f(m,n) (\frac{4(m+n-1)}{2(2n-1)}-\frac{2m+1}{2n-1})=f(m,n) \frac{2m+2n-2-2m+1}{2n-1}=f(m,n)$.

Therefore, we have found the recurrence relation $f(m,n)=4f(m,n-1)-f(m+1,n-1)$.

We can see that $f(m,0)=\frac{(2m)!}{m!m!}$ is integral because the RHS is just $_{2m} C _m$, which we know to be integral for all $m \geq 0$.

So, $f(m,1)=4f(m,0)-f(m+1,0)$ must be integral, and then $f(m,2)=4f(m,1)-f(m+1,1)$ must be integral, etc.

By induction, $f(m,n)$ is integral for all $m,n \geq 0$.

Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html


Solution 2

An alternative solution is nested induction in n and m. As induction start we have the case $n = 0$. In that case $m!n!(m+n)! = (m!)^2$ and $(2m)!(2n)! = (2m)!$.

With induction in $m$ we prove the induction start for $n = 0$ which states that

$(2m)!$ is a multiple of $(m!)^2$ for all natural numbers $m$ (including 0) (Assertion 1):

For $m = 0$ (induction start) we have $(2m)! = 1 = (m!)^2$. Hence, we can assume that Assertion 1 holds for $m - 1$ and $m > 0$: That means that $(2m-2)!$ is a multiple of $((m-1)!)^2$. Division by $(m-1)!$ leads to the result that $X:= (m-1)! = 1 \cdot 2 \cdot \ldots (m-1)$ is a divisor of $M := m \cdot \ldots \cdot (2m-2)$ and thus $X' := mX = 1 \cdot 2 \cdot \ldots m$ is a divisor of $M' := 2m(2m-1)M = m \cdot \ldots \cdot 2m$. And so $(m!)^2 = m!X'$ is a divisor of $m!M' = (2m)!$, which is Assertion 1.

Hence, for $n = 0$ as induction start in $n$ the statement holds for all $m$. So we assume that the statement also holds for all natural numbers $n - 1$, where $n > 0$, and all natural numbers $m$ (including 0), which means that we assume that $m!(n-1)!(m+n-1)!$ divides $(2m)!(2n-2)!$ for all $m$. Division by $m!(n-1)!$ leads to the result that $X:= (m+n-1)! = 1 \cdot 2 \cdot \ldots (m + n - 1)$ is a divisor of $M := [(m + 1) \cdot \ldots \cdot 2m] \cdot [n \cdot \ldots \cdot (2n-2)]$ and thus $X' := m!nX = m!(m + n)!$ is a divisor of $M' := m!2n(2n-1)M$. And so $n!m!(n+m)! = n!X'$ is a divisor of $n!M' = (2m)!(2n)!$, which was to prove.

Agentmmk (talk) 16:43, 27 October 2015 (EDT)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1972_IMO_Problems/Problem_3&oldid=72621"