Difference between revisions of "2020 Mock Combo AMC 10 II Problems/Problem 23"
(Created page with "Call a sequence a_1, a_2") |
|||
| Line 1: | Line 1: | ||
| − | Call a sequence a_1, a_2 | + | 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 5. Let <math>f(n)</math> be the number of 5-free sequences <math>b_1, b_2,..., b_n</math> exist such that its sum has a remainder of 1 or 4 when divided by 5 (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 1 when divided by 5. |
| + | |||
| + | 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 4 when divided by 5, 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 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. | ||
| + | |||
| + | 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} = 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. | ||
| + | |||
| + | So the answer is <math>144 + 144 = 288 \Rightarrow \fbox D</math>. | ||
| + | |||
| + | |||
| + | ~sdfgfjh | ||
Latest revision as of 21:21, 6 August 2024
Call a sequence 
5-free if 
for all 
and that 
is never divisible by 5. Let 
be the number of 5-free sequences 
exist such that its sum has a remainder of 1 or 4 when divided by 5 (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 1 when divided by 5.
If 
, the sequence 
has a sum that has a remainder of 4 when divided by 5, so we add 
for this case.
If 
, the sequence has a sum that has a remainder of 3 when divided by 5, so 
must equal 2. Then 
has a sum that has a remainder of 1 when divided by 5. 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 1 when divided by 5. We add 
for this case.
If 
, 
similarly and has a sum that has a remainder of 4 when divided by 5. We also add for this case.
So the answer is 
.
~sdfgfjh
