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 and
be arbitrary non-negative integers. Prove that
is an integer. (
.)
Solution
Let . We intend to show that
is integral for all
. To start, we would like to find a recurrence relation for
.
First, let's look at :
Second, let's look at :
Combining,
.
Therefore, we have found the recurrence relation .
We can see that is integral because the RHS is just
, which we know to be integral for all
.
So, must be integral, and then
must be integral, etc.
By induction, is integral for all
.
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 . In that case
and
.
With induction in we prove the induction start for
which states that
is a multiple of
for all natural numbers
(including 0) (Assertion 1):
For (induction start) we have
. Hence, we can assume that Assertion 1 holds for
and
: That means that
is a multiple of
. Division by
leads to the result that
is a divisor of
and thus
is a divisor of
. And so
is a divisor of
, which is Assertion 1.
Hence, for as induction start in
the statement holds for all
.
So we assume that the statement also holds for all natural numbers
, where
, and all natural numbers
(including 0), which means that
we assume that
divides
for all
. Division by
leads to the result that
is a divisor of
and thus
is a divisor of
. And so
is a divisor of
, which was to prove.