Difference between revisions of "1975 USAMO Problems/Problem 1"
(→Proof of Key Lemma) |
|||
Line 30: | Line 30: | ||
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>. | 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]</ | + | 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> 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, | Therefore, | ||
<cmath>[3x + y] + [3y + x] \le [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.</cmath> | <cmath>[3x + y] + [3y + x] \le [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.</cmath> | ||
− | To prove that < | + | 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> | 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 < | + | 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> | <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 < | + | 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> | <cmath>[5{x}] + [5{y}] \ge [3{x} + {y}] + [3{y} + {x}],</cmath> | ||
− | which we have already proved (as < | + | 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== | ==How the Key Lemma Solves the Problem== | ||
Part (a) is a direct collorary of the lemma. | Part (a) is a direct collorary of the lemma. | ||
− | For part (b), consider an arbitrary prime < | + | For part (b), consider an arbitrary prime <math>p</math>. We have to prove the exponent of <math>p</math> in |
− | <center>< | + | <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> | 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 < | + | 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</math> |
==See Also== | ==See Also== |
Revision as of 15:50, 16 August 2014
Contents
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 otherwise. It is not difficult to verify that if and are real numbers with , then . (The only new thing we have to consider here is the case where is integral, which is trivial.)
Therefore,
To prove that , we shall list cases. Without loss of generality, let . (There are only 15 cases, all simple computations: is obvious, and is easy. Compare this to an assembly line.)
Thus, we have proved for all x and y between 0 and 1, exclusive,
Now, we prove the lemma statement without restrictions on x and y. Let , and , where , the fractional part of x, is defined to be . Note that as a result. Substituting gives the equivalent inequality
But, because for any integer , this is obtained from simplifications following the adding of to both sides of
which we have already proved (as ). 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 . We have to prove the exponent of in
is non-negative, or equivalently that
But, the right-hand side minus the left-hand side of this inequality is
\[\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),\] (Error compiling LaTeX. ! Missing \right. inserted.)
which is the sum of non-negative terms by the Lemma. Thus, the inequality is proved, and so, by considering all primes , we deduce that the exponents of all primes in are non-negative. This proves the integrality of (i.e. is an integer).
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.