Problem 13 - American Invitational Mathematics Examination (AIME), Mathematics Video Lecture - Engineering Mathematics

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!