Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution) |
Mathboy100 (talk | contribs) |
||
(21 intermediate revisions by 7 users not shown) | |||
Line 3: | Line 3: | ||
is an integer. (<math>0! = 1</math>.) | is an integer. (<math>0! = 1</math>.) | ||
− | == Solution == | + | == Solution 1 == |
− | + | Denote the given expression as <math>f(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>. First, let's look at <math>f(m,n-1)</math>: | |
+ | <cmath>\begin{align*} | ||
+ | f(m,n-1) &=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!}\\ | ||
+ | &=\frac{(2m)!(2n)!(n-1)(m+n)}{m!n!(m+n)!(2n-1)(2n-2)}\\ | ||
+ | &=f(m,n) \cdot \frac{(n-1)(m+n)}{(2n-1)(2n-2)}\\ | ||
+ | &=f(m,n) \cdot \frac{m+n}{2(2n-1)} | ||
+ | \end{align*}</cmath> | ||
+ | Second, let's look at <math>f(m+1,n-1)</math>: | ||
+ | <cmath>\begin{align*} | ||
+ | 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) \cdot \frac{(2m+1)(2m+2)(n-1)}{(m+1)(2n-1)(2n-2)}\\ | ||
+ | &=f(m,n) \cdot \frac{(2m+1)}{2n-1} | ||
+ | \end{align*}</cmath> | ||
+ | Combining, | ||
+ | <cmath>\begin{align*} | ||
+ | 4f(m,n-1)-f(m+1,n-1) &=f(m,n)\cdot \Bigg(\frac{4(m+n)}{2(2n-1)}-\frac{2m+1}{2n-1}\Bigg)\\ | ||
+ | &=f(m,n) \cdot \frac{2m+2n-2m-1}{2n-1}\\ | ||
+ | &=f(m,n). | ||
+ | \end{align*}</cmath> | ||
+ | Therefore, we have found the recurrence relation <cmath>f(m,n)=4f(m,n-1)-f(m+1,n-1).</cmath> | ||
− | + | Note that <math>f(m,0)</math> is just <math>\binom{2m}{m}</math>, which is an integer for all <math>m \geq 0</math>. Then <cmath>f(m,1)=4f(m,0)-f(m+1,0),</cmath> so <math>f(m,1)</math> is an integer, and therefore <math>f(m,2)=4f(m,1)-f(m+1,1)</math> must be an integer, etc. | |
− | <math>f(m,n | + | By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</math>. |
− | + | Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html | |
+ | |||
+ | == Solution 2 == | ||
+ | Let p be a prime, and n be an integer. Let <math>V_p(n)</math> be the largest positive integer <math>k</math> such that <math>p^k|n</math> | ||
+ | |||
+ | 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} \left\lfloor{\frac{x}{p^a}}\right\rfloor</cmath> | ||
− | <math> | + | 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> | + | <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\{2(a+b)\}\rfloor</math> | |
− | + | It is trivial that <math>\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor\ge\lfloor\{2(a+b)\}\rfloor</math> (Triangle Inequality) | |
− | + | Apply Lemma 2.1 to the problem: and we are pretty much done. | |
− | + | Note: I am lazy, so this is only the most important part. I hope you can come up with the rest of the solution. This is my work, but perhaps someone have come up with this method before I did. | |
− | + | == See Also == {{IMO box|year=1972|num-b=2|num-a=4}} |
Latest revision as of 23:26, 6 December 2022
Let and be arbitrary non-negative integers. Prove that is an integer. (.)
Solution 1
Denote the given expression as . 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
Note that is just , which is an integer for all . Then so is an integer, and therefore must be an integer, etc.
By induction, is an integer for all .
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html
Solution 2
Let p be a prime, and n be an integer. Let be the largest positive integer such that
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 (Triangle Inequality)
Apply Lemma 2.1 to the problem: and we are pretty much done.
Note: I am lazy, so this is only the most important part. I hope you can come up with the rest of the solution. This is my work, but perhaps someone have come up with this method before I did.
See Also
1972 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |