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.

Main content
Current time:0:00Total duration:16:13

2003 AIME II problem 13

Video transcript

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 stood starting vertex on his tenth move is M over N where m and n are relatively prime positive integers find M plus n so this lesson it's right here where m and n are relatively prime positive integers that's essentially says we have the positive version of this fraction in lowest in simplified form I guess you could say you you can't simplify it any more so let's just think about the problem we have an equilateral triangle here we have an equilateral triangle with three vertices a B and C and our bug our bug is going to start let's say at vertex a so this is our this is our bug right here and on each move it'll randomly select one of the two vertices so on its first move it will either go to vertex B or then vertex C and then depending whether it went there I went to vertex C then on its next move it'll either go to vertex B or vertex a if it went to vertex B on the next move it'll either go to vertex a or vertex C so let's just think about it we want to figure out let's see and crawls along side given that the probability that the bug moves us to its starting vertex on his tenth move so we want to see the probability of it moving to vertex a on its tenth move on his tenth move so let's just let's just think about what happens in each move the probability of moving to one of the vertices in a given move so let's say let's say we have let me just number these so let's say we have move one over here move let me make a column so we have vertex a B and C vertices a B and C and let's think about move once let me make it clear that this is a row and then on move one what's the probability of moving to vertex a well you're already at vertex a and it says the bug is always going to go to one of the other two vertices so your probability of moving to vertex a is zero on move one what's the probability of moving to vertex B what's gonna be one-half what's the probability of moving to vertex C what's gonna be one half as well half chance going there half a chance going there and obviously all of the probabilities have to add up to one cuz gonna do something on that on that move now let's think about move to let's think about move to so what's the probability what's the probability of now moving to vertex a well there was a what there's a one half chance that we were already at B if we were already at B if we were already it'd be there will now be a one half chance of moving back to a so this is one half one half times one half but that's that's only the situation if we were already it be if we were already at C which there was a 1/2 probability of that then there would also be a 1/2 probability of moving to a so this is going to be the one half chance that we were already at C times given that we were all ready to see the probability that we move to a so this is 1/2 times 1/2 is 1/4 plus 1/2 times 1/2 plus 1/4 this is going to be equal to this is equal to 1/2 now what's the probability of moving to B in the second turn now the only the only place other than B so obviously you can't move from B to B the only place that the bug can move from B in the second turn it's going to be C because we know in the second turn or at the end of the first turn that he's not going to be an a he's either gonna be at B or C if he's already at B there's no way he's gonna go back to B so the only situation is if the bug is already at C if the bug is already seen there's a 1/2 chance of that happening so that's this number right here if the bug is already at C there and that's the 1/2 probability then there's going to be a further 1/2 probability that it moves to B so it's going to be 1/2 times 1/2 which is equal to 1/4 now what's the probability of moving to see well it's the exact same logic the bug is not going to be on verdict vertex a after the first move there's a 1/2 probability there's a 1/2 probability that it's going to be at B and that if it's at B then there's a 1/2 probability then there's a 1/2 probability then it'll go to see that it'll go to C so this is going to be 1/4 as well in general let me just draw something let me just do something a little general here let's say that we have turned let I'll erase this in a second because I think we might want to use this real estate over here let's say we have we let's say and move n the probability at vert of being at vertex a is probability of a the probability of being at vertex B is probability of landing on B on move N and the probability of C is P this is the probability of moving to vertex C on move-in now let's think about the probability of being each at each of these nodes on n plus 1 or moving to each of these nodes on move n plus 1 so in to get to a on move n plus 1 you have to either be at problem at B or at C you can't be at a and stay at a so the the probability of moving to a and your n plus 1 move is going to be the probability of being at B times 1/2 right because if you're at B there's a 1/2 chance you're going to go to a plus the probability of being at C in your last and you're at the end of the last move times 1/2 the only there's a 1/2 chance if you're at C you'll move to a there's a 1/2 chance if you'd be you move to a now what's the probability of going to be well there's two ways that you can get to B you could start at a so it's you could start at a so the probability of being at a times 1/2 or you could start at C so it's plus the probability of C times 1/2 if you're actually doing this problem under time pressure you wouldn't necessarily have to go through this but I just want to make it clear what's going on here and finally what's the probability of landing and C on your end plus 1 term well it's going to be the probability it's going to be the probability of being at a times 1/2 plus the probability of being at B times 1/2 so hopefully this makes the pattern a little bit clearer of what what's good happening no matter what a is going to be the average a and the next move going to be the average essentially of the probabilities of being at B and C in the last move and you see that the average of 1/2 and 1/2 is 1/2 the probability of being B at B and the n plus 1 move it's 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 average of 0 and 1/2 is 1/4 but now that'll helpfully simplify things a little bit more for our brains let's go let's keep going through the I'll leave this here I said I was going to erase it but let's keep going this way and let me continue the column so we have columns a or rows a B and C and now we are on move three I'm just continuing it down here so what's the probability of move being a and move three what we just said it's going to be the average of B and C and B and C or 1/4 so the average of 1/4 and 1/4 is going to be 1/4 what's the probability of being at B we'll see average of a and C and move to average of 1/2 and 1/4 or that's the same thing as the average of what four eight four eight and two eighths that's 3/8 3/8 and then we're gonna get the exact same value for C 3/8 and I think you see another pattern here B and C are always going to be the same thing and since B and C are always going to be the same thing their 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's just keep doing this and we could go all the way to ten but maybe we'll see some type of pattern here so on our fourth move on our fourth move what's the probability of being at a what's just the average of B and C so it's going to be 3/8 it's just going to be 3/8 so we can just take this value here and then what's the probability of being at B well it's going to be the average of a and C average of a and C and so let's say I think we'd have to go over 16 this is 4 over 16 for over 16 plus 6 over 16 is 10 over 16 10 over 16 which is did I do oh and then we have to divide it by 2 which is 5 over 16 5 over 16 did I do that right let me just do this on the I don't make a careless mistake here so we want to do one fourth we want to do one fourth is 4 over 16 plus 6 over 16 and then we want to divide that by 2 we're taking the average so it's 10 over 16 divided by 2 which is equal to 5 over 16 all right so let me clear this out so that I don't waste valuable real estate all right so then this is also going to be 5 or 16 because it's going to be the average of 3/8 and 1/4 as well so it's going to be 5 well let me just switch I'll switch colors in the next column 5 over 16 now we're in move five and we could keep going like this all the way to move 10 but hopefully we'll just see a pattern here so and move 5 the probability of moving to a is going to be 5 over 16 the average of these to 5 over 16 the probability of moving to be you already see a pattern it seems like you know we went from a 2 in the denominator 4 in the denominator 8 in the denominator 60 in the denominator I'm guessing that we're gonna have to go to 32 over the denominator and so we're gonna take the average of 10 over 32 10 over 32 and 12 over 32 and that's 11 over 32 and this is also going to be 11 over 32 let's go to move 6 let's go to move 6 so in 4a it's going to be 11 over 11 over 32 and I'll just seems like the pattern is holding this is going to be something over 64 and so this is the average this if you multiply this times 4 you get 20 and then this is 22 over say this is 20 over 64 this is 22 over 64 the average is going to be 21 so if we just wanted to keep extrapolating this let's see if there's a way and we could actually just do the math I just do 7 8 9 10 we're only four moves away but actually let's see if we can see a pattern yeah I feel free to do that on your own if you're interested hopefully you'll get the right answer this is also going to be 21 over 64 move seven move 7 4 a is easy that's just going to be the average of these two guys 21 over 64 but let's see if there's a pattern forming so it looks like it looks like the problem for if and remember our question is we just want to look at the probability of moving to a on the tenth move and so if you look at a you start off with a denominator you start off with the denominator so this is two to the move plot minus one one over two to the move minus one it looks like it's always because there's 1 over 2 to the 0 this is 1 over 2 to the 1 then you have 1 over 2 squared that's 1 less than 3 1 over 2 to the third so it looks like it looks like if you fast forward to the enth move or even better let's fast forward to the 10th move so 7 8 9 and 10 this actually isn't a lot of math to fill in but let's just figure it out so if you 7 8 9 10 so 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 actual if you have time you can prove that this definitely is the pattern and then this row over here is going to be over 512 so we actually already figured out the end part and let's see if we can figure out a pattern for the numerators here we went from C we went 1 3 to 5 so C 5 is 3 plus 2 not 1 then you go you see you have 5 well it looks like we're taking 2 times this you're taking 2 times this and adding it to that to get that 2 times 1/2 times 1 plus 3 is 5 2 times 3 plus 5 is 11 2 times 5 plus 11 is 21 so let's just go with that so 2 times 11 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 right 2 times 43 is 86 86 plus 85 is let's the 85 times 2 is 170 so it's going to be 170 171 and so if we believe what we just did we get our answer M plus n is going to be is going to be 171 plus 512 so it's going to be 171 512 plus 171 which is which is let's see we're going to have 2 plus 1 is 3 one plus so this comes ten and then we get 703 no no wait I just made a boneheaded mistake on the addition let me let me 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's that's M plus N or the probability of moving to the to vertex a on the tenth turn is 171 over 512 and you can verify for yourself it actually wasn't a lot more math just to go through it at this point or we could even prove to ourselves if we're interested that each successive term here is really equal to the previous term plus 2 times the term before that actually let me just let's just just for fun let's just prove it to ourselves so let's say that we this is the nth term our probability of being at a let's say our probability of being at a is a over a over 2 to the N a over 2 to the N and what and they're not probability of being at B and C is going to be let's call that let's call that B over this power is always 1 higher power of 2 2 to the n plus 1 and this right over here is also going to be the same probability 2 over n plus 1 then on the n plus 1 term the probability of being at age is 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 remember this is B and this is C this is a the probability of being at B is going to be the average of a and C so it's going to be a to the 2n let me put it multiply it by 2 so it's 2 a over 2 to the n plus 1 I just multiply the numerator and denominator by 2 plus B over 2 to the n plus 1 and then all of that over 2 all of that over 2 so we're going to divide that the whole let me not write it that way we're going to divide that by 2 and that's going to be the same value for C and actually if we do a little bit of math here this is going to be this is going to be 2a plus B over 2a plus B over two to the N plus 2 2 to the N plus 2 and so on the nth plus to move our value for H is going to be this thing right here the average of 2 these two guys which is the exact same thing so it's going to be 2a plus B over 2 to the n plus 2 so this verifies the pattern that we just thought about our powers of 2 are increasing and if we go to terms forward this term is equal to 2 times 2 terms before plus the term before 2a plus B so that's the pattern we used so we can feel pretty good about our answer