Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution 1) |
Mathboy100 (talk | contribs) |
||
Line 3: | Line 3: | ||
is an integer. (<math>0! = 1</math>.) | is an integer. (<math>0! = 1</math>.) | ||
− | == Solution | + | ==Solution== |
+ | If <math>m = n</math>, then <math>\frac{(2m)!(2n)!}{m!n!(m+n)!} = \frac{(2m)!(2m)!}{m!^2(2m)!} = \frac{(2m)!}{m!^2} = {2m \choose m}</math> which is integral. | ||
+ | |||
+ | == Solution 2 == | ||
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>: | 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>: | ||
Line 33: | Line 36: | ||
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 | + | == Solution 3 == |
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> | 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> | ||
Revision as of 00:04, 7 December 2022
Let and
be arbitrary non-negative integers. Prove that
is an integer. (
.)
Contents
Solution
If , then
which is integral.
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 |