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.

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

Two things coming up soon

1) A USAMO problem. Oooh, scary!

2) I'm going to type up a mini post about what this blog actually is, since my original first post is long since buried beneath everything else.

In the meantime, I have lots of reading that needs to be done for law.

AIME - Number Theory

This is just a quickie I felt like posting, it had a fast solution that I'll just outline.



We can actually do the polynomial division to get the result:



Clearly, the largest integer n for which this is an integer is n = 890. Piece of delicious cake.

AIME - Complex Numbers / Probability

Today everyone was on an NHS field trip (maybe later I'll explain why I'm not in NHS...) and so in most of our classes we didn't really do anything. So I brought in a bunch of old AIME problems to work on. This one caught my attention while my physics teacher started giving a random lecture on economics:



Some of those words are blue because I copied that from the AoPS wiki.

Speaking of the AoPS wiki, I hate some of the solutions they have on there. Mainly because they're hard to follow. I suppose they're just supposed to be general solution outlines, but the one for this was some odd use of a bunch of trig formulas, and it wasn't very nice to look at. I like my solution because once it's explained, the problem becomes rather intuitive.

I interpretted this problem geometrically. It makes it a lot easier to see what's going on. So we have some roots of unity. At this point, I didn't even consider the number 1997. Then we're adding another root of unity to it. If we treat the complex numbers as vectors, then this is just the head-to-tail method. The diagram shows some of the possibilities of this. The dashed circles are all possible roots of unity. I just drew in two possibilities:



The absolute value of this number, which is just its distance from the origin, is greater than that odd square root. In other words, it's outside the circle of that radius. We can sketch that in too to get a better look:



Hmm. If we can visualize sliding that second "unity" circle around the first, the same percentage of it should always be outside that circle that we drew in. That suggests that the probability is independent of the first choice, which certainly makes things easier.

One issue that's worth addressing at this point is whether our approach of throwing away the number 1997 for simplicity has thrown us off course. The same percentage of the circle is always farther from the origin than that silly circle with the square root radius, but we're not looking at the percentage of the circle, we're looking at the number of roots of unity for the number 1997 that lay outside the circle. If we slide that second circle around, there's no guarentee that this will be the same for each. When I did the problem out, I reasoned that it is, because if you draw in all the actual possibilities for a certain number, you can rotate the entire thing by 360 / n degrees, causing each set of possibilties to translate to the next exactly...if that makes sense. I hope it does T_T.

Anyway, we can make this problem easier by only considering the case where u = 1. Since the number of roots outside of that larger circle should be the same for each case, then the probability for all cases will be the same as the probability for one case. Here's an altered diagram for this case:



If we can figure out where they intersect, then we can figure out the range of that arc that is outside the circle, and figure out how many roots lay on it! The equation of each circle is:



We can expand the second equation and substitute the first into it to get:



That familiar sqrt(3)/2 expression is encouraging. What about the +1? Remember that our circle is translated over to the right by +1. So if we consider the center of that circle the origin, then they intersect at x = sqrt(3)/2 = cos(+/- pi/6). Aha, now we have a range! If we let our angle be:



(this is the general angle of a 1997th root of unity)

Then it lies within the range:



Since the floor of 1997 / 12 is 166, then there are 166 positive integers and 166 negative integers in this range. We aren't counting k=0 because this wouldn't be a distinct root. Therefore, we have 332 total roots in this range. We are selecting them from 1996 roots (remember, that root we already picked is off limits), therefore, the probability is:



And our final answer is 499 + 83 = 582.

The lesson learned? When doing a problem with complex numbers, take some time to consider which way it's more profitable to interpret it: algebraically, or geometrically, as complex numbers are essentially a mix between these two topics.


OH. So why aren't I in NHS? Because it's a cult where all they do is struggle to sell crap candy and do random community service for NHS points, the currency of NHS. You gain nothing from joining, besides maybe having an extra activity on your college resume. You lose your soul. Not a great trade in my oppinion. Also, they appreciate kids who stack on the L4 classes more than the kids who actually focus on subject and become really good at it. And their advisor is a stubborn old man too, according to most of my friends in NHS.

Induction

This is a problem that I tried a while ago and got nowhere with. Looking at it again, it seems rather tame and easy. Maybe this is because it was a problem set from the induction lecture, giving a rather large hint as to what to do. Nonetheless, I enjoy whenever this happens because it shows that I'm actually making progress.



Proceed by INDUCTION. LECKE.

Start with n=3. Since the distances to each person are different, we can conclude that they form a scalene triangle. Take the shortest of its lengths - these two people shoot eachother, leaving the third man unsprayed.

Assume its true for n=k, k-2, ..., 3, show its true for n=k+2:

Again, consider the shortest attainable distance. Depending on the positioning of the people, this shortest distance could occur between a number of people. Assume for now that it only occurs once (we'll address this soon enough). These two people shoot each other. Now consider the remaining k people. If any one of them shoots one of these two people, then at least one person will be left dry, as we have k-1 shots left but k people who haven't been sprayed. Thus, we can assume that they form their own little "spraying group", if you will, of k people. Since we already showed that at least one of these people will be left dry, we're done.

Note that if we have more than one of those "shortest distances" then all that happens is that instead of having a group of k people, we would now have a group of k-2, k-4, or something else depending on how many of those there are.

What if, as a result of these shortest distance cases, we are left with a group of only 1 person? Although we didn't prove the base case of n=1, we can just point out that if this occurs, we're left with one dry person, which is enough to prove our claim.

Olympiad Diophantine Equation

This was one of my practice olympiad problems I had to do. It was pretty tough. I struggled with it for most of the time until I got a mediocre solution with a lot of holes in it. However, it was a rewarding experience. You don't learn how to tackle the tough problems unless you actually get engaged with one. I'll be explaining the complete solution.



I forgot to include that m and n are positive btw.

It's pretty intimidating. What's so intimidating about it? For one, the variables in the exponents make the equation funky looking. Second, at first glance, there's absolutely nothing we can do with it. There's nothing to factor. We do notice the square on the right hand side of the equation for it, which I don't show here. Does that suggest a difference of squares? Only if one of m or n are even. Can we show that it is? If we can, it's certainly not intuitive how.

By the way, before I forget, for any Diophantine equation, try playing around with small numbers to see if you can find any solutions. Here, a fairly obvious solution is (4,2), as this yields one side of a Pythagorean triple. Whether or not you can find any solutions will help you understand where you might need to steer your proof. The fact that both m and n are even in this solution suggests even more so that our previous idea is on the right track.

So back to the problem. We have an idea of where to go. Seeing as I don't have any better ideas, it's worth exploring. How do we show that m or n is even? We can start by breaking down the equation using mods. What does this mean? It means we look at the equation under as many mods as we see fit. What sort of mods should jump out right away? 2 and 3 might come in handy later. Because the quadratic residues are so limited mod 4 and 8, it will probably be helpful examining the equation under these. And if you don't know what quadratic residues are, I'll side track to explain them:

How many solutions are there to n = 3 mod 4? Obviously an infinite amount, whenever n is in the form 4m + 3. This is basic modular notation.

How many solutions are there to n^2 = 3 mod 4? Turns out that there are none. How can we show this?

Every number will be congruent to either 0, 1, 2, or 3 mod 4. Therefore, every number in the form n^2 will be congruent to o^2, 1^2, 2^2, or 3^2 mod 4. This table explains it pretty well:





We can take this idea and apply it to a number of different things. The powers of an integer modulo n, cubes modulo n, etc. Lets look at the powers of 2 and 3 modulo 4:




We can show by induction that all odd powers of 3 =3 mod 4, and all even powers =1 mod 4. It's pretty simple to do so I won't bother explaining it. We can make a similar argument for powers of 2 where the exponent is greater than 1, it will be congruent to 0 mod 4.

Since all squares are congruent to 0,1 mod 4, then we only have two cases for our powers of 2 and 3: 2 reduces to 2 mod 4 (or in other words, our power of 2 is 1), and 3 reduces to 3. Or, 2 reduces to 0 mod 4, and 3 reduces to 1. Playing around with smaller numbers for the first case suggests that it won't work out, and we can easily prove it:




We can reduces all squares modulo 3 to find that they're congruent to 0,1 mod 3. However, its easy to see that the expression is always congruent to 2 mod 3.

So we can conclude that n must be even. Let n = 2x. Then we can subtract and factor:




Clearly both factors must be nonegative powers of two. Writing some equations and subtracting them yields:




Taking both sides mod 2 and remembering that x is a positive integer, we see that our power of two must be 1, giving us the equation:




Trying small values of x, we quickly see x = 1 works, meaning n = 2. Putting this back into our original equations, we can determine that m = 4. We now have one solution, (4,2).

If we try values of x larger than 1, it seems as if the RHS of that equation will never be a power of two. Lets try to prove it. We try looking at it modulo 8, because for x > 1, the RHS will always be greater than 8, and since its supposed to be a power of two, must be divisible by 8:



Again we can induct to show that it's always congruent to 3 or 1 modulo 8. And since we're adding 1, the LHS is congruent to 4 or 2 modulo 8. So it'll never be a power of 2 for x > 1. Thus, our only solution is (4,2).

That problem was pretty mind numbing, mainly because of all the modular residues we had to examine. However, it is a great example of how to break down number theory problems using modular arithmetic. To sum everything up, here's my main approach for diophantine equations that don't like immediately solvable by some method:

1) Quickly look for some solutions
2) Look for ways to factor it
3) Examine it under different modulos to narrow down the possibilities of the variables.

Also, here are the general tactics that ACoPS proposes:

- Is the problem in "simple" form? Always make sure that you have divided out all common factors, or assume the variables share no common factors.

-Do there exist solutions? Sometimes you cannot actually solve the equation, but you can show that at least one solution exists.

-Are there no solutions? Quite frequently, this is the first question to ask. As with argument by contradiction, it is sometimes rather easy to prove that an equation has no solutions. It is always worth spending some time on this question when you begin your investigation.
(I'll add here that this is why you should look for some quick solutions first, so you don't get caught up trying to prove that there are no solutions whatsoever)

-Can we find all solutions? Once one solution is found, we try to understand how we can generate more solutions. It is sometimes quite tricky to prove that the solutions found are the complete set.

Oomph. So how are you? I'm visiting WPI tomorrow and monday, I'm planning on visiting RPI in november, and I'm also going to plan a trip to MIT sometime before winter. I'm not as stressed out about it anymore, as I took a step back and realized that once I switch from my retarded french guidance counselor I'll be better off. And now I'm very tired and while I would love to do more math, I have a bunch of tests to study for next week.