1972 IMO Problems/Problem 3
Contents
Problem
Let and
be arbitrary non-negative integers. Prove that
is an integer. (
.)
Solution 1
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 2
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.
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~∞).
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)! .
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)] .
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] .
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.
Remarks (added by pf02, April 2025)
1. The first solution has a few errors in the computation, but they cancel out, and the proof is essentially correct. Below I will give the corrections, to make the solution flawless.
2. As pointed out by a contributor, the second solution is incorrect. The correction given is good, but very sloppily written and hard to read (even after I edited the spacing, to make it legible). Below, I will repeat the argument in a simplified form, to make it easier to follow.
3. I will give a third solution below, inspired by the papers mentioned in the next paragraph.
4. The problem is a classical result, attributed to Eugene
Catalan, who stated it in a paper published in 1874. The
numbers are
sometimes called the super-Catalan numbers. (They are
mentioned at the end of
https://en.wikipedia.org/wiki/Catalan_number).
There are a few papers published about them. See for example
the paper "The Super Catalan Numbers for
and Some Integer Factorial Ratios" by Xin Chen & Jane Wang
(https://www-users.cse.umn.edu/~reiner/REU/ChenWang2012.pdf),
and "Super Ballot Numbers" by Ira M. Gessel (especially section 6)
(https://www.sciencedirect.com/science/article/pii/0747717192900342/pdf).
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 |