Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2020 CIME I Problems/Problem 8: Difference between revisions

← Older edit
Jbala (talk | contribs)
1,029 edits
No edit summary
Bigbrain 2009 (talk | contribs)
editor
27 edits
 
(4 intermediate revisions by 2 users not shown)
Line 9: Line 9:


==Solution==
==Solution==
{{solution}}
First, note that to get <math>2^n</math> people more on the island, you can only have <math>2^n</math> people join on day <math>n</math>, because otherwise two things would happen on some day after <math>n</math> (things such as <math>2^{n+1} - 2^n</math> happen on the same day).
 
Also, the population cannot reach <math>2^n</math> by day <math>n</math>. This means that we must gain <math>2^n</math> people on days <math>9</math>, <math>10</math>, <math>19</math>, and <math>20</math>, which has a probability of <math>\frac{1}{3^4}</math>.
 
Next, let's consider days <math>1-8</math>. On each day, three things can happen to keep the sum at <math>0</math> (otherwise we would not get the desired result):
 
- You gain <math>0</math> people.
 
- You gain <math>2^n</math> people, and lose the same amount the next day.
 
- You lose <math>2^{n-1}</math> people, cancelling out yesterday's gain.
 
The gaining and the losing come in pairs. We have <math>5</math> cases:
 
1. <math>8</math> blanks: probability <math>\frac{{8 \choose 0}}{3^8} = \frac{1}{3^8}</math>.
 
2. <math>6</math> blanks, <math>1</math> gain and lose: probability <math>\frac{{7 \choose 1}}{3^8} = \frac{7}{3^8}</math>.
 
3. <math>4</math> blanks, <math>2</math> gain and lose: probability <math>\frac{{6 \choose 2}}{3^8} = \frac{15}{3^8}</math>.
 
4. <math>2</math> blanks, <math>3</math> gain and lose: probability <math>\frac{{5 \choose 3}}{3^8} = \frac{10}{3^8}</math>.
 
5. <math>0</math> blanks, <math>4</math> gain and lose: probability <math>\frac{{4 \choose 4}}{3^8} = \frac{1}{3^8}</math>.
 
Adding these up, our probability is <math>\frac{34}{3^8}</math>.
 
Similarly, the probability for days <math>11-18</math> is <math>\frac{34}{3^8}</math>.
 
Now, the number of people stays the same mod <math>2^{21}</math> after day <math>21</math>. Therefore, if you can reach the desired sum, you would have the desired sum on day <math>20</math>. Thus, we can get our answer by multiplying.
 
<cmath>\frac{1}{3^4} \cdot \left(\frac{34}{3^8}\right)^2 = \frac{1156}{3^{20}}.</cmath>
 
Therefore, <math>p=1156</math> and <math>q=20</math>. Taking the remainder of <math>\frac{1176}{1000}</math>, we get <math>176</math>.
 
~mathboy100


{{CIME box|year=2020|n=I|num-b=7|num-a=9}}
{{CIME box|year=2020|n=I|num-b=7|num-a=9}}
{{MAC Notice}}
{{MAC Notice}}

Latest revision as of 12:14, 1 February 2025

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^4} \cdot \left(\frac{34}{3^8}\right)^2 = \frac{1156}{3^{20}}.\]

Therefore, $p=1156$ and $q=20$. Taking the remainder of $\frac{1176}{1000}$, we get $176$.

~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

Template:MAC Notice

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2020_CIME_I_Problems/Problem_8&oldid=241610"