Alright, so we want to relate something all the way on the bottom to the single number on the top. Wahh? Hm... we're not going to get anywhere by taking the case head on. I mean, is a boring number. As always, with counting problems, start with Let the numbers on the bottom be What is the number on the top in terms of these letters?

If you followed through with my hint, you'll realize that in terms of the bottom numbers, the top number is I won't get down to the rigor, but this is a fantastic discovery!

In fact, the top number for is which we want to take the of, which turns out to be Lovely, all the middle terms cancel out because they're multiples of . Since each of these four numbers are or , we either have
in which case we have just way, or in which case we have ways.

But how about the other numbers? They can be whatever they want, for a total of ways! So the answer is

As always, be ready to explore on the AIME.

Honestly, the majority of trig-identity problems on the AIME qualifies as number 4 on my top 5 favorites. Each question teaches you a new trick (which, unfortunately, pretty much ran out these days so there're less trig problems nowadays). This question is just to give an idea of how awesome trig problems are and how fun they are to play with.

In this particular case, the set up makes things like sum-to-product impossible (tried it), and the summations make top and bottom cancellation pretty much impossible. However, the identity seems fun to play with. Play around!

So the summation becomes Aha! We've found a way to rewrite the ugly cos summation in this way. We have an equation!

For some reason these years there have been quite a lot of sequence problems late in the AIME (I don't recall ever seeing one that's pre-2000???), and most of them have involved some kind of wicked observation, which, although sometimes obscure, are what makes these problems awesome.

For this particular question, nothing jumped out to me. I was tempted to think it may involve the pythagorean theorem because of the square root because it's a pretty renowned trick by now -- see 2006 II #15, 1991 #15, for example. But the in it doesn't make any sense. The next thing to try is some kind of trig substitution, and in this case it's utilizing the identity

Rewrite and let Making the substitution,

This looks much better. Now about the trig substitution... aha! The and s remind us of a triangle! We can picture such a right triangle and define and Similarly, define


Yes! Don't forget the . Remember that when is in , we must take the negative root of This is important!

This is an amazing discovery. Let's walk through the remaining steps carefully (be very careful with the signs). Since is , we take to be positive, so Similarly, How big is Well so , we can keep adding to get

But so and hence we have to subtract in our next move, so Aha! When in , is even, we get and when is odd. So

When I looked at this I forgot about the ...

This has got be the NT problem, and I don't think any other question comes close in terms of effectively using elementary number theory skills to solve a hard problem.

Motivation:

I assume you already set up the equations

or something of the sorts?

Our goal is to learn as much as we can about . The second equation doesn't tell us much for now. You may think of substituting it in, but nothing clever comes out of it (no nice factorizing, etc.), so we start with the quadratic in . This is a lovely trick. When you're dealing with a diophantine equation in a quadratic, the discriminant has to be a perfect square.

Alright, so by the discriminant, is a perfect square. We'll like to use this fact, but doesn't tell us a whole lot. Well, we do know that two consecutive odd integers are relatively prime (Euclidean algorithm), so we can start trial and error. But hey, we haven't used the second equation yet! Let's substitute it in.

We can factor it into , which gives us much more info.

Now we would like to give us a factor of (since a mod check shows can't be divisible by ), so we let
Remember, the latter two factors are relatively prime, and yet they, when put together, form a perfect square. But divisors of perfect squares come in pairs, so we know that these two must each be relatively prime perfect squares themselves.

Let's work with the first guy.


The first factor is smaller than the second, and they must have the same parity. The only possibilities are which yields However, the second ordered pair doesn't work as will no longer be a perfect square.

Remember that and Solving, we get So the answer is .

Beautiful problem. I wasn't able to solve it... darn I really need to take the Interm NT class this summer.