Difference between revisions of "1975 USAMO Problems/Problem 1"

Line 8: Line 8:
 
is integral for all positive integral <math>m</math> and <math>n</math>.
 
is integral for all positive integral <math>m</math> and <math>n</math>.
  
==Solution==
+
 
{{solution}}
+
==Background Knowledge==
 +
''Note: A complete proof for this problem will require these results, and preferably also their proofs.''
 +
 
 +
If <math>[x] = a</math>, then <math>x < a + 1</math>. This is the definition of greatest integer less than itself.
 +
 
 +
If <math>a < b</math>, then <math>[a] \le [b]</math>. This is easily proved by contradiction or consideration of the contrapositive.
 +
 
 +
If <math>a</math> is an integer, then <math>[x + a] = [x] + a</math>. This is proved from considering that <math>[x] + a \le x + a < [x] + a + 1</math>.
 +
 
 +
This is a known fact: the exponent of a prime <math>p</math> in the prime factorization of <math>n!</math> is <math>\sum_{k=1}^\infty \left[ \frac{n}{p^k} \right]</math>.
 +
 
 +
 
 +
==Key Lemma==
 +
''Lemma:'' For any pair of non-negative real numbers <math>x</math> and <math>y</math>, the following holds: <cmath>[5x] + [5y] \ge [x] + [y] + [3x + y] + [3y + x].</cmath>
 +
 
 +
 
 +
==Proof of Key Lemma==
 +
We shall first prove the lemma statement for <math>x, y < 1</math>. Then <math>[x] = [y] = 0</math>, and so we have to prove that <cmath>[5x] + [5y] \ge [3x + y] + [3y + x].</cmath>
 +
 
 +
Let <math>[5x] = a, [5y] = b</math>, for integers <math>a</math> and <math>b</math>. Then <math>5x < a + 1 and 5y < b + 1</math>, and so <math>x < \frac{a+1}{5}</math> and <math>y < \frac{b+1}{5}</math>.
 +
 
 +
Define a new function, the ceiling function of x, to be the least integer greater than or equal to x. Also, define the ''trun-ceil function'', <math>[[x]]</math>, to be the value of the ceiling function minus one. Thus, <math>[[a]] = a - 1</math> if <math>a</math> is an integer, and <math>[[a]] = [a]</math><math> otherwise. It is not difficult to verify that if </math>a<math> and </math>b<math> are real numbers with </math>a < b<math>, then </math>[[a]] \le [a] \le [[b]]<math>. (The only new thing we have to consider here is the case where </math>b<math> is integral, which is trivial.)
 +
 
 +
Therefore,
 +
<cmath>[3x + y] + [3y + x] \le [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.</cmath>
 +
 
 +
To prove that </math>S \le a + b = T<math>, we shall list cases. Without loss of generality, let </math>a \le b<math>. (There are only 15 cases, all simple computations: </math>T<math> is obvious, and </math>S<math> is easy. Compare this to an assembly line.)
 +
 
 +
</math>a = 0, b = 0 \rightarrow S = 0, T = 0.<math>
 +
</math>a = 0, b = 1 \rightarrow S = 1, T = 1.<math>
 +
</math>a = 0, b = 2 \rightarrow S = 2, T = 2.<math>
 +
</math>a = 0, b = 3 \rightarrow S = 3, T = 3.<math>
 +
</math>a = 0, b = 4 \rightarrow S = 4, T = 4.<math>
 +
</math>a = 1, b = 1 \rightarrow S = 2, T = 2.<math>
 +
</math>a = 1, b = 2 \rightarrow S = 3, T = 3.<math>
 +
</math>a = 1, b = 3 \rightarrow S = 3, T = 4.<math>
 +
</math>a = 1, b = 4 \rightarrow S = 5, T = 5.<math>
 +
</math>a = 2, b = 2 \rightarrow S = 4, T = 4.<math>
 +
</math>a = 2, b = 3 \rightarrow S = 4, T = 5.<math>
 +
</math>a = 2, b = 4 \rightarrow S = 5, T = 6.<math>
 +
</math>a = 3, b = 3 \rightarrow S = 6, T = 6.<math>
 +
</math>a = 3, b = 4 \rightarrow S = 6, T = 7.<math>
 +
</math>a = 4, b = 4 \rightarrow S = 6, T = 8.<math>
 +
 
 +
Thus, we have proved for all x and y between 0 and 1, exclusive, <cmath>[5x] + [5y] = T \ge S \ge [3x + y] + [3y + x].</cmath>
 +
 
 +
Now, we prove the lemma statement without restrictions on x and y. Let </math>x = [x] + {x}<math>, and </math>y = [y] + {y}<math>, where </math>{x}<math>, the fractional part of x, is defined to be </math>x - [x]<math>. Note that </math>{x} < 1<math> as a result. Substituting gives the equivalent inequality
 +
 
 +
<cmath>[5[x] + 5{x}] + [5[y] + 5{y}] \ge [x] + [y] + [3[x] + 3{x} + [y] + {y}] + [3[y] + 3{y} + 3[x] + 3{x}].</cmath>
 +
 
 +
But, because </math>[x] + a = [x + a]<math> for any integer </math>a<math>, this is obtained from simplifications following the adding of </math>5[x] + 5[y]<math> to both sides of
 +
 
 +
<cmath>[5{x}] + [5{y}] \ge [3{x} + {y}] + [3{y} + {x}],</cmath>
 +
 
 +
which we have already proved (as </math>0 \le {x}, {y} < 1<math>). Thus, the lemma is proved.
 +
 
 +
==How the Key Lemma Solves the Problem==
 +
Part (a) is a direct collorary of the lemma.
 +
 
 +
For part (b), consider an arbitrary prime </math>p<math>. We have to prove the exponent of </math>p<math> in
 +
<center></math>I = \frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}<math></center>
 +
is non-negative, or equivalently that <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] \right) \ge \sum_{k=1}^{\infty} \left( \left[ \frac{m}{p^k} \right] + \left[ \frac{n}{p^k} \right] + \left[ \frac{3m+n}{p^k} \right] + \left[ \frac{3n+m}{p^k} \right] \right).</cmath>
 +
 
 +
But, the right-hand side minus the left-hand side of this inequality is <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] - \left( \left[ \frac{m}{p^k} \right] + \left[ \frac{n}{p^k} \right] + \left[ \frac{3m+n}{p^k} \right] + \left[ \frac{3n+m}{p^k} \right] \right),</cmath> which is the sum of non-negative terms by the Lemma. Thus, the inequality is proved, and so, by considering all primes </math>p<math>, we deduce that the exponents of all primes in </math>I<math> are non-negative. This proves the integrality of </math>I<math> (i.e. </math>I<math> is an integer). </math>\blacksquare$
  
 
==See Also==
 
==See Also==

Revision as of 15:47, 16 August 2014

Problem

(a) Prove that

$[5x]+[5y]\ge [3x+y]+[3y+x]$,

where $x,y\ge 0$ and $[u]$ denotes the greatest integer $\le u$ (e.g., $[\sqrt{2}]=1$).

(b) Using (a) or otherwise, prove that

$\frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}$

is integral for all positive integral $m$ and $n$.


Background Knowledge

Note: A complete proof for this problem will require these results, and preferably also their proofs.

If $[x] = a$, then $x < a + 1$. This is the definition of greatest integer less than itself.

If $a < b$, then $[a] \le [b]$. This is easily proved by contradiction or consideration of the contrapositive.

If $a$ is an integer, then $[x + a] = [x] + a$. This is proved from considering that $[x] + a \le x + a < [x] + a + 1$.

This is a known fact: the exponent of a prime $p$ in the prime factorization of $n!$ is $\sum_{k=1}^\infty \left[ \frac{n}{p^k} \right]$.


Key Lemma

Lemma: For any pair of non-negative real numbers $x$ and $y$, the following holds: \[[5x] + [5y] \ge [x] + [y] + [3x + y] + [3y + x].\]


Proof of Key Lemma

We shall first prove the lemma statement for $x, y < 1$. Then $[x] = [y] = 0$, and so we have to prove that \[[5x] + [5y] \ge [3x + y] + [3y + x].\]

Let $[5x] = a, [5y] = b$, for integers $a$ and $b$. Then $5x < a + 1 and 5y < b + 1$, and so $x < \frac{a+1}{5}$ and $y < \frac{b+1}{5}$.

Define a new function, the ceiling function of x, to be the least integer greater than or equal to x. Also, define the trun-ceil function, $[[x]]$, to be the value of the ceiling function minus one. Thus, $[[a]] = a - 1$ if $a$ is an integer, and $[[a]] = [a]$$otherwise. It is not difficult to verify that if$a$and$b$are real numbers with$a < b$, then$a \le [a] \le b$. (The only new thing we have to consider here is the case where$b$is integral, which is trivial.)

Therefore, <cmath>[3x + y] + [3y + x] \le [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.</cmath>

To prove that$ (Error compiling LaTeX. ! Missing $ inserted.)S \le a + b = T$, we shall list cases. Without loss of generality, let$a \le b$. (There are only 15 cases, all simple computations:$T$is obvious, and$S$is easy. Compare this to an assembly line.)$a = 0, b = 0 \rightarrow S = 0, T = 0.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 0, b = 1 \rightarrow S = 1, T = 1.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 0, b = 2 \rightarrow S = 2, T = 2.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 0, b = 3 \rightarrow S = 3, T = 3.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 0, b = 4 \rightarrow S = 4, T = 4.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 1, b = 1 \rightarrow S = 2, T = 2.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 1, b = 2 \rightarrow S = 3, T = 3.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 1, b = 3 \rightarrow S = 3, T = 4.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 1, b = 4 \rightarrow S = 5, T = 5.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 2, b = 2 \rightarrow S = 4, T = 4.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 2, b = 3 \rightarrow S = 4, T = 5.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 2, b = 4 \rightarrow S = 5, T = 6.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 3, b = 3 \rightarrow S = 6, T = 6.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 3, b = 4 \rightarrow S = 6, T = 7.$$ (Error compiling LaTeX. ! Missing $ inserted.)a = 4, b = 4 \rightarrow S = 6, T = 8.$Thus, we have proved for all x and y between 0 and 1, exclusive, <cmath>[5x] + [5y] = T \ge S \ge [3x + y] + [3y + x].</cmath>

Now, we prove the lemma statement without restrictions on x and y. Let$ (Error compiling LaTeX. ! Missing $ inserted.)x = [x] + {x}$, and$y = [y] + {y}$, where${x}$, the fractional part of x, is defined to be$x - [x]$. Note that${x} < 1$as a result. Substituting gives the equivalent inequality

<cmath>[5[x] + 5{x}] + [5[y] + 5{y}] \ge [x] + [y] + [3[x] + 3{x} + [y] + {y}] + [3[y] + 3{y} + 3[x] + 3{x}].</cmath>

But, because$ (Error compiling LaTeX. ! Missing $ inserted.)[x] + a = [x + a]$for any integer$a$, this is obtained from simplifications following the adding of$5[x] + 5[y]$to both sides of

<cmath>[5{x}] + [5{y}] \ge [3{x} + {y}] + [3{y} + {x}],</cmath>

which we have already proved (as$ (Error compiling LaTeX. ! Missing $ inserted.)0 \le {x}, {y} < 1$). Thus, the lemma is proved.

==How the Key Lemma Solves the Problem== Part (a) is a direct collorary of the lemma.

For part (b), consider an arbitrary prime$ (Error compiling LaTeX. ! Missing $ inserted.)p$. We have to prove the exponent of$p$in <center>$I = \frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}$</center> is non-negative, or equivalently that <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] \right) \ge \sum_{k=1}^{\infty} \left( \left[ \frac{m}{p^k} \right] + \left[ \frac{n}{p^k} \right] + \left[ \frac{3m+n}{p^k} \right] + \left[ \frac{3n+m}{p^k} \right] \right).</cmath>

But, the right-hand side minus the left-hand side of this inequality is <cmath>\sum_{k=1}^{\infty} \left( \left[ \frac{5m}{p^k} \right] + \left[ \frac{5n}{p^k} \right] - \left( \left[ \frac{m}{p^k} \right] + \left[ \frac{n}{p^k} \right] + \left[ \frac{3m+n}{p^k} \right] + \left[ \frac{3n+m}{p^k} \right] \right),</cmath> which is the sum of non-negative terms by the Lemma. Thus, the inequality is proved, and so, by considering all primes$ (Error compiling LaTeX. ! Missing $ inserted.)p$, we deduce that the exponents of all primes in$I$are non-negative. This proves the integrality of$I$(i.e.$I$is an integer).$\blacksquare$

See Also

1975 USAMO (ProblemsResources)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Invalid username
Login to AoPS