Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1972 IMO Problems/Problem 3"

(→‎Solution)
 
(24 intermediate revisions by 8 users not shown)
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>.
 
−
 
 
−
First, let's look at <math>f(m,n-1)</math>:
 
−
 
 
−
<math>f(m,n-1)=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!}=\frac{(2m)!(2n)!(n-1)(m+n-1)}{m!n!(m+n)!(2n-1)(2n-2)}=f(m,n) \frac{(n-1)(m+n-1)}{(2n-1)(2n-2)}=f(m,n) \frac{m+n-1}{2(2n-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>:
 +
<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>:
 
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>
  
−
<math>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) \frac{(2m+1)(2m+2)(n-1)}{(m+1)(2n-1)(2n-2)}=f(m,n) \frac{(2m+1)}{2n-1}</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.
  
−
Combining,
+
By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</math>.
  
−
<math>4f(m,n-1)-f(m+1,n-1)=f(m,n) (\frac{4(m+n-1)}{2(2n-1)}-\frac{2m+1}{2n-1})=f(m,n) \frac{2m+2n-2-2m+1}{2n-1}=f(m,n)</math>.
+
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html
−
 
 
−
Therefore, we have found the recurrence relation <math>f(m,n)=4f(m,n-1)-f(m+1,n-1)</math>.
 
  
−
We can see that <math>f(m,0)=\frac{(2m)!}{m!m!}</math> is integral because the RHS is just <math>_{2m} C _m</math>, which we know to be integral for all <math>m \geq 0</math>.
+
== 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>
  
−
So, <math>f(m,1)=4f(m,0)-f(m+1,0)</math> must be integral, and then <math>f(m,2)=4f(m,1)-f(m+1,1)</math> must be integral, etc.
+
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>
  
−
By induction, <math>f(m,n)</math> is integral for all <math>m,n \geq 0</math>.
+
We know <cmath>V_p(x!)=\sum_{a=1}^{\infty} \left\lfloor{\frac{x}{p^a}}\right\rfloor</cmath>
  
−
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html
+
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>
  
−
== Solution 2  ==
+
<math>\lfloor{2a}\rfloor+\lfloor{2b}\rfloor=2(a_1+b_1)+\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor</math>
−
An alternative solution is nested induction in n and m.
 
−
As induction start we have the case <math>n = 0</math>. In that case <math>m!n!(m+n)! = (m!)^2</math> and <math>(2m)!(2n)! = (2m)!</math>.
 
  
−
With induction in <math>m</math> we prove the induction start for <math>n = 0</math> which states that
+
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>
  
−
<math>(2m)!</math> is a multiple of <math>(m!)^2</math> for all natural numbers <math>m</math> (including 0) (Assertion 1):
+
It is trivial that <math>\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor\ge\lfloor\{2(a+b)\}\rfloor</math> (Triangle Inequality)
  
−
For <math>m = 0</math> (induction start) we have <math>(2m)! = 1 = (m!)^2</math>. Hence, we can assume that Assertion 1 holds for <math>m - 1</math> and <math>m > 0</math>: That means that <math>(2m-2)!</math> is a multiple of <math>((m-1)!)^2</math>. Division by <math>(m-1)!</math> leads to the result that <math>X:= (m-1)! = 1 \cdot 2 \cdot \ldots (m-1)</math>
+
Apply Lemma 2.1 to the problem: and we are pretty much done.
−
is a divisor of <math>M := m \cdot \ldots \cdot (2m-2)</math> and thus <math>X' := mX = 1 \cdot 2 \cdot \ldots m</math>
 
−
is a divisor of <math>M' := 2m(2m-1)M = m \cdot \ldots \cdot 2m</math>. And so <math>(m!)^2 = m!X'</math> is a divisor of
 
−
<math>m!M' = (2m)!</math>, which is Assertion 1.
 
  
−
Hence, for <math>n = 0</math> as induction start in <math>n</math> the statement holds for all <math>m</math>.
+
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.
−
So we assume that the statement also holds for all natural numbers <math>n - 1</math>, where <math>n > 0</math>, and all natural numbers <math>m</math> (including 0), which means that
 
−
we assume that <math>m!(n-1)!(m+n-1)!</math> divides <math>(2m)!(2n-2)!</math> for all <math>m</math>. Division by <math>m!(n-1)!</math> leads to the result that <math>X:= (m+n-1)! = 1 \cdot 2 \cdot \ldots (m + n - 1)</math>
 
−
is a divisor of <math>M := [(m + 1) \cdot \ldots \cdot 2m] \cdot [n \cdot \ldots \cdot (2n-2)]</math> and thus <math>X' := m!nX = m!(m + n)!</math>
 
−
is a divisor of <math>M' := m!2n(2n-1)M</math>. And so <math>n!m!(n+m)! = n!X'</math> is a divisor of <math>n!M' = (2m)!(2n)!</math>, which was to prove.
 
  
−
[[User:Agentmmk|Agentmmk]] ([[User talk:Agentmmk|talk]]) 16:43, 27 October 2015 (EDT)
+
== See Also == {{IMO box|year=1972|num-b=2|num-a=4}}

Latest revision as of 23:26, 6 December 2022

Let $m$ and $n$ be arbitrary non-negative integers. Prove that \[\frac{(2m)!(2n)!}{m!n!(m+n)!}\] is an integer. ($0! = 1$.)

Solution 1

Denote the given expression as $f(m,n)$. We intend to show that $f(m,n)$ is integral for all $m,n \geq 0$. To start, we would like to find a recurrence relation for $f(m,n)$. First, let's look at $f(m,n-1)$: \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*} Second, let's look at $f(m+1,n-1)$: \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*} Combining, \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*} Therefore, we have found the recurrence relation \[f(m,n)=4f(m,n-1)-f(m+1,n-1).\]

Note that $f(m,0)$ is just $\binom{2m}{m}$, which is an integer for all $m \geq 0$. Then \[f(m,1)=4f(m,0)-f(m+1,0),\] so $f(m,1)$ is an integer, and therefore $f(m,2)=4f(m,1)-f(m+1,1)$ must be an integer, etc.

By induction, $f(m,n)$ is an integer for all $m,n \geq 0$.

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 $V_p(n)$ be the largest positive integer $k$ such that $p^k|n$

WTS: For all primes $p$, $V_p((2m)!)+V_p((2n)!) \ge V_p(m!)+V_p(n!)+V_p((m+n)!)$

We know \[V_p(x!)=\sum_{a=1}^{\infty} \left\lfloor{\frac{x}{p^a}}\right\rfloor\]

Lemma 2.1: Let $a,b$ be real numbers. Then $\lfloor{2a}\rfloor+\lfloor{2b}\rfloor\ge\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor$

Proof of Lemma 2.1: Let $a_1=\lfloor{a}\rfloor$ and $b_1=\lfloor{b}\rfloor$

$\lfloor{2a}\rfloor+\lfloor{2b}\rfloor=2(a_1+b_1)+\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor$

On the other hand, $\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor=a_1+b_1+(a_1+b_1)+\lfloor\{2(a+b)\}\rfloor$

It is trivial that $\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor\ge\lfloor\{2(a+b)\}\rfloor$ (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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1972_IMO_Problems/Problem_3&oldid=183691"