National Math Camp 2020 Exam 1 Problem 3

Discussion on Bangladesh National Math Camp
User avatar
FuadAlAlam
Posts:30
Joined:Wed Sep 16, 2020 11:10 am
Location:Dhaka, Bangladesh
Contact:
National Math Camp 2020 Exam 1 Problem 3

Unread post by FuadAlAlam » Mon Dec 07, 2020 1:27 pm

Call a permutation of the numbers $1,2,3,...,n$ stable if it starts with a $1$ and it's consecutive terms differ by at most $2$. Let $T_n$ be the number of stable permutations. If $1 \leq n \leq 2020$, for how many values of $n$ is $T_n$ divisible by $3$?

User avatar
FuadAlAlam
Posts:30
Joined:Wed Sep 16, 2020 11:10 am
Location:Dhaka, Bangladesh
Contact:

Re: National Math Camp 2020 Exam 1 Problem 3

Unread post by FuadAlAlam » Mon Mar 01, 2021 11:39 am

It is easy to check that $T_1 = T_2 = 1$ and $T_3 = 2$. Now, we will find a recurrence relation for $T_n$. Consider all stable permutation for $n+1$ numbers, where $n \geq 3$. Let $\{ 1, a_1, a_2, \ldots, a_n \}$ be such a permutation. We have $4$ cases :

Case 1 : $a_1=2$
Remove $\{1\}$ and consider all permutations of $\{a_1 - 1, a_2 - 1, \ldots, a_n - 1\}$. As $a_1 - 1 = 1$ is fixed, we get $T_n$ number of permutation for this case.
Case 2 : $a_2=2$
This forces $a_1 = 3$ and $a_3 = 4$. Otherwise, there would be consecutive terms differ by at least $3$. Now, remove $\{ 1, 3, 2 \}$ and consider all permutations of $\{a_3 - 3, a_4 - 3, \ldots, a_n - 3 \}$. As $a_3 - 3 = 1$ is fixed, similar to the previous case, we get $T_{n-2}$ number of permutations for this case.
Case 3 : $a_i = 2$ for $3 \leq i \leq n-1$
This forces $a_1 = 3$. So, at least one of the $a_{i-1}$ and $a_{i+1}$ would be greater than $4$. This contradicts the given condition. So, there is no such stable permutation in this case.
Case 4 : $a_n = 2$
This forces the only valid permutation $\{1, 3, 5, 7, \ldots, 8, 6, 4, 2 \}$.

Therefore, $T_{n+1} = T_n + T_{n-2} + 1$ must hold for $n \geq 3$.

It is easy to show by strong induction that
$$T_{8k+1} \equiv 1 \pmod{3}$$
$$T_{8k+2} \equiv 1 \pmod{3}$$
$$T_{8k+3} \equiv 2 \pmod{3}$$
$$T_{8k+4} \equiv 1 \pmod{3}$$
$$T_{8k+5} \equiv 0 \pmod{3}$$
$$T_{8k+6} \equiv 0 \pmod{3}$$
$$T_{8k+7} \equiv 2 \pmod{3}$$
$$T_{8k+8} \equiv 0 \pmod{3}$$

Notice that for $8k + 1 \leq i \leq 8k + 8$, there are exactly $3$ of the $T_i$'s which are divisible by $3$. It is easy to check that for $2017 \leq i \leq 2020$, none of the $T_i$'s are divisible by $3$.
Therefore, the total number of values of $n$ for which $T_n$ is divisible by $3$ is $\frac{2016 \times 3}{8} = 756$.

Post Reply