THE END

This is my last post on this blog. It stopped supporting LaTeX, so I got annoyed having to manually render + upload pictures. The new blog can be found at:

http://cloudcomplex.wordpress.com.

Once I figure out how, I'll import all these posts over.

AIME Guide - The general math

So you've qualified for AIME - good job! This guide is meant to help you prepare for what will ultimately violate your confidence in your ability to do math. This first part is meant to tell you what you should generally know if you want to do decent on it. I'm going to base this on the AIME class that I took last summer:

Equations:
The type of AIME problems that are, for the most part, just plain old algebra. There's not much more to learn here. The best way to prepare for these is to go through old AIME problems about systems of equations to be familiar with the types of factorizations and substitutions that may be useful.

Complex Numbers and Polynomials:
Besides the basic a+bi notation, you should be familiar with polar representation. Also, you should know Vieta's. Newton Sums would be helpful, but if they actually come up, you can always derive them. (If you don't know what those are, go look them up. =P )
I've found that doing Olympiad problems about polynomials can actually be pretty helpful. So go bust open PSS and ACoPS for preparing for these types of problems.

Functions
Floor function, sine/cosine, logarithms, and just plain old f(x). Solving functional identities can help you be more comfortable with the function problems on the AIME. Also, going through old problems will give you more of an idea of what sort of questions to expect (do you see a pattern yet?).

Inequalities, Optimization Problems, Sequences, and Series:
AM-GM, Arithmetic sums, Geometric sums, recurrences, etc. Know them and know how to use them. Most sequence problems on the AIME will be pretty straight forward. On the other hand, most inequality / optimization problems are, as far as I've seen, pretty tricky. Again, GO THROUGH OLD PROBLEMS.

Counting:
Know your basics is the most important part here. The rest is being clever in how you apply them. Granted, it'll be helpful to know a few tricks, such as balls and urns, seating people such that nobody is next to one another, etc. The hardest counting problems on the AIME will require you to create some sort of recurrence to solve them. OLD PROBLEMS. DO THEM.

Probability:
Most of the probability problems on the AIME will actually just be a mix of counting and some other category. Know your combinatorics, conjugate counting tricks, and geometric probability, and you should do fine with these. Most of the time, the probability problems will appear to be rather tricky. The trick is seeing past this and simplifying it. This is the last time I'll tell you to do old problems. It applies to every category though.

Number Theory:
The category that most AIME qualifiers know nothing about. It's unfortunate; number theory is quite beautiful, and very common on the AIME. Things you should know are modular arithmetic and Diophantine equations. Once you do enough number theory problems, you become familiar with the tricks involved: when it's appropriate to factor (almost always), when its appropriate to expand something out (almost never), things like that.

Trigonometry and Analytic Geometry:
Almost all geometry buffs will tell you to avoid resorting to trig and coordinates to solve geometry problems. However, sometimes it will be clear that you simply need to use coordinates and trig to solve a problem. If they give you ellipses, parabolas, and trig functions in relation to a figure or angle, then its probably safe to reach for these tools. You should be familiar with the basics of coordinate geometry, and all of the trig identities. Most of the time, you'll have to use these tools to create equations, which you can then solve for your desired variable.

Euclidean Geometry:
Arguably the most important part of the AIME. Also arguably everybody's worst subject. I can't possibly list all the crap that falls into this category. The most important thing to be familiar with besides all the basic formulas are similar triangles. They come up a lot, and if you can recognize them and use them, it'll be very helpful.

In another post, I'll go more in depth on a few of these. Here's some nifty music (more MGS4 stuff).

AMC 12

I think I did pretty well. There were two problems that bothered me though:

#15 - I made a really stupid mistake. 6 points down the drain...
#25 - I thought I had it, but turns out that my logic was off. Afterward, I was able to bash it out with a calculator to find the right answer. I'm curious as to what the efficient method is. I did recognize that it was clearly a tangent sum, though. I would've hoped that the answers would give me some "guessing credit," but I "GUESS" not.

I didn't answer 23 or 24 because they stumped me. xD

Everything else, I'm pretty sure that I got right. So my score should come to a 129, more than enough to make AIME. Hopefully, it'll be enough to help me make USAMO later.

Here's the coolest video on my mind right now:

AMC is coming up

It's a scary moment. If I screw it up, then it basically means I've wasted the past year. So this weekend has been reserved for review and AMC problems. But I couldn't live with myself if I didn't keep in contact with you people....>.>......so here's one I did recently:

Let be a trapezoid with and . Bisectors of and meet at , and bisectors of and meet at . What is the area of hexagon ? (AMC 12B 2008)

This one actually annoyed me, but I think that if you can learn how to do it correctly, then it'll help tremendously with cutting down on mistakes and such. It requires a good amount of calculations. Lots of Pythagorean Theorem with square roots. Throw that on top of the 2008 AMC being a no calculator exam, and you've got yourself a lot of paper work. If you're reading this and would actually like to learn from it, I recommend that you go through the entire problem in a very neat manner.

Anyway, the first thing is to draw a diagram. I don't have time to draw a digital one for you (sorry!), so draw it yourself =P. Here is where drawing a good diagram is crucial. Granted, it doesn't have to be perfect. In fact, all you need to do here to guarantee that you see what needs to be seen is that you draw AB and CD parallel, and draw good estimations of the angle bisectors. But if you don't, then you might miss the important observation that blows the problem away.

So, if it wasn't obvious, it should pop out that AP is perpendicular to DP, and the same with the angle bisectors from B and C. If this were true, then it would be an exercise in calculation to bash out the math leading to the answer. The steps would look something as follows:

Find the length of the height of the trapezoid.
Draw heights from A and B, and find how far the foot of each is from C and D.
Extend AP and BQ to make triangles on each side of the trapezoid.
Using the idea that the angle bisectors are perpendicular to each other, draw in some right triangles (actually, by this point, all you need should already be drawn in), and bash out the Pythagorean Theorem until you find enough information to find the areas of the triangles that are cut out of the trapezoid.

So if we can prove our conjecture, then we'll have basically solved the problem. It turns out that since A+D = 180 (AB is parallel to CD), then 1/2 A + 1/2 B = 90. Marking these angles, it shows that the angle of intersection between the bisectors is a right angle. If you were confident in your conjecture, or just didn't know how to prove it, then you could plow ahead with the problem anyway, as long as the calculations don't throw you off.

I'm not going to go through all the math for it, but I'm going to list out the "categories" that people might fall into when attempting this problem:

1) Looked, and didn't attempt:

Only do this if you're slow and want to guarantee that you get, say, the first 20 right. A good strategy for making AIME, but not really a good strategy for making USAMO. I'm going to assume that you want to make USAMO and won't have too much trouble with the first 20.

2)Looked, drew a diagram, and didn't know where to go with it:

Either your diagram was crap (it only takes 20 seconds to draw a decent diagram!), or your strategy for attacking is was poor. With geometry problems, it's important to use all the information that they give you. Something that I like to do is take what they give me, and for each one, list at least one thing that it would imply, even if it's obvious. It helps to get you going if you're stuck. Here, if you draw a decent diagram, you may not have even had to do this.

3)Looked, drew a diagram, conjectured / proved that the bisectors are perpendicular, and then didn't know where to go:

I'm guessing that this is where most 100-120 scorers would fall, which is unfortunate, because at this point, the hard part is done! They may draw in some altitudes and find some more lengths, but then get lost in their own work. Here, organization is especially important. Some tips are:

For a messy problem like this, keep your diagram seperate from your work. When calculating certain parts of the diagram, keep your work clean, write it as if you were going to hand it in, and when you get to it, box the final answer, along with what value it is. This makes it easy to refer to for later calculations. Some might argue that this takes too much time, but I usually find myself with left over time at the end if I can't get some of the problems. Don't waste time at the end, put it to good use during the exam.

When labeling your diagram, do so only if it makes the next step easier to visualize. For example, you have a number of connected right triangles, and you are going to do a Pythagorean combo, where you move from one triangle to another. Otherwise, it's just taking up room and making the diagram harder to read.

Don't get too happy drawing in extra lines. Only draw them if you have reason to believe that they might help. Example: drawing in a certain altitude that you know how to calculate, and which forms another right triangle with a side length that you need to find.

I don't really have anything else to say about this problem. It's a good excercise in work habits and basic problem solving. There might be a more clever way to do it in less time. However, assuming that you noticed the bisectors were perpendicular within 1 minute of drawing the diagram, then the rest of the calculations shouldn't take you more than 5-10 minutes. Hopefully you didn't take more than 3 minutes on any of the earlier ones =P.

Anyway, I'm doing pretty good. Second semester has been easy so far, I've taken up chess again and restarted Chess Club at my school, and I finally got a hair straightener. Good stuff. Here's some music that I've been listening to:

Braaaains....

No, I didn't die. I haven't posted on here for a while because I've been pretty busy with things.
Some of them have been negative:

Power outages
Seasonal depression
Stressing out about college applications
Seasonal depression
Studying for midterms and finishing up semester projects
Seasonal depression

Some of them have been positive:

Trying to advertise chess club to people
Trying to get back into drawing
Attempting to learn Mandarin because of Kay peer pressuring me.
Enjoying the HDTV and PS3 that we (my family) all pitched in to get for Christmas.
Treating myself by having a social life.

That last one is actually all that it's hyped up to be, despite what shut-ins like to believe. Sorry, Chao. xD

Anyway, I owe you a math problem, so here:

Aime 2005b, #6

---

The cards in a stack of cards are numbered consecutively from through from top to bottom. The top cards are removed, kept in order, and form pile . The remaining cards form pile . The cards are then restacked by taking cards alternately from the tops of pile and , respectively. In this process, card number becomes the bottom card of the new stack, card number is on top of this card, and so on, until piles and are exhausted. If, after the restacking process, at least one card from each pile occupies the same position that it occupied in the original stack, the stack is named magical. Find the number of cards in the magical stack in which card number retains its original position.

Start by "listing" the cards from top to bottom, to help visualize it:

1
2
3
...
2n

Now, the two piles look like this:

A--------- B

1 ------- n+1
2 ------- n+2
3 ------- n+3
... ............ .......
n -------- 2n

Using the method described above, we can mix them to get the new pile. You may need to work backwards a bit if you want to build it from top to bottom, but it's really nothing hard:

n
2n
n-1
2n-1
....
1
n+1

Now we'll generalize that a certain card is in the same position as the original pile. Again, to visualize, let's line the two up:

n ------- 1
2n ------ 2
n-1 ---- 3
2n-1 --- 4
.... .............
1 --- 2n-1
n+1 -- 2n

There is a very clear pattern here. If you don't see it, then see what this looks like when you only consider the odd numbered cards:

1 ----- n
3 ---- n-1
5 ---- n-2
7 ---- n-3
... ..............
2n-5 --- 3
2n-3 --- 2
2n-1 --- 1

We're looking at the odd numbered cards since our desired card, 131, is odd. If we can make a formula for the xth card up in each column, we can set them equal to 131.

For the first column, this is 2n - (2x - 1)
For the second column, this is x

2n - 2x + 1 = x = 131
2n + 1 = 3x = (131 * 3) = 393
2n = 392

Indeed, 2n is the number of cards in the pile, so our answer is 392.

I find this problem interesting, because you hardly need any math to do it. You just need some logic and some courage to actually try working with it.

On a side note, I very much like this song:

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.