2020 CIME I Problems/Problem 8
Problem 8
A person has been declared the first to inhabit a certain planet on day . For each positive integer , if there is a positive number of people on the planet, then either one of the following three occurs, each with probability :
- (i) the population stays the same;
- (ii) the population increases by ; or
- (iii) the population decreases by . (If there are no greater than people on the planet, the population drops to zero, and the process terminates.)
The probability that at some point there are exactly people on the planet can be written as , where and are positive integers such that isn't divisible by . Find the remainder when is divided by .
Solution
First, note that to get people more on the island, you can only have people join on day , because otherwise two things would happen on some day after (things such as happen on the same day).
Also, the population cannot reach by day . This means that we must gain people on days , , , and , which has a probability of .
Next, let's consider days . On each day, three things can happen to keep the sum at (otherwise we would not get the desired result):
- You gain people.
- You gain people, and lose the same amount the next day.
- You lose people, cancelling out yesterday's gain.
The gaining and the losing come in pairs. We have cases:
1. blanks: probability .
2. blanks, gain and lose: probability .
3. blanks, gain and lose: probability .
4. blanks, gain and lose: probability .
5. blanks, gain and lose: probability .
Adding these up, our probability is .
Similarly, the probability for days is .
Now, the number of people stays the same mod after day . Therefore, if you can reach the desired sum, you would have the desired sum on day . Thus, we can get our answer by multiplying.
Therefore, and . Taking the remainder of , we get .
~mathboy100
2020 CIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All CIME Problems and Solutions |
The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions.