Difference between revisions of "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 $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]$.

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 $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 [[\frac{3a+b+4}{5}]] + [[\frac{3b+a+4}{5}]] = S.$$

To prove that $S \le a + b = T$, we shall list cases. Without loss of generality, let $a \le b$. 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} + 3[x] + 3{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 collorary 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 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 $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$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 