Difference between revisions of "2020 CIME I Problems/Problem 8"
(Created page with "==Problem 8== A person has been declared the first to inhabit a certain planet on day <math>N=0</math>. For each positive integer <math>N=0</math>, if there is a positive numb...") |
Megaboy6679 (talk | contribs) m (→Solution) |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
==Problem 8== | ==Problem 8== | ||
− | A person has been declared the first to inhabit a certain planet on day <math>N=0</math>. For each positive integer <math>N | + | A person has been declared the first to inhabit a certain planet on day <math>N=0</math>. For each positive integer <math>N>0</math>, if there is a positive number of people on the planet, then either one of the following three occurs, each with probability <math>\frac{1}{3}</math>: |
:(i) the population stays the same; | :(i) the population stays the same; | ||
Line 9: | Line 9: | ||
==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^5} \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 21:23, 30 January 2023
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.