USAMO 1972 #1

USAMO 1972 #1 July 18, 2009

Posted by lumixedia in Problem-solving.
Tags: contest math, number theory, olympiad math, USAMO, USAMO 1972
trackback

My first post was going to be an introduction to combinatorial game theory, but putting that together would have been rather more complicated than grabbing some USAMO problem and putting up my solution, so of course I chose the path of less resistance. The intro to game theory will come eventually, but in the meantime, here’s the first USAMO problem ever:

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

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

Here is, based on my first instinct when seeing this problem…

My solution. Let ${(a,b,c)=d}$ , ${(a,b)=xd}$ , ${(a,c)=yd}$ , and ${(b,c)=zd}$ where ${x,y,z}$ are integers. We have that ${x,y}$ are relatively prime since otherwise some factor greater than ${1}$ would divide both ${x}$ and ${y}$ and therefore divide all of ${a/d,b/d,c/d}$ , a contradiction. Then we have ${[xd,yd]=xyd}$ ; since ${a}$ is certainly a multiple of ${[xd,yd]}$ we can write ${a=a_1xyd}$ where ${a_1}$ is an integer. Similarly, we conclude that ${x,y,z}$ are pairwise relatively prime and that ${b=b_1xzd}$ and ${c=c_1yzd}$ where ${b_1,c_1}$ are integers.

We have that ${a_1,b_1,c_1}$ are pairwise relatively prime since otherwise some factor greater than ${1}$ would divide (WLOG) both ${a_1}$ and ${b_1}$ and therefore divide both ${a/(xd)}$ and ${b/(xd)}$ , a contradiction. We also have ${(a_1,z)=(b_1,y)=(c_1,x)=1}$ since otherwise we would again have a factor greater than ${1}$ dividing all of ${a/d,b/d,c/d}$ .

Now we can write ${[a,b]=ab_1z=ba_1y=a_1b_1xyzd}$ , since, as we just showed, ${(b_1z,a_1y)=1}$ . Similarly, ${[b,c]=b_1c_1xyzd}$ and ${[a,c]=a_1c_1xyzd}$ . We claim that ${[a,b,c]=a_1b_1c_1xyzd}$ . Clearly ${a_1b_1c_1xyzd}$ is a multiple of ${[a,b,c]}$ ; if it were not ${[a,b,c]}$ , there would be some ${e>1}$ so that

$\displaystyle \frac{a_1b_1c_1xyzd}{e}\cdot\frac{1}{a}=\frac{b_1c_1z}{e}$

$\displaystyle \frac{a_1b_1c_1xyzd}{e}\cdot\frac{1}{b}=\frac{a_1c_1y}{e}$

$\displaystyle \frac{a_1b_1c_1xyzd}{e}\cdot\frac{1}{c}=\frac{a_1b_1x}{e}$

are all integers. But ${(b_1c_1z,a_1c_1y,a_1b_1x)=1}$ since no ${e>1}$ divides any two of ${x,y,z}$ or any two of ${a_1,b_1,c_1}$ , so that in order to divide all of ${b_1c_1z,a_1c_1y,a_1b_1x}$ , we must have ${e}$ divide (WLOG) all of ${c_1,c_1,x}$ , which is impossible since ${(c_1,x)=1}$ . We conclude that ${[a,b,c]=a_1b_1c_1xyzd}$ . Now we have a little quick algebra…

$\displaystyle \frac{[a,b,c]^2}{[a,b][b,c][c,a]}$

$\displaystyle =\frac{(a_1b_1c_1xyzd)^2}{(a_1b_1xyzd)(b_1c_1xyzd)(a_1c_1xyzd)}$

$\displaystyle =\frac{d^2}{xyzd^3}=\frac{d^2}{(xd)(yd)(zd)}$

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

And here is the unsurprisingly quicker, cleverer, and possibly more convincing…

Official solution. For an arbitrary prime ${p}$ , suppose the exponent on ${p}$ in the prime factorization of ${a}$ is ${a'}$ and define ${b',c'}$ similarly. Assume WLOG ${a'\ge b'\ge c'}$ . Take the reciprocal of both sides of the desired equation; then the exponent on ${p}$ in the prime factorization of the LHS is

$\displaystyle -2\max(a',b',c')+\max(a',b')+\max(b',c')+\max(c',a')$

$\displaystyle =-2a'+a'+b'+a'=b'$

while the exponent on ${p}$ in the prime factorization of the RHS is

$\displaystyle -2\min(a',b',c')+\min(a',b')+\min(b',c')+\min(c',a')$

$\displaystyle =-2c'+b'+c'+c'=b'$

so the two sides have the same prime factorization and are therefore equal.

Hmm yeah, modern USAMOs are probably more interesting than the old ones, but consequently posts about them would take longer to write, so whatever.

About these ads

Comments»

1. Qiaochu Yuan - July 18, 2009: The point of the “look at everything mod a prime” strategy when it comes to gcd and lcm problems is that the poset $\mathbb{N}$ under division is a product of a countable number of chains, one for each prime. So there are two symmetries in the problem. The first symmetry is that each of these chains is interchangeable, and the second symmetry is that each of the variables is interchangeable. Taking advantage of both symmetries is what makes the second solution shorter.

Reply
2. lumixedia - July 18, 2009: Interesting. I’m pretty unfamiliar with some language everyone else here takes for granted, so could you clarify these parts of your comment?
~Poset N under division–this means that one element is considered “greater than” another if the second divides the first?
~Chains–is a chain like p, p^2, p^3, etc.?
~Product of said chains–assuming I understood the previous two phrases correctly, this basically makes sense, but how does the formal definition go?
~By symmetry, do you just mean something like that all primes behave the same in this context?

Reply
3. Qiaochu Yuan - July 18, 2009: 1. Yep. Another way to think about it is that the (ordered) monoid $\mathbb{N}$ under multiplication is a direct sum of countable copies of the monoid $\mathbb{N} \cup \{ 0 \}$ under addition, and it inherits the order.

2. Yep. A chain is a totally ordered poset, and $1, p, p^2, ...$ is a chain under divisibility for every prime.

3. The product of two posets $P, Q$ consists of the Cartesian product $P \times Q$ with the ordering $(a, b) \le (c, d)$ if and only if $a \le c, b \le d$ . This is exactly the condition that an integer divides another integer if and only if they divide each other “locally,” i.e. the exponent of a given prime in the prime factorization of the former is always less than or equal to that of the latter.

4. I mean exactly that. When you’re only dealing with multiplicative properties of the integers and you can ignore the additive structure, the primes all behave the same way. It’s a good thing to look for in a number theory problem, since most of what makes number theory hard is the presence of both additive and multiplicative structure (for example, in Diophantine equations).

Reply
Qiaochu Yuan - July 18, 2009: I should also mention that the gcd and lcm operations have names in this more general setup: they’re called meet and join respectively, and they turn $\mathbb{N}$ into a lattice. You might know meet and join under the more familiar names intersection and union, or equivalently AND and OR; these terms occur in studying Boolean lattices, where the underlying poset is that of the subsets of a set under inclusion.

Ultimately, the point of all this jargon is to highlight structural similarities between different lattices. Boolean lattices and, say, the lattice of divisors of a given integer share the property that they are both products of chains; it’s just that in the Boolean case each of these chains has length 2. So one can gain some useful intuition about how gcd and lcm work by using intuition from the Boolean case.

Reply
Akhil Mathew - July 18, 2009: This is an interesting way to think of $\mathbb{N}$ . Is it possible to shorten and/or generalize number-theoretic results using this more abstract approach?

Reply
Qiaochu Yuan - July 19, 2009: The biggest thing looking at poset structure does is clarify the notion of arithmetic function, particularly the central role played by the Mobius function. It turns out that every poset has an associated Mobius function, and the construction of the Mobius function of a Boolean lattice is none other than by inclusion-exclusion. This should make sense if you’ve ever computed the totient function by inclusion-exclusion; the same argument carries through in a very general setting. (Mobius functions are multiplicative under product, so once you’ve computed the Mobius function of a chain you get the Boolean case and the divisibility case with one stone.)

So what is the appropriate generalization of an arithmetic function? It turns out that what you want to look at is (a certain subalgebra of) the incidence algebra of a locally finite poset. The incidence algebra has a distinguished function called the zeta function (which, for $\mathbb{N}$ , is – surprise – the Riemann zeta function), and its inverse, if it exists, is the Mobius function of the poset.

Gian-Carlo Rota popularized the idea that the different types of generating functions that appear in combinatorics are really (reduced) incidence algebras over different posets. For example, ordinary generating functions exist in the incidence algebra of the non-negative integers under the order inherited from $\mathbb{R}$ , and exponential generating functions exist in the incidence algebra of the poset of finite sets under inclusion.

This is some deep stuff. It even turns out that the Mobius function of a poset is related to the Euler characteristic of a certain simplicial complex associated to the poset – in two ways! I don’t understand this connection very well, but it’s fascinating to think about.
4. Akhil Mathew - July 19, 2009: This is very interesting indeed. I was aware that there was a generalization of the Mobius formula of some sort, in a combinatorial way (e.g. the paper I needed to read actually used it, though only in a minor way).

I should probably learn more about combinatorics and abstract analytic number theory to become more familiar with tools such as incidence algebras and (this type of) zeta functions.

Reply
5. lumixedia - July 19, 2009: Wow, thanks for all the information. I need to learn some non-high-school math sometime…I really do.

Reply
6. RSI students blog « Secret Blogging Seminar - July 22, 2009: [...] the representations of . The other half seem to be puzzles and Olympiad problems; for example, this post starts out by talking about the first US Olympiad problem ever, and moves to discussion of lattices [...]

Reply

	malmsteenkoushik on Divisibility theorems for grou…
	tinyurl.com on The tubular neighborhood …
	Advanced Analysis, N… on The Hahn-Banach theorem and tw…
	Gary K on The tubular neighborhood …
	Gary K on The tubular neighborhood …

Delta Epsilons

USAMO 1972 #1 July 18, 2009

Like this:

Comments»

Leave a Reply Cancel reply

About

Mathematical websites

Categories

Recent Posts

Recent Comments

Previous Posts

Tags

Feeds

Follow “Delta Epsilons”