2020 Mock Combo AMC 10 II Problems/Problem 23

Call a sequence $a_1, a_2,..., a_n$ 5-free if $a_i \in \{2, 3\}$ for all $1 \leq i\leq n$ and that $\sum_{j=1}^{k} a_j$ is never divisible by 5. Let $f(n)$ be the number of 5-free sequences $b_1, b_2,..., b_n$ 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 $b_n$ to create a recurrence. Here I will assume that the sum of $b_1, b_2,..., b_n$ has a remainder of 1 when divided by 5.

If $b_n = 2$ , the sequence $b_1, b_2,..., b_{n-1}$ has a sum that has a remainder of 4 when divided by 5, so we add $f(n-1)$ for this case.

If $b_n = 3$ , the sequence $b_1, b_2,..., b_{n-1}$ has a sum that has a remainder of 3 when divided by 5, so $b_{n-1}$ must equal 2. Then $b_1, b_2,..., b_{n-2}$ has a sum that has a remainder of 1 when divided by 5. So we add $f(n-2)$ for this case.

These are all of the cases so $f(n) = f(n-1) + f(n-2)$ and $f(1) = 0$ and $f(2) = 1$ by testing. Now let's return to the original problem. We will do casework on $a_{15}$ .

If $a_{15}= 2$ , $a_{14} = 2$ as well and $a_1, a_2,..., a_{13}$ has a sum that has a remainder of 1 when divided by 5. We add $f(13) = 144$ for this case.

If $a_{15} = 3$ , $a_{14} = 3$ similarly and $a_1, a_2,..., a_{13}$ has a sum that has a remainder of 4 when divided by 5. We also add $f(13) = 144$ for this case.

So the answer is $144 + 144 = 288 \Rightarrow \fbox D$ .

~sdfgfjh

Page

Toolbox

Search

2020 Mock Combo AMC 10 II Problems/Problem 23