Difference between revisions of "1975 USAMO Problems/Problem 1"
(→Proof of Key Lemma) |
m (→How the Key Lemma Solves the Problem) |
||
(9 intermediate revisions by 5 users not shown) | |||
Line 18: | Line 18: | ||
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>. | 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>. | + | 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>. (Legendre's Formula) |
==Key Lemma== | ==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> | + | ''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>vcd |
− | |||
==Proof of Key Lemma== | ==Proof of Key Lemma== | ||
We shall first prove the lemma statement for <math>0 \le 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> | We shall first prove the lemma statement for <math>0 \le 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 \text{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 \text{ 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> 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.) | 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 \left [ \left [\frac{3a+b+4}{5} \right ] \right] + \left[\left[\frac{3b+a+4}{5} \right]\right] = S.</cmath> |
− | + | We shall prove that <math>S \le a + b = T</math>; to do so, we list cases. Without loss of generality, let <math>a \le b</math>. Because <math>x</math> and <math>y</math> are less than one, we have <math>a \le b \le 4.</math> Then, we find, for all 15 cases: | |
<math>a = 0, b = 0 \rightarrow S = 0, T = 0.</math> | <math>a = 0, b = 0 \rightarrow S = 0, T = 0.</math> | ||
Line 66: | Line 65: | ||
<math>a = 4, b = 4 \rightarrow S = 6, T = 8.</math> | <math>a = 4, b = 4 \rightarrow S = 6, T = 8.</math> | ||
− | Thus, we have proved for all x and y in the range <math> | + | Thus, we have proved for all x and y in the range <math>[0, 1)</math>, <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 | 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\} + | + | <cmath>[5[x] + 5\{x\}] + [5[y] + 5\{y\}] \ge [x] + [y] + [3[x] + 3\{x\} + [y] + \{y\}] + [3[y] + 3\{y\} + [x] + \{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 | 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 | ||
Line 85: | Line 84: | ||
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 | + | But, the left-hand side minus the right-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[ \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== |
Latest revision as of 02:43, 8 June 2024
Contents
Problem
(a) Prove that
![$[5x]+[5y]\ge [3x+y]+[3y+x]$](http://latex.artofproblemsolving.com/f/3/5/f35b4df2174c9e93d13d91ef893d3c1743e22e01.png)
where and
denotes the greatest integer
(e.g.,
).
(b) Using (a) or otherwise, prove that
![$\frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}$](http://latex.artofproblemsolving.com/8/a/d/8adf3172b9cbf506283e6114ccb395d9c4901dcf.png)
is integral for all positive integral and
.
Background Knowledge
Note: A complete proof for this problem may require these results, and preferably also their proofs.
If , then
. This is the alternate definition of
.
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
. (Legendre's Formula)
Key Lemma
Lemma: For any pair of non-negative real numbers and
, the following holds:
vcd
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,
We shall prove that ; to do so, we list cases. Without loss of generality, let
. Because
and
are less than one, we have
Then, we find, for all 15 cases:
Thus, we have proved for all x and y in the range ,
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 corollary of the lemma.
For part (b), consider an arbitrary prime . We have to prove the exponent of
in
![$I = \frac{(5m)!(5n)!}{m!n!(3m+n)!(3n+m)!}$](http://latex.artofproblemsolving.com/e/a/a/eaa6effc911895fe1df8d2041e7d5bab905e0e1f.png)
is non-negative, or equivalently that
But, the left-hand side minus the right-hand side of this inequality is 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.