\section*{Exercise 3 (Candidates who have followed the specialization course)}
5 POINTS

We have a fair die with 6 faces numbered 1 to 6 and 3 coins A, B and C each having one heads side and one tails side.\\
A game consists of rolling the die one or more times.\\
After each die roll, if we get 1 or 2, then we flip coin A, if we get 3 or 4, then we flip coin B and if we get 5 or 6, then we flip coin C.\\
At the beginning of the game, all 3 coins are on the tails side.

\begin{enumerate}
  \item In the algorithm below, 0 codes the tails side and 1 codes the heads side. If $a$ codes one side of coin A, then $1 - a$ codes the other side of coin A.
\end{enumerate}

\begin{verbatim}
Variables: a, b, c, d, s are natural integers
    i, n are integers greater than or equal to 1
Initialization: a takes the value 0
    b takes the value 0
    c takes the value 0
    Input n
Processing: For i going from 1 to n do
    d takes the value of a random integer between 1 and 6
    If d <= 2
        then a takes the value 1 - a
        else If d <= 4
            then b takes the value 1 - b
            else c takes the value 1 - c
            EndIf
    EndIf
    s takes the value a + b + c
    EndFor
Output: Display s
\end{verbatim}

a. We execute this algorithm by inputting $n = 3$ and assuming that the random values generated successively for $d$ are $1; 4$ and 2. Copy and complete the table given below containing the state of the variables during the execution of the algorithm:

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
variables & $i$ & $d$ & $a$ & $b$ & $c$ & $s$ \\
\hline
initialization &  &  &  &  &  &  \\
\hline
$1^{\text{st}}$ loop iteration &  &  &  &  &  &  \\
\hline
$2^{\mathrm{nd}}$ loop iteration &  &  &  &  &  &  \\
\hline
$3^{\mathrm{rd}}$ loop iteration &  &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

b. Does this algorithm allow us to know whether, after an execution of $n$ rolls, all three coins are on the heads side?

2. For every natural integer $n$, we denote:
\begin{itemize}
  \item $X_{n}$ the event: ``After $n$ die rolls, all three coins are on the tails side''
  \item $Y_{n}$ the event: ``After $n$ die rolls, exactly one coin is on the heads side and the others are on the tails side''
  \item $Z_{n}$ the event: ``After $n$ die rolls, exactly two coins are on the heads side and the other is on the tails side''
  \item $T_{n}$ the event: ``After $n$ die rolls, all three coins are on the heads side''.
\end{itemize}

Moreover, we denote $x_{n} = p(X_{n}); y_{n} = p(Y_{n}); z_{n} = p(Z_{n})$ and $t_{n} = p(T_{n})$ the respective probabilities of events $X_{n}, Y_{n}, Z_{n}$ and $T_{n}$.