A common problem among AIME contests is a “path” problem, where you must calculate a value/ probability of an event occurring many times.
For example, let’s say you have this problem:
You and Bob play Rock Paper Scissors. You both start with $2 dollars and if you win, you give Bob $1. If Bob wins, he gives you $1. What’s the chance Bob loses all of his money before you?
So, you know that the situation returns to the norm, so the probability should be affected.
p = (probability of winning two straight) + (probability of winning 1 and losing 1) * p (because this would cause it to go back to p) + (probability of tying) * p
The probability of winning a game of rock paper scissors is 1/3, because if you go anywhere, there is a 1/3 chance his move is the losing move.
The probability of winning two straight is (1/3)^2 * 2, because you win twice, but the order doesn’t matter, you could win with rock then paper, or vice versa, so it’s 2/9
Now, the probability of winning and losing once is (1/3) * (1/3) * 2 = 2/9, because the order of the win/loss doesn’t matter.
The probability of tying is 1/3, because once again, for any move you make, there’s a 1/3 chance it’ll be the same one.
p = 2/9 + 2/9p + 1/3p
p = 2/9 + 2/9p + 3/9p
p = 2/9 + 5/9p
4/9p = 2/9
p = 1/2
So, there's a 50% chance that if you both start at $2, there's a 50% chance you'll win. That's pretty obvious, because no one has an advantage.
Now, if you start with $3 and Bob starts with $1, the odds change.
So, now p = 1/3 (win) + 1/3 * p (tie) + 1/3* (1/2) (1/3 chance you lose, then you have a 1/2 chance of winning)
p = 1/3 + 1/3p + 1/6
2/3p = 1/2, p = 3/4.
You have a 75% chance of winning if you start at $3, and Bob starts at $1.
Those questions were pretty straightforward, and could be guessed just by using logic.
Another Example Problem
You're in a cave, and you have three doors. In one door, you walk around for two days, before returning to your original location. In another door, you walk around for three days, before returning back to the cave. In the last door, you walk for four days, and you leave. What is the average number of days you stay in the cave? (note: assume the doors are random each time. Otherwise, you could go in the first, then the second, then the third)
Using the same method as before, you are able to calculate the average number of days.
So, e = 1/3* (first door amount) + 1/3 (second door amount) + 1/3 * (last door amount)
For the first two doors, it's 2 + e, and 3 + e, respectively, because you return to your original location, and the expected number of days hasn't been affected.
e = 1/3 * (2 + e) + 1/3 * (3 + e) + 1/3 (4)
e = 5/3 + 2/3e + 4/3
e = 3 + 2/3e
1/3e = 3
e = 9
So, if you're in that situation, you can expected to be in the cave for an average of 9 days.
A Third Example Problem
You have a single bacterium. It has a 1/4 chance of tripling, a 1/4 chance of doubling, a 1/4 chance of staying the same, and a 1/4 chance of dying. What's the chance the colony of bacteria dies off completely?
So, p, the probability of one bacterium dying = 1/4 * (probability of 3 dying) + 1/4 * (probability of 2 dying) + 1/4 * (probability of 1 dying) + 1/4
Each bacterium can either die, stay the same then die, double then die, triple then die, and etc. So you must take into consideration that the situation returns to the original place, just there are more of them. So, the chance of three bacteria dying is p^3, two- p^2, one- p, and etc. For three bacteria, it's p^3, because each bacterium is has a chance p of dying.
p = 1/4p^3 + 1/4p^2 + 1/4p + 1/4
0 = 1/4p^3 + 1/4p^2 - 3/4p + 1/4
0 = p^3 + p^2 - 3p + 1
Now, by looking at How to Find the Roots of a Polynomial, you can figure out that a factor is 1.
0 = (p-1)(p^2 + 2p - 1)
The probability can't equal 1, because the bacteria can keep doubling or tripling forever, so that's an extraneous root. Now, the factors of the quadratic are -1±√2, and -1-√2 is negative, so that's also extraneous. So, our answer is -1+√2, or √2 - 1 or ~0.414. Therefore, there's a 41.4% chance that the bacteria die off completely.