USAMO 1972 - Combinatorics

This one was from the very first USA Math Olympiad. I thought it was rather easy compared to the other ones on the test, which goes to support the conjecture that, being the very first exam the problem writers had to create, they had trouble establishing a difficulty level. Anyway, here it is:

A random number selector can only select one of the nine integers 1, 2, ..., 9, and it makes these selections with equal probability. Determine the probability that after selections (1" class="latex" style="vertical-align: -1px;">), the product of the numbers selected will be divisible by 10. (USAMO '72)

I stole those latex images from AoPS, teehee. Hopefully they don't mind.

Anyway, we want the probability that after n selections, we have at least one factor of 2 and at least one factor of 5. So, just to clarify, we want at least one number of each set:

{2, 4, 6, 8} , {5}

The "at least" should be the tip off that instead you'll count the complement and subtract from the total number, which is 9^n . In case you couldn't tell, I'm just going for the counting approach.

Call the sets the (E)ven set and the (F)ive set. Or E and F for short. We want to count the number of sequences {a_n} such that it has either no elements of E or no elements of F. We can easily count these using PIE.

The number of sequences which have no elements of F is 8^n.
The number of sequences which have no elements of E is 5^n.

However, we overcounted the number of sequences which have neither elements of E or F, as it appears in both of our previous two sequences. Thus, we subtract it once.

The number of sequences which have no elements of E AND no elements of F is 4^n.

Thus, the total number of sequences such that the sequence does not contain an element from both sets E and F is 5^n + 8^n - 4^n.

We subtract this from our total number, 9^n. Thus, the total number of sequences with at least one element from both E and F is:

9^n - 5^n - 8^n + 4^n.

We divide this by the total number, 9^n, to get our probability, which is:

1 - (5/9)^n - (8/9)^n + (4/9)^n

Intermediate Olympiad - Polynomials

Find all polynomials P(x) with the following property:

There exists a positive integer k such that:

P(P(x)) = [P(x)]^k


Good stuff. Anyway, you can easily discover some quick things by plugging in basic values of x.

Suppose r is a root of P(x) then, obviously, P(r) = 0

And, P(P(r)) = [P(r)]^k

P(P(0)) = 0^k = 0

P(0) = 0

Similarly, plugging in any root of P(x) yields that P(P(r)) = 0. Thus, all roots of P(x) are roots of P(P(x)). or:

P(P(r)) = P(r) = 0

P(P(r)) will equal 0 when P(r) is a root of P(x), or

P(r_1) = r_2

Since P(r_1) = o, we have:

r_2 = 0, for any root of P(x).

Thus, all roots of P(x) are 0., P(x) = cx^k for some k. Plugging this into our equation quickly yields c = 1, and thus, P(x) = x^k for all positive integers k.

Olympiad - Polynomials

This one doesn't need latex and the solution is quick (I literally did it while going to the bathroom and reading Samurai Champloo at the same time) so I'll just type it up now.

(Canada 1970) Let P(x) be a polynomial with integral coefficients. Suppose that there exist four distinct integers a, b, c, d with P(a) = P(b) = P(c) = P(d) = 5. Prove that there is no integer k with P(k) = 8.

Kind of scary looking, but it's really not. We can say that P(x) -5 has 4 distinct integral roots, or:

P(x) - 5 = Q(x)(x-a)(x-b)(x-c)(x-d) = 0

Hopefully I don't need to explain that part to you. Now, suppose that there exists an integer k such that P(k) = 8, then we have the result:

P(x) - 8 = ((P(x) - 5) - 3 = Q(x)(x-a)(x-b)(x-c)(x-d) - 3 = 0

Q(x)(x-a)(x-b)(x-c)(x-d) = 3


Since all of (x-a), (x-b), (x-c), (x-d) are distinct and integers, then our assumed result is impossible. As only one can be 3, and the rest must be either 1 or -1. However, we have 4 roots, and thus, one of these three choices for numbers must occur twice, contradicting that the integers are distinct.

Redefining polynomials is a useful tool.

USAMO 1983 - Inequalities

Maybe I'm getting better. Maybe I picked out an easy one. Maybe the aura from visiting MIT today hasn't rubbed off yet (happiest place ever btw). Whatever the case, I managed to do an old USAMO problem today, with the help of ACoPS's compilation of obscure inequalities:



We want information about the roots, so it'll help to use our basic polynomial rules to rewrite a and b in terms of the roots. Let these roots be F, G, H, J, K:



Sorry if that last image is hard to read at the end. Try doing view image or something like that.

From now on, we'll simply be interpreting the inequality with these substitutions made. Also, I'm going to use that cyclic sum symbol consistently, because it's much easier than writing it all out.

We need to show that if the inequality is satisfied, then the roots which are represented in it cannot all be real. So our strategy will be to assume the inequality is satisfied as a given, and that all the roots are real, and attempt to find a contradiction. When we find one, then it will imply that one of our assumptions was false. Since we're operating under the pretense that our inequality is true, then our assumption about all the roots being real will be false.

With substitutions made, our inequality is:



Here it helps to know how to square expressions in the form (a + b + c + ....) quickly.

By the way, looking at that, I realize that it's a little hard to follow because it's cramped / ugly. So I recommend writing it out yourself.

Now we can start using well known (well, maybe not well known...) inequalities to find a contradiction. We know from Chebyshev's Inequliaty (WTF! Yes, I'll comment on the obscureness of this later) that:




For sequences of real numbers {a_n} and {b_n} that are "monotonic in the same direction". Or in other words, increasing or decreasing.

This works well for our roots, as since we're assuming they're real, we can, WLOG, arrange them in increasing order and apply Chebyshev's. Let {a_n} be our roots, and let {b_n} ALSO be our roots. Then we get the inequality (after multiplying both sides by 25, which I'll skip right over):





If you line this up with our assumed inequality, then it DIRECTLY contradicts it. Thus, we have our contradiction, and our proof is done.

It's possible to do this with AM-GM too, I believe. And I'm not 100% sure that my solution works, as I have nobody to check it with. However, I found the Chebyshev's solution first, and there doesn't appear to be anything wrong with it. Perhaps I'll outline that method later.

As for the obscureness of Chebyshev's...the only reason I used it was that I was using ACoPS while I was doing the problem, and I tried it and it worked. You don't need to know lots of random inequalities to do good on the USAMO (at least, I hope not). However, you should at least know the basics: AM-GM, the general Mean Inequality, and Cauchy-Schwarz inequality. It might help to know Chebyshev's, but get the basics down first.

What is this blog?

My original post got buried a long time ago, and the explanation in it was less than vague, so I'll try to go into more detail here.

If it wasn't already obvious, this is a cheap little blog where I post interesting math problems, pretty much all of which are contest problems. I try to write the solutions so that they're easy to follow along with, but at the same time they assume that you're familiar with the math needed to solve them.

I write as if I'm trying to explain problems to an audience. However, I hardly share this blog with anyone who would actually read the problems in a way that they were trying to understand them. So then, why bother writing in this way?

Two reasons (there's actually also a third reason that recently became apparent) :
1) They say that if you can't teach something, then you don't understand it. And vise versa. Technically, I'm not actually teaching anyone anything. But by forcing myself to write up these problems in a way that I'm actually explaining them, I can make sure that I truly understand them. But then again, sometimes I only type up problems which I already know I understand, so maybe I'm wasting my time. T_T
2) This is kind of odd, but someday I might want to be a teacher. Now that I think about it, I would probably get frustrated with stupid kids and only want the cream of the crop, so maybe it's not the best choice for me. But if I decide to go down that path, I'll have a little bit of experience teaching a ghost classroom via blog posts.
3) I've recently gotten awfully good at math (obviously I'm not at the IMO level, but I still think I'm pretty good). However, this sudden surge was after the last AMC date, and seeing as I'm in my senior year now, the next AMC's might not be in time for colleges to look at. So this sort of doubles as a way for me to show off my progress.

But, for you, the (non existant T_T) reader, this doesn't have much to do with you. So if you're interested, just go through some of the problems, and maybe you'll learn something!

AMC - Basic Equations

This is one of those ones where some of your variables have certain restrictions, so you can use that to intuitively find the answer.



So we have:

1/4 m + 1/6 c = 8
m + c = 8p

We know that p has to be an integer, and m, c, p are all positive. We can get each in terms of p:

P = 6 - 1/16 m = 4 + 1/24 c

Since m c and p are positive, and P is an integer, we can see that P > 4 and P < 6 . Thus, P = 5. In fact, we could also find out that there are 16 ounces of milk and 24 ounces of coffee, too. Nice! Easy like sunday morningggggg.

No political talk from me. I can't vote, and it has nothing to do with competition math. =D