Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution) |
Mathboy100 (talk | contribs) |
||
(20 intermediate revisions by 7 users not shown) | |||
Line 5: | Line 5: | ||
== Solution 1 == | == 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*} | |
− | First, let's look at <math>f(m,n-1)</math>: | + | 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>: | 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, | 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> | ||
− | <math> | + | 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. |
− | |||
− | |||
− | + | By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</math>. | |
− | |||
− | |||
− | |||
− | By induction, <math>f(m,n)</math> is | ||
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 == | == 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> | 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> | + | We know <cmath>V_p(x!)=\sum_{a=1}^{\infty} \left\lfloor{\frac{x}{p^a}}\right\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> | 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> | ||
Line 40: | Line 46: | ||
<math>\lfloor{2a}\rfloor+\lfloor{2b}\rfloor=2(a_1+b_1)+\lfloor2\{a\}\rfloor+\lfloor2\{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> | + | 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\{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. | 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 00:26, 7 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 |