<s>[INST] Probability of a sum being divisible by $4$ Roll $n$ six-sided dice.
What is the probability that the sum of the results is divisible by $4$?
This is an 11th grade problem, and I really don't know -after a lot of searching-what tools do I need to solve this problem using only high school knowledge.
 [/INST] Let $S_n$ denotes the random variable corresponding to the sum modulo $4$ after $n$ throws. You can model $S_n$ as a Markov Chain with $4$ states $\{0,1,2,3\}$ and initial value $S_0 = 0$
The matrix associated with this chain is :
$$M = \frac{1}{6}\begin{pmatrix}
1 & 2 & 2 & 1 \\ 
1 & 1  & 2 & 2 \\ 
2 & 1& 1 & 2 \\ 
2 & 2 & 1 & 1
\end{pmatrix}$$ and the desired probability is $m^{(n)}_{1,1}$ where  $m^{(n)}_{i,j}$ are the coefficients of $M^n$
Let's denote $$M' = \begin{pmatrix}
1 & 2 & 2 & 1 \\ 
1 & 1  & 2 & 2 \\ 
2 & 1& 1 & 2 \\ 
2 & 2 & 1 & 1
\end{pmatrix}$$
It is a circulant matrix and it implies that

*

*$M'$ is a diagonalizable matrix

*The 4 eigenvalues $\lambda_i$ are given by the $P(\omega)$  where $\omega \in \mathbb{U}_4$ and $P(x) = \sum_{j=1}^4 m_{1,j}x^{j-1} = 1 + 2x + 2x^2 + x^3$
We obtain $\lambda_1 = 0$, $\lambda_2 = 6$, $\lambda_2 = -1-i$, $\lambda_3 = -1+i$
and $M'$ can be written $$M' = Pdiag(\lambda_1,\lambda_2,\lambda_3,\lambda_4)P^{-1}$$ and therefore
$$M'^n = Pdiag(\lambda_1^n,\lambda_2^n,\lambda_3^n,\lambda_4^n)P^{-1}$$
This shows that $m'^{(n)}_{1,1}$ is a linear combination of $\lambda_i^n$.
More precisely, it exists 4 constant $a,b,c,d$ such as :
$m'^{(n)}_{1,1} = a \times 0^n + b \times 6^n + c(-1+i)^n + d(-1-i)^n$
with $m'^{(n)}_{1,1} = 1,1,9,55$ for $n=0,1,2,3$ you can solve a $4 \times 4$ system and get $$m'^{(n)}_{1,1} = \frac14(0^n + 6^n + (-1-i)^n + (-1+i)^n)$$
And you can retrieve $$m^{(n)}_{1,1} = \frac1{4 \times 6^n}(0^n + 6^n + (-1-i)^n + (-1+i)^n)$$
</s>