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

Revision as of 22:52, 10 July 2015

Problem

The symbols $(a,b,\ldots,g)$ and $[a,b,\ldots, g]$ denote the greatest common divisor and least common multiple, respectively, of the positive integers $a,b,\ldots, g$ . For example, $(3,6,18)=3$ and $[6,15]=30$ . Prove that

$\frac{[a,b,c]^2}{[a,b][b,c][c,a]}=\frac{(a,b,c)^2}{(a,b)(b,c)(c,a)}$ .

Solutions

Solution 1

As all of the values in the given equation are positive, we can invert it to get an equivalent equation:

$\frac{[a,b][b,c][c,a]}{[a,b,c]^2}=\frac{(a,b)(b,c)(c,a)}{(a,b,c)^2}$ .

We will now prove that both sides are equal, and that they are integers.

Consider an arbitrary prime $p$ . Let $p^\alpha$ , $p^\beta$ , and $p^\gamma$ be the greatest powers of $p$ that divide $a$ , $b$ , and $c$ . WLOG let $\alpha \leq \beta \leq \gamma$ .

We can now, for each of the expressions in our equation, easily determine the largest power of $p$ that divides it. In this way we will find that the largest power of $p$ that divides the left hand side is $\beta+\gamma+\gamma-2\gamma = \beta$ , and the largest power of $p$ that divides the right hand side is $\alpha + \beta + \alpha - 2\alpha = \beta$ . $\blacksquare$

Solution 2

Let $p = (a, b, c)$ , $pq = (a, b)$ , $pr = (b, c)$ , and $ps = (c, a)$ . Then it follows that $q, r, s$ are pairwise coprime and $a = pqsa'$ , $b = pqrb'$ , and $c = prsc'$ , with $a', b', c'$ pairwise coprime as well. Then, we wish to show $\frac{(pqrsa'b'c')^2}{(pqrsa'b')(pqrsb'c')(pqrsc'a')} = \frac{p^2}{(pq)(pr)(ps)},$ which can be checked fairly easily.

Solution 3 (very long, but detailed)

Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.

Dividing both sides of the equation by $(a,b,c)^2$ , and then multiplying both sides by $[a,b][b,c][c,a]$ gives us $(\frac{[a,b,c]}{(a,b,c)})^2 = \frac{[a,b][b,c][c,a]}{(a,b)(b,c)(c,a)}.$ Now, we look at the prime factorisations of $a,b,c$ . Let $a=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots,$ $b=2^{y_1}\cdot 3^{y_2}\cdot 5^{y_3}\cdots,$ $c=2^{z_1}\cdot 3^{z_2}\cdot 5^{z_3}\cdots,$ where all of the $x_1, y_1, z_1$ are nonnegative integers (they could be 0). Thus, we have $[a,b,c]=2^{\max(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3)} \cdots$ and $(a,b,c)=2^{\min(x_1,y_1,z_1)} \cdot 3^{\min(x_2,y_2,z_2)} \cdot 5^{\min(x_3,y_3,z_3)} \cdots.$ Now, we see that $(\frac{[a,b,c]}{(a,b,c)}) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.$ Squaring the LHS will just double all the exponents on the RHS.

Also, we have $[a,b]=2^{\max(x_1,y_1)} \cdot 3^{\max(x_2,y_2)} \cdot 5^{\max(x_3,y_3)} \cdots$ . We can also build similar equations for $[b,c],[c,a],(a,b),(b,c)(c,a)$ , using 2 of $x,y,z$ and either the minimum of the exponents or the maximum. We see that when we multiply $[a,b]$ , $[b,c]$ , and $[a,c]$ together, the exponents of the prime factorization will be $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(z_i,x_1)$ , where $i$ is chosen for the $i$ 'th prime. When we multiply $(a,b)$ , $(b,c)$ , and $(a,c)$ together, the exponents of the prime factorization will be $\min(x_i,y_i)+ \min(y_i,z_i)+ \min(z_i,x_1)$ , where $i$ is chosen for the $i$ 'th prime.

Thus, when we divide the former by the latter, we have $\max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))$ . We wish to prove that this is equal to the exponents we got from $([a,b,c]/(a,b,c))^2$ .

In other words, this problem is now down to proving that $2(\max(x_i,y_i,z_i) - \min(x_i,y_i,z_i)) = \max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))$ for any nonnegative integers $x_i, y_i, z_i$ . WLOG, let $x_i \le y_i \le z_i$ . Thus, computing maximums and minimums, this equation turns into $2(z_i - x_i) = y_i + z_i + z_i - x_i - y_i - x_i.$

Finally, canceling out the $y_i$ 's and collecting like terms, we see the RHS is $2z_i - 2x_i$ , which is equal to the LHS. Thus, this equation is true, and we are done. $\square$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 21: / Line 21: @@
 <cmath>\frac{(pqrsa'b'c')^2}{(pqrsa'b')(pqrsb'c')(pqrsc'a')} = \frac{p^2}{(pq)(pr)(ps)},</cmath>
 which can be checked fairly easily.
+===Solution 3 (very long, but detailed)===
+Note: This solution is more of a "bashy" solution, and is easier to think of than the first 2 solutions.
+Dividing both sides of the equation by <math>(a,b,c)^2</math>, and then multiplying both sides by <math>[a,b][b,c][c,a]</math> gives us <cmath>(\frac{[a,b,c]}{(a,b,c)})^2 = \frac{[a,b][b,c][c,a]}{(a,b)(b,c)(c,a)}.</cmath>
+Now, we look at the prime factorisations of <math>a,b,c</math>. Let
+<cmath>a=2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots,</cmath>
+<cmath>b=2^{y_1}\cdot 3^{y_2}\cdot 5^{y_3}\cdots,</cmath>
+<cmath>c=2^{z_1}\cdot 3^{z_2}\cdot 5^{z_3}\cdots,</cmath>
+where all of the <math>x_1, y_1, z_1</math> are nonnegative integers (they could be 0).
+Thus, we have <cmath>[a,b,c]=2^{\max(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3)} \cdots</cmath>
+and <cmath>(a,b,c)=2^{\min(x_1,y_1,z_1)} \cdot 3^{\min(x_2,y_2,z_2)} \cdot 5^{\min(x_3,y_3,z_3)} \cdots.</cmath>
+Now, we see that <math>(\frac{[a,b,c]}{(a,b,c)}) = 2^{\max(x_1,y_1,z_1) - \min(x_1,y_1,z_1)} \cdot 3^{\max(x_2,y_2,z_2) - \min(x_2,y_2,z_2)} \cdot 5^{\max(x_3,y_3,z_3) - \min(x_3,y_3,z_3)} \cdots.</math> Squaring the LHS will just double all the exponents on the RHS.
+Also, we have <math>[a,b]=2^{\max(x_1,y_1)} \cdot 3^{\max(x_2,y_2)} \cdot 5^{\max(x_3,y_3)} \cdots</math>. We can also build similar equations for <math>[b,c],[c,a],(a,b),(b,c)(c,a)</math>, using 2 of <math>x,y,z</math> and either the minimum of the exponents or the maximum.
+We see that when we multiply <math>[a,b]</math>, <math>[b,c]</math>, and <math>[a,c]</math> together, the exponents of the prime factorization will be <math>\max(x_i,y_i)+ \max(y_i,z_i)+ \max(z_i,x_1)</math>, where <math>i</math> is chosen for the <math>i</math>'th prime.
+When we multiply <math>(a,b)</math>, <math>(b,c)</math>, and <math>(a,c)</math> together, the exponents of the prime factorization will be <math>\min(x_i,y_i)+ \min(y_i,z_i)+ \min(z_i,x_1)</math>, where <math>i</math> is chosen for the <math>i</math>'th prime.
+Thus, when we divide the former by the latter, we have <math>\max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))</math>. We wish to prove that this is equal to the exponents we got from <math>([a,b,c]/(a,b,c))^2</math>.
+In other words, this problem is now down to proving that <cmath>2(\max(x_i,y_i,z_i) - \min(x_i,y_i,z_i)) = \max(x_i,y_i)+ \max(y_i,z_i)+ \max(x_i,z_i) - (\min(x_i,y_i)+ \min(y_i,z_i)+ \min(x_i,z_i))</cmath> for any nonnegative integers <math>x_i, y_i, z_i</math>. WLOG, let <math>x_i \le y_i \le z_i</math>. Thus, computing maximums and minimums, this equation turns into <cmath>2(z_i - x_i) = y_i + z_i + z_i - x_i - y_i - x_i.</cmath>
+Finally, canceling out the <math>y_i</math>'s and collecting like terms, we see the RHS is <math>2z_i - 2x_i</math>, which is equal to the LHS. Thus, this equation is true, and we are done. <math>\square</math>
 {{alternate solutions}}

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

Page

Toolbox

Search