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.

I'm back!

After much moping about the house, I'm finally back in my math groove! Except....now my LaTeX image generator isn't working anymore!!! T_T. Luckily this one doesn't require much latex, so I'll just type it out:
A function f is defined by f(z) = (4+i)z^2 + az + y, where a and y are complex numbers. Given that f(1) and f(i) are both real, what is the minimum value of |a| + |y|?

They also mentioned something about how i^2 = -1. If you didn't know that then I would recommend you close out the browser and go open a middle school math textbook.

So how should we start? I'll tell you something I've noticed. The AMC problems are meant to look intimidating. They really aren't that bad. So we are given that certain values have no imaginary component. This is a clue to split a and y into real and imaginary components:

a := a + bi
y := y + zi

I used := because I mean that we're completely redefining them now.

So lets look at f(1) and f(i):

f(1) = 4 + i + a + bi + y + zi

From this we can conclude that b + z = -1, as we need all the i terms to go away

f(i) = -4 - i + ai - b + yi - z

Again, we conclude that a + y = 1

This is where most people would get stuck. How can we possible find the minimum value of |a| + |y| given this information? Here, I turned to a geometric interpretation using vectors. In AP Physics we've been doing vector component stuff. If you interpret a and y as the x components and b and y and z as the y components, then we get a picture like this:




I thought that would be too big but now it looks too small.

Well anyway, the point is that if we look at the complex numbers as vectors, their x and y components both add up to 1. Well, technically one of them adds up to -1, but it doesn't matter. So the absolute value of each will be the length of each vector added together. However, since we know how their components add up, we know that if we add the vectors together using that silly head to tail method, they go to the point (-1,1). What's the shortest path from 1 point to another? A straight line. The distance from the origin to (-1,1) is the square root of 2. Problem solved!