Bug on a Triangle (AIME #13)

[Ender]

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is m/n, where m and n are relatively prime positive integers, find m+n.

[Chavo]

I'm not a huge math buff but...relatively prime?  I don't think numbers can be 'relatively' prime unless you are restricting the problem to a closed set and even then it doesn't exactly make a lot of sense to say it :)

[rabbit]

Relatively prime: 10 and 11 are relatively prime because neither divides the other.

[iago]

683?

[Ender]

683?

Correct :D Solution? :P

[iago]

683?

Correct :D Solution? :P

Well, first I captured myself a whole bunch of ants and made a triangle out of sugar. Then...

<edit>
(9:41:33 AM) Nick: if a_i is the probability of landing on the starting spot after 0 moves (i.e. a_0=1, a_1=0)  then a_i+1=(1-a_i)/2
(9:42:39 AM) Nick: or the probability of the current point being not on the starting point (1-a_i)  divided by two since half the time you will land back at the start

I don't know what it means, but is it right? :P

[Ender]

Yep, that works =) That's a nice conceptual shortcut, actually. The way he did it you don't even have to look for a pattern by getting your hands dirty, you just have to evaluate the anchor case and use the logic stated.

I'll explain what he did. Let's say the bug is on its nth move. If the bug got to the starting point on its (n-1)th move (lol @ notation) then it has a zero probability of getting to the starting point on its nth move. So you take the probability that it DIDN'T get to the starting point on the (n-1)th move, which is 1 - a_n-1, which implies that the bug is on one of the two vertices that's not the starting point. In this situation, the bug has two places to move to, and each are equally likely, so you take half the probability, to make it (1 - a_n-1) / 2.

I probably should have used LaTeX on that hehe... I may get around to prettifying it later.

By the way, why doesn't Nick visit these forums? :P (i.e. without the iago proxy ;-))

[iago]

It's more fun for me if I get to be a middleman. He explains his answers to me and I totally don't understand them, it's fun :)

[Ender]

Hehe. >:( Did you get my explanation?

[iago]

It sounds like what he told me. To be honest, I didn't put much thought in it. I just find myself not caring about math problems :P

[rabbit]