Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 3: | Line 3: | ||
is an integer. (<math>0! = 1</math>.) | is an integer. (<math>0! = 1</math>.) | ||
− | == Solution == | + | == Solution 1 == |
Let <math>f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}</math>. We intend to show that <math>f(m,n)</math> is integral for all <math>m,n \geq 0</math>. To start, we would like to find a recurrence relation for <math>f(m,n)</math>. | Let <math>f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}</math>. We intend to show that <math>f(m,n)</math> is integral for all <math>m,n \geq 0</math>. To start, we would like to find a recurrence relation for <math>f(m,n)</math>. | ||
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 == | ||
+ | WTS: For all primes <math>p</math>, <math>V_p((2m)!)+V_p((2n)!) \ge V_p(m!)+V_p(n!)+V_p((m+n)!)</math> | ||
+ | |||
+ | We know <cmath>V_p(x!)=\sum_{a=1}^{\infty} \lfloor{\frac{x}{p^a}}\rfloor</cmath> | ||
+ | |||
+ | Lemma 2.1: Let <math>a,b</math> be real numbers. Then <math>\lfloor{2a}\rfloor+\lfloor{2b}\rfloor\ge\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor</math> | ||
+ | |||
+ | Proof of Lemma 2.1: Let <math>a_1=\lfloor{a}\rfloor</math> and <math>b_1=\lfloor{b}\rfloor</math> | ||
+ | |||
+ | <math>\lfloor{2a}\rfloor+\lfloor{2b}\rfloor=2(a_1+b_1)+\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor</math> | ||
+ | |||
+ | On the other hand, <math>\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor=a_1+b_1+(a_1+b_1)+\lfloor\{a+b\}\rfloor</math> | ||
+ | |||
+ | It is trivial that <math>\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor\ge\lfloor\{a+b\}\rfloor</math> | ||
+ | |||
+ | Apply Lemma 2.1 to the problem: and we are pretty much done. | ||
+ | |||
+ | P.S. This is my work, but perhaps someone have come up with this method before I did. |
Revision as of 20:29, 20 November 2018
Let and be arbitrary non-negative integers. Prove that is an integer. (.)
Solution 1
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
WTS: For all primes ,
We know
Lemma 2.1: Let be real numbers. Then
Proof of Lemma 2.1: Let and
On the other hand,
It is trivial that
Apply Lemma 2.1 to the problem: and we are pretty much done.
P.S. This is my work, but perhaps someone have come up with this method before I did.