Main content
Course: Math for fun and glory > Unit 4
Lesson 1: 2003 AIME- 2003 AIME II problem 1
- 2003 AIME II problem 3
- Sum of factors of 27000
- Sum of factors 2
- 2003 AIME II problem 4 (part 1)
- 2003 AIME II problem 4 (part 2)
- 2003 AIME II problem 5
- 2003 AIME II problem 5 minor correction
- Area circumradius formula proof
- 2003 AIME II problem 6
- 2003 AIME II problem 7
- 2003 AIME II problem 8
- Sum of polynomial roots (proof)
- Sum of squares of polynomial roots
- 2003 AIME II problem 9
- 2003 AIME II problem 10
- Trig challenge problem: area of a triangle
- 2003 AIME II problem 12
- 2003 AIME II problem 13
- Trig challenge problem: area of a hexagon
- 2003 AIME II problem 15 (part 1)
- 2003 AIME II problem 15 (part 2)
- 2003 AIME II problem 15 (part 3)
© 2024 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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?(15 votes)
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(20 votes)
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.(6 votes)
5 sec solution: by symmetry answer should be very close to 1/3... 512/3 is about 171. And our answer is 171/512.(2 votes)- 5 sec solution: by symmetry answer should be very close to 1/3... 512/3 is about 171. And our answer is 171/512.(2 votes)
- 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?(2 votes)
- 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).(0 votes)
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.(0 votes)- this is similar what sal did, just more formal(1 vote)
Video transcript
A bug starts at a vertex of an equilateral traingle. 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 So this lesson right here where m and n are relatively prime positive integers essentially says we have the positive version of this fraction in its simplified form So let's just think about the problem we have an equilateral triangle here with three vertices A B and C and our bug is going to start at lets say vertex A So this is our bug right here and on each move it will randomly select one fo the two vertices So on its first move it will either go to vertex B or then vertex C and then depending on whether it went there If it went to vertex C then on it's next move it wil either go to vertex B or vertex A if it went to vertex B on its next move it will either go to vertex A or vertex C So let's just think about it. We want to figure out the probability of it moving to vertex a on its tenth move So let's just think about what happened in each move. The probability of moving toward on of the vertices in a given move So let us say that we have move 1 over here in this column so we have vertex A,B and C so let's think about move one On move 1 what's the probablilty of moving to vertex A Well you are already on vertex A and it says that the insect in going to go to one of the other 2 vertices So the probability on move one of moving to vertex A is 0 What's the probablilty of moving to vertex B? Well it is going to be 1/2 what's the probablilty of moving to vertex C? It's going to be 1/2 as well half a chance of going there and half a chance fo going there Well obviously all of the probabilities have to add up to 1 because it's going to do something on that move. Now let us think about move 2 So what is the probability of now moving to vertex A? Well there is a 1/2 chance that we are already at B. If we were already at B there will now be a 1/2 chance of moving back to A So this is 1/2 times 1/2 that's only the situation if we were already at B. If we were already at C then there would also be a 1/2 probability of moving to A So this is going be the 1/2 chance that we were already at C times the probability that we move to A So 1/2 times 1/2 = 1/4 + 1/2 times 1/2 = 1/2 So what is the probability of moving to B in the second turn? Now the only place other than B that the bug can move to is C in the second turn. This is because we know that at the end of the first turn the bug will not be at A It will either be at B or C If the bug is already at B there is no way that it will go back to B So the only situation is if the bug is already at C there is a 1/2 chance of that happening so that is this number right here. So if the bug is already at C and that is the 1/2 probablility then there is going to be a further 1/2 probability that it moves to B So it is going to be 1/2 times 1/2 = 1/4 Now what is the probability of moving to C? Well it is the same logic. The bug is not going to be on vertex A after the first move there is a 1/2 probability that it is going to be at B; and then if it is at B then there is a 1/2 probability that it will go to C So this is going to be 1/4 as well In general let's say that in move N the probablility of being at vertex A is the probability of A The probability of being at vertex B is probability of landing on B at move N and the probability of C is Probability of moving ot vertex C on move N Now let us think of the probability of being at each of these nodes on N+1 So in order to get to A on move n+1, you either have to be at B or C. You cannot be at A and stay at A So the probability of moving to A in your n+1th move is going to be the probability of being at B times 1/2 (right because if you are at B there is a one half chance that you are going to go to A) + the probability of being at C at the end of your last move times 1/2 There is a half chance that if you are at C you will move to A. There is a half chance that if you are at C you will move to A. Now what's the probability of going to B? Well there are two ways that will get ot you B. You can start at A so you are going to start at A So the probablilty of being at A times 1/2 or you could start at C. So it's plus the probability at C times 1/2 If you were doing this problem in a situation that had time constraints you would not neccesarily have to go through this, but I just want ot make it all clear. And finally what is the probability of landing in C at you n+1th term It's going to be the probability of being at A times 1/2 + the probability of being at B times 1/2 So hopefully this makes the pattern of what is happening little bit clearer So no matter what A is going to be the average. A in the next move is essentially going to be the average the probabilities of being at B and C And you can see that. The average of 1/2 and 1/2 is 1/2 The probability of being at B in the n+1th move is going to be the average of the probabilities of being at A and C in the last move the average of 0 and 1/2 is 1/4 and the same logic for C. The average for 0 and 1/2 is 1/4 Now that will help me simplify things a little bit more for our brains Let's keep going this way and let me continue the columns Rows A,B and C and now we are on move 3. I am just continuing it down here So what is the probability of the move being A in move 3 Well we just said it's going to be the average of B and C and B and C is 1/4 So the average of 1/4 and 1/4 is going to be 1/4 What is the probability of being at B? Well the average of A and C in move two is 1/2 and 1/4 that's the same thing as the average of 4/8ths and 2/8ths that's 3/8ths and then we are going to get the exact same value for C. I think 3/8ths Another pattern here is that B and C are always going to be the same thing and since B and C are always going to be the same thing the average is going to be that value and it's going to be the probability of being at A in the next turn So let us just keep doing this and we can go all the way to ten but maybe we will see some type of pattern here So on out fourth move what is the probability of being at A? Which is the average of B and C So it is going to be 3/8ths So we can just take this value here and then what is the probability of being at B? Well it is going to be the average of A and C and so let's see this is 4/16 + 6/16 = 10/16 and then we have to divide it by two which is 5/16 Did I do that right? Let me just do this on the corner. I don't want to make a careless mistake here. 1/4 is 4/16 + 6/16 and then we want to divide that by two. We are taking the average. So that's 10/16 divided by 2 which is equal to 5/16 Alright so let me clear theis out so that I do not waste valuable real estate Alright. So then this is also going to be 5/16 because it's going to be the average of 3/8 and 1/4 as well so it's going to be 5/16 Now we are on move 5 And we could keep going like this all the way to move ten but hopefully we willl see a pattern here So move five the probability of moving to A is going to be 5/16 the average of these two 5/16 The probability of moving to B (We can already see a pattern) it seems like we went from having 2,4,8 in the denominator to 16 in the denominator I'm guessing that we are going to have to go to 32 in the denominator and so we are going to take the average of 10/32 and 12/32 and that is 11/32 And this is also going to be 11/32 Let's go to move 6 for A it's going to be 11/32 (it seems like the pattern is holding) this is going ot be something over 64 and so this is the average if you multiply this times 4 you get 20 and then this is 20/64 and this is 22/64 the average is going to be 21 So let us keep extrapolating this and see if there is a way and we could actually just keep doing the math for 7,8,9,10 Feel free to do that on your own if you are interested and hopefully you will get the right answer. But let's see is you can spot a pattern here This is also going to be 21/64 move 7 for A is easy. That's just going to be the average of these two guys, 21/64 But let's see if there is a pattern forming So it looks like the (and remember the question is we just want to look at the probability of it moving to A on the tenth move.) and so if you look at A you start off with a denominator So this is 2 to the move minus 1. 1/2 to the move minus 1 It looks like it's always cuz its 1/2 to the 0. This is 1/2 to the 1 and you have 1/2 squared that's 1 less than three 1/2 to the 3rd So it looks like if you fast forward to the nth move or even better let us fast forward to the tenth move. So 7, 8, 9 and 10 This is not actually a lot of math to fill in. But let us just figure it out So 7,8,9, 10, this is going to be 16, 32, 64 This is going to be 128 if we go with the pattern This is going to be 256 and then this row over here is going to be over 512. So we actually already figured out the n part. And lets see is we can figure out a pattern for the numerators here. We went from 1 to 3 to 5 So let us see 5 is 3+2 not 1 Then we go, let's see you have 5 and it looks like you are taking 2times this and adding it to that to get that. 2 times 1 plus 3 is five. 2 times 3 plus 5 is 11. 2 times 5 plus 11 is 21. So let us just go with that So 2 times 11 is 22 plus 21 is 43 and then 2 times 21 is 42 plus 43 is 85 and then this is going to be 86 plus 85 is let's see 85 times two is 170 so its going to be 171 So if we believe what we just did we get out answer m + n = 171 +512 Which is let's see we are going to have two plus 1 is 3 1 plus so this becomes ten and then we get 703. Wait I made a bone headed mistake on the addition Let me do that again So 1 plus 7 is 8 not 10. I don't know why my brain was thinking that and then 5 plus 1 is 6. So we get 683 as our answer So that is m + n and the probability of moving to vertex A on the tenth turn is 171/512 and you can verify this for yourself Or we could even prove to ourselves is we are interested that each successive term here is really equal to the previous term times two times the term before that Actually for fun let us just prove it to ourselves So let us just say that this is the nth term Our probability of being at A is A/2^n and what ends up happening is that the probability of being at b and C let us call that B/ This power is always 1 higher power of 2. 2 ^n plus 1 and this right over here is also going to be the same probability 2/n+1 Then on the nth + 1 term the probability of being at A is just going to be the average of these two guys which is going to be B times 2 to the n plus 1 and the probability of being at, this is B this is C, this is A The probability of being at B is going ot be the average of 2A/ 2^(n+1) (I just multiplied the numerator and the denominator by 2) plus B/2^(n+1)and then all of that over 2 So we are going to divide the whole thing by 2 and that's going to be the same value for C. And actaully if we do a little math here this is going to be [2A + B]/[2^(n+2)] And so on the nth+2 move our value for A is going to be this thing right here The average of these two guys which is the exact same thing so it's going to be [2A+B] / [2^(n+2)] So this verifies the pattern that we just thought about Our powers of two are increasing and so if we go two terms forward This term is = to 2 times 2 terms before plus the terms before. 2A+B So that is the pattern that we used and we can feel pretty good about the answer!