2020 CIME I Problems/Problem 8

Problem 8

A person has been declared the first to inhabit a certain planet on day $N=0$ . For each positive integer $N>0$ , if there is a positive number of people on the planet, then either one of the following three occurs, each with probability $\frac{1}{3}$ :

(i) the population stays the same;

(ii) the population increases by $2^N$ ; or

(iii) the population decreases by $2^{N-1}$ . (If there are no greater than $2^{N-1}$ people on the planet, the population drops to zero, and the process terminates.)

The probability that at some point there are exactly $2^{20}+2^{19}+2^{10}+2^9+1$ people on the planet can be written as $\frac{p}{3^q}$ , where $p$ and $q$ are positive integers such that $p$ isn't divisible by $3$ . Find the remainder when $p+q$ is divided by $1000$ .

Solution

First, note that to get $2^n$ people more on the island, you can only have $2^n$ people join on day $n$ , because otherwise two things would happen on some day after $n$ (things such as $2^{n+1} - 2^n$ happen on the same day).

Also, the population cannot reach $2^n$ by day $n$ . This means that we must gain $2^n$ people on days $9$ , $10$ , $19$ , and $20$ , which has a probability of $\frac{1}{3^4}$ .

Next, let's consider days $1-8$ . On each day, three things can happen to keep the sum at $0$ (otherwise we would not get the desired result):

- You gain $0$ people.

- You gain $2^n$ people, and lose the same amount the next day.

- You lose $2^{n-1}$ people, cancelling out yesterday's gain.

The gaining and the losing come in pairs. We have $5$ cases:

1. $8$ blanks: probability $\frac{{8 \choose 0}}{3^8} = \frac{1}{3^8}$ .

2. $6$ blanks, $1$ gain and lose: probability $\frac{{7 \choose 1}}{3^8} = \frac{7}{3^8}$ .

3. $4$ blanks, $2$ gain and lose: probability $\frac{{6 \choose 2}}{3^8} = \frac{15}{3^8}$ .

4. $2$ blanks, $3$ gain and lose: probability $\frac{{5 \choose 3}}{3^8} = \frac{10}{3^8}$ .

5. $0$ blanks, $4$ gain and lose: probability $\frac{{4 \choose 4}}{3^8} = \frac{1}{3^8}$ .

Adding these up, our probability is $\frac{34}{3^8}$ .

Similarly, the probability for days $11-18$ is $\frac{34}{3^8}$ .

Now, the number of people stays the same mod $2^21$ after day $21$ . Therefore, if you can reach the desired sum, you would have the desired sum on day $20$ . Thus, we can get our answer by multiplying:

$\frac{1}{3^5} \cdot \left(\frac{34}{3^8}\right)^2 = \frac{1156}{3^20}.$

Our answer is $1176$ .

~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.

Page

Toolbox

Search

2020 CIME I Problems/Problem 8

Problem 8

Solution