2020 Mock Combo AMC 10 II Problems/Problem 23
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