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.
 A: I'm not quite sure that generating functions and some complex numbers are included in 11th grade (not sure what it corresponds to in Sweden), but you can get a closed solution for each value of $n$ if you know about these. Even though I suspect this is too complicated.
Let the generating function be
\begin{equation}
f_n(x) = (x+x^2+x^3+x^4+x^5+x^6)^n
\end{equation}
For two dices, expanding $f_2(x)$ gives
\begin{equation}
f_2(x) = x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9 +3x^10+2x^{11}+x^{12}
\end{equation}
here, it is the coefficients of $x^4,x^8$ and $x^{12}$ which are interesting, the sum of these corresponds to the number of outcomes which are divisible by four. Summing up, we see that for two dices, there are $3+5+1=9$ ways to get a sum divisible by four.
Now, define the number $\zeta = e^{\pi i/2}$. This has a periodicity of $4$, e.g. $\zeta^1 = \zeta^5$. If you expand $f_n(x)$, you get $f_n(x) = \sum_{k=0}^{6n} c_kx^k$, so here we want to try to extract the coefficients of interest, i.e. $c_4,c_8,c_{12}, ...$.
If you now look at the function $g_k(x)=x^k, k=0,1,2,3,...$, note that
\begin{align} 
g_0(\zeta^0) + g_0(\zeta^1) + g_0(\zeta^2) + g_0(\zeta^3) &= 4 \newline
g_1(\zeta^0) + g_1(\zeta^1) + g_1(\zeta^2) + g_1(\zeta^3) &= 0 \newline
g_2(\zeta^0) + g_2(\zeta^1) + g_2(\zeta^2) + g_2(\zeta^3) &= 0 \newline
g_3(\zeta^0) + g_3(\zeta^1) + g_3(\zeta^2) + g_3(\zeta^3) &= 0 \newline
g_4(\zeta^0) + g_4(\zeta^1) + g_4(\zeta^2) + g_4(\zeta^3) &= 4 \newline
\end{align}
and so on. As you can see, we extract the correct coefficients. This means that we have that the number of possible ways $N$ to have a sum divisible by four is given by
\begin{equation}
N = \frac{1}{4} \sum_{k=0}^3 f_n(\zeta^k) 
\end{equation}
Calculating gives
\begin{align}
f_n(\zeta^0) &= 6^n \newline
f_n(\zeta^1) &= (-1+i)^n \newline
f_n(\zeta^2) &= 0 \newline
f_n(\zeta^3) &= (-1-i)^n
\end{align}
such that
\begin{equation}
N = \frac{1}{4} \sum_{k=0}^3 f_n(\zeta^k) = \frac{1}{4} \left(6^n + 2^{n/2+1} \cos\left(\frac{3\pi n}{4} \right) \right)
\end{equation}
The first few terms give that the number of total outcomes which are divisible by four are then $N=1,9,55,322,1946$ for $n=1,2,3,4,5$. These are the same I got when expanding the generating functions so I think things match up, even though I'm seldom certain.
Furthermore, since you asked about the probability, the total number of outcomes are $6^n$, the probability for the sum being divisible by four, is given by
\begin{equation}
P_n = \frac{1}{4} \left(1 + \frac{2^{n/2+1}}{6^n} \cos\left(\frac{3\pi n}{4} \right) \right)
\end{equation}
Finally, note that $P_n\rightarrow 1/4$ when $n\rightarrow \infty$.
A: 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)$$
