Difference between revisions of "2020 Mock Combo AMC 10 II Problems/Problem 23"
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | How many sequences <math>a_1, a_2, …, a_{15}</math> satisfy that <math>a_i \in \{2, 3\}</math> for all <math>1 \leq i\leq 15</math> and that<cmath>\sum_{j=1}^{k} a_j</cmath>is divisible by <math>5</math> if and only if <math>k=15</math>? | ||
− | + | <math>\textbf{(A)}\ 144 \qquad\textbf{(B)}\ 178 \qquad\textbf{(C)}\ 233 \qquad\textbf{(D)}\ 288 \qquad\textbf{(E)}\ 466</math> | |
+ | ==Solution 1== | ||
+ | Call a sequence <math>a_1, a_2,..., a_n</math> 5-free if <math>a_i \in \{2, 3\}</math> for all <math>1 \leq i\leq n</math> and that <math>\sum_{j=1}^{k} a_j</math> is never divisible by <math>5</math>. Let <math>f(n)</math> be the number of <math>5</math>-free sequences <math>b_1, b_2,..., b_n</math> exist such that its sum has a remainder of <math>1</math> or <math>4</math> when divided by <math>5</math> (Note that it doesn't matter if it is divisible by 1 or 4 because if you switch every 2 with a 3 and vice versa, you form a bijection between them). Now we do case work on <math>b_n</math> to create a recurrence. Here I will assume that the sum of <math>b_1, b_2,..., b_n</math> has a remainder of <math>1</math> when divided by <math>5</math>. | ||
− | If <math>b_n = 3</math>, the sequence <math>b_1, b_2,..., b_{n-1}</math> has a sum that has a remainder of 3 when divided by 5, so <math>b_{n-1}</math> must equal 2. Then <math>b_1, b_2,..., b_{n-2}</math> has a sum that has a remainder of 1 when divided by 5. So we add <math>f(n-2)</math> for this case. | + | If <math>b_n = 2</math>, the sequence <math>b_1, b_2,..., b_{n-1}</math> has a sum that has a remainder of <math>4</math> when divided by <math>5</math>, so we add <math>f(n-1)</math> for this case. |
+ | |||
+ | If <math>b_n = 3</math>, the sequence <math>b_1, b_2,..., b_{n-1}</math> has a sum that has a remainder of <math>3</math> when divided by <math>5</math>, so <math>b_{n-1}</math> must equal <math>2</math>. Then <math>b_1, b_2,..., b_{n-2}</math> has a sum that has a remainder of <math>1</math> when divided by <math>5</math>. So we add <math>f(n-2)</math> for this case. | ||
These are all of the cases so <math>f(n) = f(n-1) + f(n-2)</math> and <math>f(1) = 0</math> and <math>f(2) = 1</math> by testing. Now let's return to the original problem. We will do casework on <math>a_{15}</math>. | These are all of the cases so <math>f(n) = f(n-1) + f(n-2)</math> and <math>f(1) = 0</math> and <math>f(2) = 1</math> by testing. Now let's return to the original problem. We will do casework on <math>a_{15}</math>. | ||
− | If <math>a_{15}= 2</math>, <math>a_{14} = 2</math> as well and <math>a_1, a_2,..., a_{13}</math> has a sum that has a remainder of 1 when divided by 5. We add <math>f(13) = 144</math> for this case. | + | If <math>a_{15}= 2</math>, <math>a_{14} = 2</math> as well and <math>a_1, a_2,..., a_{13}</math> has a sum that has a remainder of <math>1</math> when divided by <math>5</math>. We add <math>f(13) = 144</math> for this case. |
− | If <math>a_{15} = 3</math>, <math>a_{14} = 3</math> similarly and <math>a_1, a_2,..., a_{13}</math> has a sum that has a remainder of 4 when divided by 5. We also add <math>f(13) = 144</math> for this case. | + | If <math>a_{15} = 3</math>, <math>a_{14} = 3</math> similarly and <math>a_1, a_2,..., a_{13}</math> has a sum that has a remainder of <math>4</math> when divided by <math>5</math>. We also add <math>f(13) = 144</math> for this case. |
So the answer is <math>144 + 144 = 288 \Rightarrow \fbox D</math>. | So the answer is <math>144 + 144 = 288 \Rightarrow \fbox D</math>. |
Latest revision as of 16:44, 7 August 2024
Problem
How many sequences satisfy that
for all
and that
is divisible by
if and only if
?
Solution 1
Call a sequence 5-free if
for all
and that
is never divisible by
. Let
be the number of
-free sequences
exist such that its sum has a remainder of
or
when divided by
(Note that it doesn't matter if it is divisible by 1 or 4 because if you switch every 2 with a 3 and vice versa, you form a bijection between them). Now we do case work on
to create a recurrence. Here I will assume that the sum of
has a remainder of
when divided by
.
If , the sequence
has a sum that has a remainder of
when divided by
, so we add
for this case.
If , the sequence
has a sum that has a remainder of
when divided by
, so
must equal
. Then
has a sum that has a remainder of
when divided by
. So we add
for this case.
These are all of the cases so and
and
by testing. Now let's return to the original problem. We will do casework on
.
If ,
as well and
has a sum that has a remainder of
when divided by
. We add
for this case.
If ,
similarly and
has a sum that has a remainder of
when divided by
. We also add
for this case.
So the answer is .
~sdfgfjh