Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎How the Key Lemma Solves the Problem)
m (→‎How the Key Lemma Solves the Problem)
 
(13 intermediate revisions by 5 users not shown)
Line 10: Line 10:
  
 
==Background Knowledge==
 
==Background Knowledge==
−
''Note: A complete proof for this problem will require these results, and preferably also their proofs.''
+
''Note: A complete proof for this problem may require these results, and preferably also their proofs.''
  
 
If <math>[x] = a</math>, then <math>a \le x < a + 1</math>. This is the alternate definition of <math>[x]</math>.
 
If <math>[x] = a</math>, then <math>a \le x < a + 1</math>. This is the alternate definition of <math>[x]</math>.
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>
  
−
To prove that <math>S \le a + b = T</math>, we shall list cases. Without loss of generality, let <math>a \le b</math>. Then, we find, for all 15 cases:
+
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>(0, 1]</math>, <cmath>[5x] + [5y] = T \ge S \ge [3x + y] + [3y + x].</cmath>
+
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} + 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\} + [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
  
−
<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 <math>0 \le {x}, {y} < 1</math>). Thus, the lemma is proved.
+
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==
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 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[ \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>
+
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 01:43, 8 June 2024

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 may require these results, and preferably also their proofs.

If $[x] = a$, then $a \le x < a + 1$. This is the alternate definition of $[x]$.

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]$. (Legendre's Formula)

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].\]vcd

Proof of Key Lemma

We shall first prove the lemma statement for $0 \le 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 \text{ 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, \[[3x + y] + [3y + x] \le \left [ \left [\frac{3a+b+4}{5} \right ] \right] + \left[\left[\frac{3b+a+4}{5} \right]\right] = S.\]

We shall prove that $S \le a + b = T$; to do so, we list cases. Without loss of generality, let $a \le b$. Because $x$ and $y$ are less than one, we have $a \le b \le 4.$ Then, we find, for all 15 cases:

$a = 0, b = 0 \rightarrow S = 0, T = 0.$

$a = 0, b = 1 \rightarrow S = 1, T = 1.$

$a = 0, b = 2 \rightarrow S = 2, T = 2.$

$a = 0, b = 3 \rightarrow S = 3, T = 3.$

$a = 0, b = 4 \rightarrow S = 4, T = 4.$

$a = 1, b = 1 \rightarrow S = 2, T = 2.$

$a = 1, b = 2 \rightarrow S = 3, T = 3.$

$a = 1, b = 3 \rightarrow S = 3, T = 4.$

$a = 1, b = 4 \rightarrow S = 5, T = 5.$

$a = 2, b = 2 \rightarrow S = 4, T = 4.$

$a = 2, b = 3 \rightarrow S = 4, T = 5.$

$a = 2, b = 4 \rightarrow S = 5, T = 6.$

$a = 3, b = 3 \rightarrow S = 6, T = 6.$

$a = 3, b = 4 \rightarrow S = 6, T = 7.$

$a = 4, b = 4 \rightarrow S = 6, T = 8.$

Thus, we have proved for all x and y in the range $[0, 1)$, \[[5x] + [5y] = T \ge S \ge [3x + y] + [3y + x].\]

Now, we prove the lemma statement without restrictions on x and y. Let $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

\[[5[x] + 5\{x\}] + [5[y] + 5\{y\}] \ge [x] + [y] + [3[x] + 3\{x\} + [y] + \{y\}] + [3[y] + 3\{y\} + [x] + \{x\}].\]

But, because $[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

\[[5\{x\}] + [5\{y\}] \ge [3\{x\} + \{y\}] + [3\{y\} + \{x\}],\]

which we have already proved (as $0 \le \{x\}, \{y\} < 1$). 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 $p$. We have to prove the exponent of $p$ in

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

is non-negative, or equivalently that \[\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).\]

But, the left-hand side minus the right-hand side of this inequality is \[\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),\] which is the sum of non-negative terms by the Lemma. Thus, the inequality is proved, and so, by considering all primes $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 (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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_1&oldid=220219"