2020 Mock Combo AMC 10 II Problems/Problem 23

Problem

How many sequences $a_1, a_2, …, a_{15}$ satisfy that $a_i \in \{2, 3\}$ for all $1 \leq i\leq 15$ and that $\sum_{j=1}^{k} a_j$ is divisible by $5$ if and only if $k=15$ ?

$\textbf{(A)}\ 144 \qquad\textbf{(B)}\ 178 \qquad\textbf{(C)}\ 233 \qquad\textbf{(D)}\ 288 \qquad\textbf{(E)}\ 466$

Solution 1

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

Problem

Solution 1