Difference between revisions of "1972 IMO Problems/Problem 3"
Mathboy100 (talk | contribs) |
Mathboy100 (talk | contribs) (→Solution) |
||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | If <math>m = n</math>, then < | + | If <math>m = n</math>, then |
+ | <cmath>\frac{(2m)!(2n)!}{m!n!(m+n)!} = \frac{(2m)!(2m)!}{m!^2(2m)!} = \frac{(2m)!}{m!^2} = {2m \choose m},</cmath> | ||
+ | which is integral. | ||
+ | |||
+ | Suppose that <math>m \neq n</math>. Then, we have | ||
+ | <cmath>\frac{(2m)!(2n)!}{m!n!(m+n)!}</cmath> | ||
+ | <cmath> = \frac{(2m)!}{m!n!} \cdot \frac{(2n!)}{(m+n)!}</cmath> | ||
+ | <cmath> = \frac{(2m}!}{m!^2} \cdot \frac{m!}{n!} \cdot \frac{(2n!)}{(m+n)!}</cmath> | ||
+ | <cmath> = \frac{(2m}!}{m!^2} \cdot \frac{m!}{n!} \cdot (m+n+1) \cdot (m+n+2) \dotsm \cdot (2n)</cmath> | ||
== Solution 2 == | == Solution 2 == |
Revision as of 23:08, 6 December 2022
Let and be arbitrary non-negative integers. Prove that is an integer. (.)
Contents
Solution
If , then which is integral.
Suppose that . Then, we have
\[= \frac{(2m}!}{m!^2} \cdot \frac{m!}{n!} \cdot \frac{(2n!)}{(m+n)!}\] (Error compiling LaTeX. Unknown error_msg)
\[= \frac{(2m}!}{m!^2} \cdot \frac{m!}{n!} \cdot (m+n+1) \cdot (m+n+2) \dotsm \cdot (2n)\] (Error compiling LaTeX. Unknown error_msg)
Solution 2
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 3
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 |