1975 USAMO Problems/Problem 1

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. Unknown error_msg)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. Unknown error_msg)a = 0, b = 1 \rightarrow S = 1, T = 1.$$ (Error compiling LaTeX. Unknown error_msg)a = 0, b = 2 \rightarrow S = 2, T = 2.$$ (Error compiling LaTeX. Unknown error_msg)a = 0, b = 3 \rightarrow S = 3, T = 3.$$ (Error compiling LaTeX. Unknown error_msg)a = 0, b = 4 \rightarrow S = 4, T = 4.$$ (Error compiling LaTeX. Unknown error_msg)a = 1, b = 1 \rightarrow S = 2, T = 2.$$ (Error compiling LaTeX. Unknown error_msg)a = 1, b = 2 \rightarrow S = 3, T = 3.$$ (Error compiling LaTeX. Unknown error_msg)a = 1, b = 3 \rightarrow S = 3, T = 4.$$ (Error compiling LaTeX. Unknown error_msg)a = 1, b = 4 \rightarrow S = 5, T = 5.$$ (Error compiling LaTeX. Unknown error_msg)a = 2, b = 2 \rightarrow S = 4, T = 4.$$ (Error compiling LaTeX. Unknown error_msg)a = 2, b = 3 \rightarrow S = 4, T = 5.$$ (Error compiling LaTeX. Unknown error_msg)a = 2, b = 4 \rightarrow S = 5, T = 6.$$ (Error compiling LaTeX. Unknown error_msg)a = 3, b = 3 \rightarrow S = 6, T = 6.$$ (Error compiling LaTeX. Unknown error_msg)a = 3, b = 4 \rightarrow S = 6, T = 7.$$ (Error compiling LaTeX. Unknown error_msg)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. Unknown error_msg)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

But, because$ (Error compiling LaTeX. Unknown error_msg)[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

which we have already proved (as$ (Error compiling LaTeX. Unknown error_msg)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. Unknown error_msg)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. Unknown error_msg)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$

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

Page

Toolbox

Search

1975 USAMO Problems/Problem 1

Contents

Problem

Background Knowledge

Key Lemma

Proof of Key Lemma

See Also