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 2)
Line 1: Line 1:
 +
==Problem==
 +
 
Let <math>m</math> and <math>n</math> be arbitrary non-negative integers. Prove that
 
Let <math>m</math> and <math>n</math> be arbitrary non-negative integers. Prove that
 
<cmath>\frac{(2m)!(2n)!}{m!n!(m+n)!}</cmath>
 
<cmath>\frac{(2m)!(2n)!}{m!n!(m+n)!}</cmath>
Line 33: Line 35:
 
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>
 
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>
  
Line 54: Line 58:
 
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.
 
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}}
+
 
 +
==Remark about and correction to Solution 2==
  
 
The last step seems mistaken. For example [1.5]+[1.5]<[1.5+1.5]. Triangle inequality is about absolute value |x| not floor function [x]. Following is a rectified solution.
 
The last step seems mistaken. For example [1.5]+[1.5]<[1.5+1.5]. Triangle inequality is about absolute value |x| not floor function [x]. Following is a rectified solution.
  
 
Lemma: [a+b]<=[a]+[b]+1, a,b>=0.
 
Lemma: [a+b]<=[a]+[b]+1, a,b>=0.
 +
 
Proof: a<[a]+1, b<[b]+1, so a+b<[a]+[b]+2, [a+b]<=a+b<[a]+[b]+2, so [a+b]<=[a]+[b]+1.
 
Proof: a<[a]+1, b<[b]+1, so a+b<[a]+[b]+2, [a+b]<=a+b<[a]+[b]+2, so [a+b]<=[a]+[b]+1.
  
Line 64: Line 70:
 
V2(9!)=V2(1•2•3•4•5•6•7•8•9)
 
V2(9!)=V2(1•2•3•4•5•6•7•8•9)
 
=(2,4,6,8)+(4,8)+(8)=[9/2]+[9/4]+[9/8]=7.
 
=(2,4,6,8)+(4,8)+(8)=[9/2]+[9/4]+[9/8]=7.
 +
 
Generalize it and we have,
 
Generalize it and we have,
 
Vp(m!)=Vp(1•2•….•m)=[m/p]+[m/p^2]+…+[m/p^k], k=1~∞, or,
 
Vp(m!)=Vp(1•2•….•m)=[m/p]+[m/p^2]+…+[m/p^k], k=1~∞, or,
−
Vp(m!)=∑([m/p^k],k=1~∞)——(1).
+
 
 +
Vp(m!)=∑([m/p^k],k=1~∞)<math>\ \ \ \ (1)</math>.
 +
 
 
Obviously when p^k>m, k>=1, [m/p^k]=0.
 
Obviously when p^k>m, k>=1, [m/p^k]=0.
  
 
Note the target statement is equivalent to:
 
Note the target statement is equivalent to:
 +
 
for any prime p,
 
for any prime p,
 
Vp((2m)!(2n)!)>=Vp(m!n!(m+n)!), or,
 
Vp((2m)!(2n)!)>=Vp(m!n!(m+n)!), or,
−
Vp((2m)!)+Vp((2n)!)>=Vp(m!)+Vp(n!)+Vp(m+n)!——(2).
+
 
 +
Vp((2m)!)+Vp((2n)!)>=Vp(m!)+Vp(n!)+Vp(m+n)! <math>\ \ \ \ (2)</math>.
 +
 
 
Let m/p^k=a(k), n/p^k=b(k), k=1~∞.
 
Let m/p^k=a(k), n/p^k=b(k), k=1~∞.
−
Combine (1), we note that (2) is equivalent to: for any k in (1),
+
Combine (1), we note that (2) is equivalent to:
−
[2a(k)]+[2b(k)]>=[a(k)]+[b(k)]+[a(k)+b(k)]——(3).
+
 
 +
for any k in (1), [2a(k)]+[2b(k)]>=[a(k)]+[b(k)]+[a(k)+b(k)] <math>\ \ \ \ (3)</math>.
 +
 
 
For convenience of viewing, let a(k)=a, b(k)=b, a,b>=0, (3) is then rewritten as:
 
For convenience of viewing, let a(k)=a, b(k)=b, a,b>=0, (3) is then rewritten as:
−
[2a]+[2b]>=[a]+[b]+[a+b]——(4).
+
 
 +
[2a]+[2b]>=[a]+[b]+[a+b] <math>\ \ \ \ (4)</math>.
 +
 
 
We prove it under different scenarios:
 
We prove it under different scenarios:
  
Line 88: Line 104:
  
 
Therefore (4) is proved, so is (2), as every step from (2) to (4) is reversible. Therefore (2m)!(2n)!/(m!n!(m+n)!) is an integer. Proof completed.
 
Therefore (4) is proved, so is (2), as every step from (2) to (4) is reversible. Therefore (2m)!(2n)!/(m!n!(m+n)!) is an integer. Proof completed.
 +
 +
 +
== See Also == {{IMO box|year=1972|num-b=2|num-a=4}}

Revision as of 19:34, 25 April 2025

Problem

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.


Remark about and correction to Solution 2

The last step seems mistaken. For example [1.5]+[1.5]<[1.5+1.5]. Triangle inequality is about absolute value |x| not floor function [x]. Following is a rectified solution.

Lemma: [a+b]<=[a]+[b]+1, a,b>=0.

Proof: a<[a]+1, b<[b]+1, so a+b<[a]+[b]+2, [a+b]<=a+b<[a]+[b]+2, so [a+b]<=[a]+[b]+1.

Let (x,2x,…,nx)=n, p is any prime, V2(9!)=V2(1•2•3•4•5•6•7•8•9) =(2,4,6,8)+(4,8)+(8)=[9/2]+[9/4]+[9/8]=7.

Generalize it and we have, Vp(m!)=Vp(1•2•….•m)=[m/p]+[m/p^2]+…+[m/p^k], k=1~∞, or,

Vp(m!)=∑([m/p^k],k=1~∞)$\ \ \ \ (1)$.

Obviously when p^k>m, k>=1, [m/p^k]=0.

Note the target statement is equivalent to:

for any prime p, Vp((2m)!(2n)!)>=Vp(m!n!(m+n)!), or,

Vp((2m)!)+Vp((2n)!)>=Vp(m!)+Vp(n!)+Vp(m+n)! $\ \ \ \ (2)$.

Let m/p^k=a(k), n/p^k=b(k), k=1~∞. Combine (1), we note that (2) is equivalent to:

for any k in (1), [2a(k)]+[2b(k)]>=[a(k)]+[b(k)]+[a(k)+b(k)] $\ \ \ \ (3)$.

For convenience of viewing, let a(k)=a, b(k)=b, a,b>=0, (3) is then rewritten as:

[2a]+[2b]>=[a]+[b]+[a+b] $\ \ \ \ (4)$.

We prove it under different scenarios:

-If a<[a]+1/2, b<[b]+1/2, Then 2[a]<=[2a]<=2a<2[a]+1, [2a]=2[a], likewise, [2b]=2[b], so (4) is equivalent to [a]+[b]>=[a+b]. Per current condition, a+b<[a]+[b]+1, so [a+b]<[[a]+[b]+1]=[a]+[b]+1, also obviously [a+b]>=[a]+[b], so [a+b]=[a]+[b], proved;

-If a<[a]+1/2, b>=[b]+1/2, then [2a]=2[a], [2b]=2[b]+1, so (4) is equivalent to [a]+[b]+1>=[a+b], as per lemma, proved;

-If a>=[a]+1/2, b>=[b]+1/2, so [2a]=2[a]+1, [2b]=2[b]+1, so (4) is equivalent to [a]+[b]+2>=[a+b], as per lemma, proved;

Therefore (4) is proved, so is (2), as every step from (2) to (4) is reversible. Therefore (2m)!(2n)!/(m!n!(m+n)!) is an integer. Proof completed.


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=247361"