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>. | ||
− | == | + | |
− | {{ | + | ==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
where and denotes the greatest integer (e.g., ).
(b) Using (a) or otherwise, prove that
is integral for all positive integral and .
Background Knowledge
Note: A complete proof for this problem will require these results, and preferably also their proofs.
If , then . This is the definition of greatest integer less than itself.
If , then . This is easily proved by contradiction or consideration of the contrapositive.
If is an integer, then . This is proved from considering that .
This is a known fact: the exponent of a prime in the prime factorization of is .
Key Lemma
Lemma: For any pair of non-negative real numbers and , the following holds:
Proof of Key Lemma
We shall first prove the lemma statement for . Then , and so we have to prove that
Let , for integers and . Then , and so and .
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, , to be the value of the ceiling function minus one. Thus, if is an integer, and aba < ba \le [a] \le bb$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 = Ta \le bTSa = 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}y = [y] + {y}{x}x - [x]{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]a5[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.)ppI = \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.)pIII\blacksquare$
See Also
1975 USAMO (Problems • Resources) | ||
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.