AIME II #11 2006

[stupidityismygam]

A sequence is defined as follows [unparseable or potentially dangerous latex formula] and, for all positive integers [unparseable or potentially dangerous latex formula] Given that [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] find the remainder when [unparseable or potentially dangerous latex formula] is divided by [unparseable or potentially dangerous latex formula]

[mathslug]

I've simplified this problem somewhat, but I'm not sure if I've gone as far as one should go on an AIME problem.

At a glance, the problem wants us to sum the first 28 terms and take the remainder by 1000. That's cool and all, but its kinda tedious. Let's see if we can cut down on the arithmetic with some logic. Let's make use of the recursive rule.

Instead of adding a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 ... + a28, lets do:

SUM = 2(a4+a8+a12+a16+a20+a24+a28)

since a1+a2+a3=a4, a5+a6+a7=a8, etc...

To make this problem even easier, we need relationships between the terms. Lets take a look at terms a28, a29, and a30

a28 = a27 + a26 + a25
a29 = a28 + a27 + a26
a30 = a29 + a28 + a27

from this, we can derive
a30 = 2(a25) + 3(a26) + 4(a27)

Now let's use this formula we've just derived and apply it to a29, so that we can get a relationship between a28 and a24.

a29 = 2(a24) + 3(a25) + 4(a26) --> substitute a28 + a27 + a26 for a29, and we get:

a28 = 2(a24) + 3(a25) + 3(a26) -a27 --> add 4(a27) to both sides and substitute in a28:

a28 + 4(a27) = 2(a24) + 3(a28) --> The time saving eq! --> a24 + a28 = 2(a27)

This can be applied our earlier eq, and we get that the sum = 2(a4+2(a11)+2(a19)+2(a27))

I've searched for easier ways to get at a11 and a19, but the only way I could find was following the formula until I got there... : /

So the sum = 2(3+2*193+2*281+2*233) = 1417*2 = 2834 --> 834.

The answer should be 834.

Zack

[stupidityismygam]

yeah, good job!

there is a more efficient solution, it isnt mine but ill post it so that you can see it

Let [unparseable or potentially dangerous latex formula]

Now multiply this by 3,
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]

So, [unparseable or potentially dangerous latex formula]

And the rest is history

(note one simplification comes from the fact a_1=a_2=a_3)
(note latex was acting up...so my formatting # at best)