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

Revision as of 12:41, 22 August 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.

@@ Line 27: / Line 27: @@
 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. By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</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>.
 Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html

1972 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

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

Revision as of 12:41, 22 August 2022

Solution 1

Solution 2

See Also