> [!Question] Problem
> Find the number of subsets of $\{ 1,2,\dots , 2000 \},$ the sum of whose elements is divisible by $5.$
###### Solution
For positive integers $n,$ let $a_{n},b_{n},c_{n},d_{n},e_{n}$ denote the number of subsets of $\{ 1,2,\dots,5n \}$ whose sum are congruent to $0,1,2,3,4$ modulo $5$ respectively.
Then for all $n \geq 1,$ $\begin{align}
a_{n} &= 8a_{n-1} + 6b_{n-1} + 6c_{n-1} + 6d_{n-1} +6e_{n-1} \\
b_{n} &= 6a_{n-1} + 8b_{n-1} + 6c_{n-1} + 6d_{n-1} +6e_{n-1} \\
c_{n} &= 6a_{n-1} + 6b_{n-1} + 8c_{n-1} + 6d_{n-1} +6e_{n-1} \\
d_{n} &= 6a_{n-1} + 6b_{n-1} + 6c_{n-1} + 8d_{n-1} +6e_{n-1} \\
e_{n} &= 6a_{n-1} + 6b_{n-1} + 6c_{n-1} + 6d_{n-1} +8e_{n-1}
\end{align}$
Define $z_{n}= b_{n}+c_{n}+d_{n}+e_{n}$ then $\begin{pmatrix}
a_{n} \\ z_{n}
\end{pmatrix} = \begin{pmatrix}
8 & 6 \\
24 & 26
\end{pmatrix}^{n} \begin{pmatrix}
1 \\ 0
\end{pmatrix}$noting that $a_{0}=1$ and $z_{n}=0.$
Eigenvalues $\lambda$ of $\begin{pmatrix}8 & 6 \\24 & 26 \end{pmatrix}$ satisfy $\begin{array}{||}8- \lambda & 6 \\24 & 26-\lambda \end{array}= 0$which is equivalent to $(\lambda-32)(\lambda-2)=0.$ Thus $\lambda=2$ or $32.$ The corresponding eigenvectors $(-1,1)$ and $(1,4)$ thus by [[Real Square Matrix of Order n is Diagonalisable iff it has n Linearly Independent Eigenvectors (Diagonalisation Theorem)|diagonalisation theorem]], $\begin{aligned}
\begin{pmatrix}a_{n} \\ z_{n}\end{pmatrix} &= \frac{1}{5} \begin{pmatrix}
-4 & 1 \\
1 & 1
\end{pmatrix} \begin{pmatrix}
2^{n} & 0 \\
0 & 32^{n}
\end{pmatrix} \begin{pmatrix}
-1 & 1 \\
1 & 4
\end{pmatrix} \begin{pmatrix}
1 \\ 0
\end{pmatrix} \\
& = \frac{1}{5} \begin{pmatrix}
4 \cdot 2^{n} + 32^{n} \\
32^{n} - 2^{n}
\end{pmatrix}
\end{aligned}$
Therefore $a_{400}= \frac{1}{5} (4 \cdot 2^{400}+ 32^{400}).$
Check
```run-python
def a(n):
A = [0] * (n + 1)
Z = [0] * (n + 1)
A[0] = 1
for i in range(1, n + 1):
A[i] = 8 * A[i - 1] + 6 * Z[i - 1]
Z[i] = 24 * A[i - 1] + 26 * Z[i - 1]
return A[n]
result_a_400 = a(400)
expected_result = (4 * (2 ** 400) + 32 ** 400) // 5
# Check if the results are equal
print(result_a_400 == expected_result)
```
###### Solution
For any natural number $m,$ let $A_{m}$ denote the number of subsets of $[5m]$ the sum of whose elements is divisible by 5.
Now $[5(m+1)]=[5m]\cup \{ 5m+1,\dots,5m+5 \}.$ By inspection, 8 subsets of $\{ 0,1,2,3,4 \}$ have sum congruent to $0$ modulo $5,$ while $6$ have sum congruent to $1,2,3$ and $4$ respectively. Thus $A_{m+1}=8A_{m}+6(2^{5m}-A_{m})$
Solving the recurrence gives the required answer.
###### Solution
Consider the [[Group action|action]] of the [[Cyclic Group|cyclic group]] of order of 5 on $\mathcal{P}([2000])$ that sends a generator to $(1,2,3,4,5)(6,7,8,9,10)\dots(1996,1997,1998,1999,2000).$
Each [[Orbit under Group Action]] contains exactly one subset divisible by 5.
By [[Orbit Counting Theorem]], number of distinct orbits is given by $\text{\# orbits} = \frac{1}{5} (2^{2000}+2^{400} + 2^{400}+ 2^{400} + 2^{400})= \frac{1}{5}2^{2000}+ \frac{4}{5}2^{400}$