If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

# 2003 AIME II problem 13

Probability of moving to a vertex. Created by Sal Khan.

## Want to join the conversation?

• What does "Relatively prime" mean?
• Prime numbers are numbers with no common factors.
(1 vote)
• I had a different way of solving it. Consider moving in a rightward direction as R and a leftward direction as L. Then, each move is reduced to R or L. In order to end up back on the initial vertex, there are three possibilities. The bug could move 5 Rs and 5 Ls, it could move 8Rs and 2 Ls, or it could move 8Ls and 2 Rs (the 8 comes from moving around the triangle a full circle). Therefore, the answer is (10C5 + 10C2 + 10C2)/2^10. this gives 171/512
• So if you think of R's as +1, and L's as -1. 8 R's minus 2 L's would give a total of six moves in the right direction. Therefore, the bug would have gone back to the start position in a full circle since 6 is divisible by 3. I actually like this solution much more, it simplifies the problem and can be done in a fraction of the time.
• 5 sec solution: by symmetry answer should be very close to 1/3... 512/3 is about 171. And our answer is 171/512.
• 5 sec solution: by symmetry answer should be very close to 1/3... 512/3 is about 171. And our answer is 171/512.
• Finding the numerator using his method is effective because you're only trying to find the 10th move. If you were solving the same problem but for a much later move, say the 52nd move, couldn't we just take the denominator (using powers of two), then round it to the nearest multiple of 3 and divide by 3 to find the numerator?
• I don't understand why you multiply by 1/2 to the probability of b and then a. What rule allows him to do this. How does he know to do this. Can someone break down this rule to me please. Thanks!
(1 vote)
• Another way is to derive the recurrence, and then listing it our. It takes away a lot of Sal's thinking and substitutes it for pure and simple computation.

P_n=1/2(1-P_{n-1}). P_0=1
(1 vote)
• Add me as ur students, my email, leefely@rocketmail.com.

Thank you very much ! :) :)
(1 vote)
• Why do you times by 1/2.
(1 vote)
• During turn 2 you can reach A from vertex B or C, but not by both at the same time. Since the probability of reaching B or C can be different, you take half of the probability of reaching B and half of the probability of reaching C. This is the same as adding the probabilities and dividing by 2.

One thing Sal explains but doesn't write is during turn 2. If you end up at B then you would take 1/2 the probablity of reaching A during the previous turn and add that to 1/2 the probability of reaching C during the previous turn. Under turn 2 ending up at B you could write that as (0 + 1/2) / 2, since you are including the previous probabilities of reaching A (0) and C (1/2).
• Another way of doing this is
to create a probability matrix which tells us the probability of going from A to B etc in 1 move. I.e the matrix would be 3x3 and look like:
0 0.5 0.5 Here the i,j th entry represents the probability of going from i to j
0.5 0 0 So label the rows and columns A,B,C
0.5 0.5 0.5

Then, you power this matrix up to the power of 10. The entries in the resultant matrix will give you the probabitlies of A->B in 10 moves, A->C in ten moves etc.