Difference between revisions of "1972 IMO Problems/Problem 3"

Revision as of 02:26, 28 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

@@ Line 28: / Line 28: @@
 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)

Page

Toolbox

Search

Difference between revisions of "1972 IMO Problems/Problem 3"

Revision as of 02:26, 28 October 2015

Solution