Exercise 3 -- Candidates who have followed the specialization course

The manager of a website, composed of three web pages numbered 1 to 3 and linked together by hypertext links, wishes to predict the frequency of connection to each of his web pages.
Statistical studies have allowed him to notice that:

• If an internet user is on page no. 1, then he will go either to page no. 2 with probability $\frac{1}{4}$, or to page no. 3 with probability $\frac{3}{4}$.
• If an internet user is on page no. 2, then either he will go to page no. 1 with probability $\frac{1}{2}$ or he will stay on page no. 2 with probability $\frac{1}{4}$, or he will go to page no. 3 with probability $\frac{1}{4}$.
• If an internet user is on page no. 3, then either he will go to page no. 1 with probability $\frac{1}{2}$, or he will go to page no. 2 with probability $\frac{1}{4}$, or he will stay on page no. 3 with probability $\frac{1}{4}$.

For every natural number $n$, we define the following events and probabilities: $A_n$: ``After the $n$-th navigation, the internet user is on page no. 1'' and we denote $a_n = P(A_n)$. $B_n$: ``After the $n$-th navigation, the internet user is on page no. 2'' and we denote $b_n = P(B_n)$. $C_n$: ``After the $n$-th navigation, the internet user is on page no. 3'' and we denote $c_n = P(C_n)$.

1. Show that, for every natural number $n$, we have $a_{n+1} = \frac{1}{2}b_n + \frac{1}{2}c_n$.

We admit that, similarly, $b_{n+1} = \frac{1}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n$ and $c_{n+1} = \frac{3}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n$. Thus: $$\left\{\begin{aligned} a_{n+1} &= \frac{1}{2}b_n + \frac{1}{2}c_n \\ b_{n+1} &= \frac{1}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n \\ c_{n+1} &= \frac{3}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n \end{aligned}\right.$$

1. For every natural number $n$, we set $U_n = \begin{pmatrix}a_n\\b_n\\c_n\end{pmatrix}$. $U_0 = \begin{pmatrix}a_0\\b_0\\c_0\end{pmatrix}$ represents the initial situation, with $a_0 + b_0 + c_0 = 1$. Show that, for every natural number $n$, $U_{n+1} = MU_n$ where $M$ is a $3\times 3$ matrix that you will specify. Deduce that, for every natural number $n$, $U_n = M^n U_0$.
2. Show that there exists a unique column matrix $U = \begin{pmatrix}x\\y\\z\end{pmatrix}$ such that: $x + y + z = 1$ and $MU = U$.
3. A computer algebra system has made it possible to obtain the expression of $M^n$, $n$ being a non-zero natural number: $$M^n = \begin{pmatrix} \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n \times 2}{3} & \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n}{-3} & \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n}{-3} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{5}{12} + \frac{\left(-\left(\frac{-1}{2}\right)^n\right)\times 2}{3} & \frac{5}{12} + \frac{-\left(\frac{-1}{2}\right)^n}{-3} & \frac{5}{12} + \cdots \end{pmatrix}$$

We study the evolution over time of the number of young and adult animals in a population. For any natural integer $n$, we denote by $j _ { n }$ the number of young animals after $n$ years of observation and $a _ { n }$ the number of adult animals after $n$ years of observation. At the beginning of the first year of the study, there are 200 young animals and 500 adult animals. Thus $j _ { 0 } = 200$ and $a _ { 0 } = 500$. We admit that for any natural integer $n$ we have: $$\left\{ \begin{array} { l } j _ { n + 1 } = 0,125 j _ { n } + 0,525 a _ { n } \\ a _ { n + 1 } = 0,625 j _ { n } + 0,625 a _ { n } \end{array} \right.$$ We introduce the following matrices: $$A = \left( \begin{array} { l l } 0,125 & 0,525 \\ 0,625 & 0,625 \end{array} \right) \text { and, for any natural integer } n , U _ { n } = \binom { j _ { n } } { a _ { n } } .$$

1. a. Show that for any natural integer $n , U _ { n + 1 } = A \times U _ { n }$. b. Calculate the number of young animals and adult animals after one year of observation and then after two years of observation (results rounded down to the nearest unit). c. For any non-zero natural integer $n$, express $U _ { n }$ as a function of $A ^ { n }$ and $U _ { 0 }$.
2. We introduce the following matrices $Q = \left( \begin{array} { c c } 7 & 3 \\ - 5 & 5 \end{array} \right)$ and $D = \left( \begin{array} { c c } - 0,25 & 0 \\ 0 & 1 \end{array} \right)$. a. We admit that the matrix $Q$ is invertible and that $Q ^ { - 1 } = \left( \begin{array} { c c } 0,1 & - 0,06 \\ 0,1 & 0,14 \end{array} \right)$. Show that $Q \times D \times Q ^ { - 1 } = A$. b. Show by induction on $n$ that for any non-zero natural integer $n$: $A ^ { n } = Q \times D ^ { n } \times Q ^ { - 1 }$. c. For any non-zero natural integer $n$, determine $D ^ { n }$ as a function of $n$.
3. We admit that for any non-zero natural integer $n$, $$A ^ { n } = \left( \begin{array} { l l } 0,3 + 0,7 \times ( - 0,25 ) ^ { n } & 0,42 - 0,42 \times ( - 0,25 ) ^ { n } \\ 0,5 - 0,5 \times ( - 0,25 ) ^ { n } & 0,7 + 0,3 \times ( - 0,25 ) ^ { n } \end{array} \right)$$ a. Deduce the expressions of $j _ { n }$ and $a _ { n }$ as functions of $n$ and determine the limits of these two sequences. b. What can we conclude about the population of animals studied?

3. For every natural integer $n$, we denote by $C _ { n }$ the column matrix $\binom { u _ { n + 1 } } { u _ { n } }$.
We denote by $A$ the square matrix of order 2 such that, for every natural integer $n$, $C _ { n + 1 } = A C _ { n }$. Determine $A$ and prove that, for every natural integer $n , C _ { n } = A ^ { n } C _ { 0 }$.
4. Let $P = \left( \begin{array} { l l } 2 & 3 \\ 1 & 1 \end{array} \right) , D = \left( \begin{array} { l l } 2 & 0 \\ 0 & 3 \end{array} \right)$ and $Q = \left( \begin{array} { c c } - 1 & 3 \\ 1 & - 2 \end{array} \right)$.
Calculate $Q P$. It is admitted that $A = P D Q$. Prove by induction that, for every non-zero natural integer $n , A ^ { n } = P D ^ { n } Q$.

A species of bird lives only on two islands A and B of an archipelago. At the beginning of 2013, 20 million birds of this species are present on island A and 10 million on island B.
Observations over several years have allowed ornithologists to estimate that, taking into account births, deaths, and migrations between the two islands, we find at the beginning of each year the following proportions:

• on island A: $80\%$ of the number of birds present on island A at the beginning of the previous year and $30\%$ of the number of birds present on island B at the beginning of the previous year;
• on island B: $20\%$ of the number of birds present on island A at the beginning of the previous year and $70\%$ of the number of birds present on island B at the beginning of the previous year.

Exercise 4 — Candidates who have followed the specialization course
In an imaginary isolated village, a new contagious but non-fatal disease has appeared. Scientists discovered that an individual could be in one of three following states:

• $S$: ``the individual is healthy, that is, not sick and not infected'',
• $I$: ``the individual is a healthy carrier, that is, not sick but infected'',
• $M$: ``the individual is sick and infected''.

Part A
Scientists estimate that a single individual is at the origin of the disease among the 100 people in the population and that, from one week to the next, an individual changes state according to the following process:

• among healthy individuals, the proportion of those who become healthy carriers is equal to $\dfrac{1}{3}$ and the proportion of those who become sick is equal to $\dfrac{1}{3}$,
• among healthy carriers, the proportion of those who become sick is equal to $\dfrac{1}{2}$.

We denote by $P_n = \begin{pmatrix} s_n & i_n & m_n \end{pmatrix}$ the row matrix giving the probabilistic state after $n$ weeks where $s_n, i_n$ and $m_n$ denote respectively the probability that the individual is healthy, a healthy carrier, or sick in the $n$-th week.
We have $P_0 = (0.99 \quad 0 \quad 0.01)$ and for all natural integer $n$, $$\left\{\begin{aligned} s_{n+1} &= \frac{1}{3}s_n \\ i_{n+1} &= \frac{1}{3}s_n + \frac{1}{2}i_n \\ m_{n+1} &= \frac{1}{3}s_n + \frac{1}{2}i_n + m_n \end{aligned}\right.$$

1. Write the matrix $A$ called the transition matrix, such that for all natural integer $n$, $P_{n+1} = P_n \cdot A$.

(For candidates who have followed the specialization course) We study the population of an imaginary region. On January 1, 2013, this region had 250,000 inhabitants, of which $70 \%$ lived in the countryside and $30 \%$ in the city. Examination of statistical data collected over several years leads to the choice of modelling the population evolution for the coming years as follows:

• the total population is globally constant,
• each year, $5 \%$ of those living in the city decide to move to the countryside and $1 \%$ of those living in the countryside choose to move to the city.

For every natural number $n$, we denote $v _ { n }$ the number of inhabitants of this region living in the city on January 1 of the year $(2013 + n)$ and $c _ { n }$ the number of those living in the countryside on the same date.

1. For every natural number $n$, express $v _ { n + 1 }$ and $c _ { n + 1 }$ as functions of $v _ { n }$ and $c _ { n }$.
2. Let the matrix $A = \left( \begin{array} { l l } 0{,}95 & 0{,}01 \\ 0{,}05 & 0{,}99 \end{array} \right)$.

A city has a bike-sharing network where two stations A and B are located at the top of a hill. It is admitted that no bikes from other stations arrive at stations A and B.
It is observed that for each hour $n$ on average:

• $20 \%$ of the bikes present at hour $n - 1$ at station A are still at this station. $60 \%$ of the bikes present at hour $n - 1$ at station A are at station B and the others are in other stations of the network or in circulation.
• $10 \%$ of the bikes present at hour $n - 1$ at station B are at station $\mathrm { A } , 30 \%$ are still at station B and the others are in other stations of the network or in circulation.
• At the beginning of the day, station A has 50 bikes, station B has 60 bikes.

Part A

After $n$ hours, let $a _ { n }$ denote the average number of bikes present at station A and $b _ { n }$ the average number of bikes present at station B. Let $U _ { n }$ denote the column matrix $\binom { a _ { n } } { b _ { n } }$ and thus $U _ { 0 } = \binom { 50 } { 60 }$.

1. Determine the matrix $M$ such that $U _ { n + 1 } = M \times U _ { n }$.
2. Determine $U _ { 1 }$ and $U _ { 2 }$.
3. After how many hours is there only one bike left in station A?

Part B

The service decides to study the effects of a supply of stations A and B consisting of bringing 30 bikes to station A and 10 bikes to station B after each hour of operation.
After $n$ hours, let $\alpha _ { n }$ denote the average number of bikes present at station A and $\beta _ { n }$ the average number of bikes present at station B. Let $V _ { n }$ denote the column matrix $\binom { \alpha _ { n } } { \beta _ { n } }$ and $V _ { 0 } = \binom { 50 } { 60 }$. Under these conditions $V _ { n + 1 } = M \times V _ { n } + R$ with $R = \binom { 30 } { 10 }$.

1. Let $I$ denote the matrix $\left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right)$ and $N$ the matrix $I - M$. a. Let $V$ denote a column matrix with two rows. Show that $V = M \times V + R$ is equivalent to $N \times V = R$. b. It is admitted that $N$ is an invertible matrix and that $N ^ { - 1 } = \left( \begin{array} { l l } 1,4 & 0,2 \\ 1,2 & 1,6 \end{array} \right)$. Deduce that $V = \binom { 44 } { 52 }$.
2. For every natural number $n$, let $W _ { n } = V _ { n } - V$. a. Show that $W _ { n + 1 } = M \times W _ { n }$. b. It is admitted that: for every natural number $n , W _ { n } = M ^ { n } \times W _ { 0 }$, and $$\text{for every natural number } n \geqslant 1 , M ^ { n } = \frac { 1 } { 2 ^ { n - 1 } } \left( \begin{array} { l l } 0,2 & 0,1 \\ 0,6 & 0,3 \end{array} \right) .$$ Calculate, for every natural number $n \geqslant 1 , V _ { n }$ as a function of $n$. c. Does the average number of bikes present in stations A and B tend to stabilize?

Exercise 3 — Candidates who have followed the specialization
Each young parent uses only one brand of baby food jars each month. Three brands $\mathrm { X } , \mathrm { Y }$ and Z share the market. Let $n$ be a natural integer. We denote: $\quad X _ { n }$ the event ``brand X is used in month $n$ '', $Y _ { n }$ the event ``brand Y is used in month $n$ '', $Z _ { n }$ the event ``brand Z is used in month $n$ ''. The probabilities of events $X _ { n } , Y _ { n } , Z _ { n }$ are denoted respectively $x _ { n } , y _ { n } , z _ { n }$. The advertising campaign of each brand causes the distribution to change.
A buyer of brand X in month $n$ has the following month: $50 \%$ chance of remaining loyal to this brand, $40 \%$ chance of buying brand Y, $10 \%$ chance of buying brand $Z$.
A buyer of brand Y in month $n$ has the following month: $30 \%$ chance of remaining loyal to this brand, $50 \%$ chance of buying brand X, $20 \%$ chance of buying brand $Z$.
A buyer of brand Z in month $n$ has the following month: $70 \%$ chance of remaining loyal to this brand, $10 \%$ chance of buying brand X, $20 \%$ chance of buying brand Y.

1. a. Express $x _ { n + 1 }$ as a function of $x _ { n } , y _ { n }$ and $z _ { n }$.

We admit that: $y _ { n + 1 } = 0.4 x _ { n } + 0.3 y _ { n } + 0.2 z _ { n }$ and that $z _ { n + 1 } = 0.1 x _ { n } + 0.2 y _ { n } + 0.7 z _ { n }$. b. Express $z _ { n }$ as a function of $x _ { n }$ and $y _ { n }$. Deduce the expression of $x _ { n + 1 }$ and $y _ { n + 1 }$ as functions of $x _ { n }$ and $y _ { n }$.
2. We define the sequence $\left( U _ { n } \right)$ by $U _ { n } = \binom { x _ { n } } { y _ { n } }$ for every natural integer $n$.
We admit that, for every natural integer $n$, $U _ { n + 1 } = A \times U _ { n } + B$ where $A = \left( \begin{array} { l l } 0.4 & 0.4 \\ 0.2 & 0.1 \end{array} \right)$ and $B = \binom { 0.1 } { 0.2 }$.
At the beginning of the statistical study (January 2014: $n = 0$), we estimate that $U _ { 0 } = \binom { 0.5 } { 0.3 }$. Consider the following algorithm:

Variables	\begin{tabular}{l} $n$ and $i$ natural integers.
$A$, $B$ and $U$ matrices

\hline Input and initialization &

Request the value of $n$ $i$ takes the value 0

$A$ takes the value $\left( \begin{array} { l l } 0.4 & 0.4 \\ 0.2 & 0.1 \end{array} \right)$

$B$ takes the value $\binom { 0.1 } { 0.2 }$

$U$ takes the value $\binom { 0.5 } { 0.3 }$

\hline Processing &

While $i < n$

$U$ takes the value $A \times U + B$

$i$ takes the value $i + 1$

End while

\hline Output & Display $U$ \hline \end{tabular}
a. Give the results displayed by this algorithm for $n = 1$ then for $n = 3$. b. What is the probability of using brand X in April?
In the rest of the exercise, we seek to determine an expression of $U _ { n }$ as a function of $n$. We denote by $I$ the matrix $\left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right)$ and $N$ the matrix $I - A$.
3. We denote by $C$ a column matrix with two rows. a. Prove that $C = A \times C + B$ is equivalent to $N \times C = B$. b. We admit that $N$ is an invertible matrix and that $N ^ { - 1 } = \left( \begin{array} { l l } \frac { 45 } { 23 } & \frac { 20 } { 23 } \\ \frac { 10 } { 23 } & \frac { 30 } { 23 } \end{array} \right)$.
Deduce that $C = \binom { \frac { 17 } { 46 } } { \frac { 7 } { 23 } }$.
4. We denote by $V _ { n }$ the matrix such that $V _ { n } = U _ { n } - C$ for every natural integer $n$. a. Show that, for every natural integer $n$, $V _ { n + 1 } = A \times V _ { n }$. b. We admit that $U _ { n } = A ^ { n } \times \left( U _ { 0 } - C \right) + C$.
What are the probabilities of using brands $\mathrm { X } , \mathrm { Y }$ and Z in May?

A laboratory studies the spread of a disease in a population. A healthy individual is an individual who has never been affected by the disease. A sick individual is an individual who has been affected by the disease and is not cured. A recovered individual is an individual who has been affected by the disease and has recovered. Once recovered, an individual is immunized and cannot become sick again.
The first observations show that, from one day to the next:

• $5\%$ of individuals become sick;
• $20\%$ of individuals recover.

For every natural number $n$, we denote by $a_n$ the proportion of healthy individuals $n$ days after the start of the experiment, $b_n$ the proportion of sick individuals $n$ days after the start of the experiment, and $c_n$ that of recovered individuals $n$ days after the start of the experiment. We assume that at the start of the experiment, all individuals are healthy, that is $a_0 = 1$, $b_0 = 0$ and $c_0 = 0$.

1. Calculate $a_1$, $b_1$ and $c_1$.
2. a) What is the proportion of healthy individuals who remain healthy from one day to the next? Deduce $a_{n+1}$ as a function of $a_n$. b) Express $b_{n+1}$ as a function of $a_n$ and $b_n$.

We admit that $c_{n+1} = 0.2b_n + c_n$. For every natural number $n$, we define $U_n = \left(\begin{array}{c} a_n \\ b_n \\ c_n \end{array}\right)$ We define the matrices $A = \left(\begin{array}{ccc} 0.95 & 0 & 0 \\ 0.05 & 0.8 & 0 \\ 0 & 0.2 & 1 \end{array}\right)$ and $D = \left(\begin{array}{ccc} 0.95 & 0 & 0 \\ 0 & 0.8 & 0 \\ 0 & 0 & 1 \end{array}\right)$ We admit that there exists an invertible matrix $P$ such that $D = P^{-1} \times A \times P$ and that, for every natural number $n$ greater than or equal to 1, $A^n = P \times D^n \times P^{-1}$.

1. a) Verify that, for every natural number $n$, $U_{n+1} = A \times U_n$. We admit that, for every natural number $n$, $U_n = A^n \times U_0$. b) Prove by induction that, for every non-zero natural number $n$, $$D^n = \left(\begin{array}{ccc} 0.95^n & 0 & 0 \\ 0 & 0.8^n & 0 \\ 0 & 0 & 1 \end{array}\right)$$

We admit that $A^n = \left(\begin{array}{ccc} 0.95^n & 0 & 0 \\ \frac{1}{3}(0.95^n - 0.8^n) & 0.8^n & 0 \\ \frac{1}{3}(3 - 4 \times 0.95^n + 0.8^n) & 1 - 0.8^n & 1 \end{array}\right)$

1. a) Verify that for every natural number $n$, $b_n = \frac{1}{3}(0.95^n - 0.8^n)$ b) Determine the limit of the sequence $(b_n)$. c) We admit that the proportion of sick individuals increases for several days, then decreases. We wish to determine the epidemic peak, that is, the moment when the proportion of sick individuals is at its maximum. To this end, we use the algorithm given in appendix 2 (to be returned with the answer sheet), in which we compare successive terms of the sequence $(b_n)$. Complete the algorithm so that it displays the rank of the day when the epidemic peak is reached and complete the table provided in appendix 2. Conclude.

(For candidates who have followed the specialization course)
As part of a study on social interactions between mice, researchers place laboratory mice in a cage with two compartments A and B. The door between these compartments is opened for ten minutes every day at noon. We study the distribution of mice in the two compartments. It is estimated that each day:

• $20\%$ of the mice present in compartment A before the door opens are found in compartment B after the door closes,
• $10\%$ of the mice that were in compartment B before the door opens are found in compartment A after the door closes.

We assume that initially, the two compartments A and B contain the same number of mice. We set $a_{0} = 0.5$ and $b_{0} = 0.5$. For all natural integer $n$ greater than or equal to 1, we denote by $a_{n}$ and $b_{n}$ the proportions of mice present respectively in compartments A and B after $n$ days, after the door closes. We denote by $U_{n}$ the matrix $\binom{a_{n}}{b_{n}}$.

1. Let $n$ be a natural integer. a. Justify that $U_{1} = \binom{0.45}{0.55}$. b. Express $a_{n+1}$ and $b_{n+1}$ as functions of $a_{n}$ and $b_{n}$. c. Deduce that $U_{n+1} = MU_{n}$ where $M$ is a matrix that we will specify. We admit without proof that $U_{n} = M^{n}U_{0}$. d. Determine the distribution of mice in compartments A and B after 3 days.
2. Let the matrix $P = \left(\begin{array}{cc} 1 & 1 \\ 2 & -1 \end{array}\right)$. a. Calculate $P^{2}$. Deduce that $P$ is invertible and $P^{-1} = \frac{1}{3}P$. b. Verify that $P^{-1}MP$ is a diagonal matrix $D$ that we will specify. c. Prove that for any natural integer $n$ greater than or equal to 1, $M^{n} = PD^{n}P^{-1}$. Using computer algebra software, we obtain $$M^{n} = \left(\begin{array}{cc} \frac{1 + 2 \times 0.7^{n}}{3} & \frac{1 - 0.7^{n}}{3} \\ \frac{2 - 2 \times 0.7^{n}}{3} & \frac{2 + 0.7^{n}}{3} \end{array}\right).$$
3. Using the help of the previous questions, what can we say about the long-term distribution of mice in compartments A and B of the cage?

Exercise 4 — Candidates who have followed the specialization course
A fish farmer has two basins A and B for raising his fish. Every year at the same time:

• he empties basin B and sells all the fish it contained and transfers all the fish from basin A to basin B;
• the sale of each fish allows the purchase of two small fish intended for basin A.

Furthermore, the fish farmer buys an additional 200 fish for basin A and 100 fish for basin B. For every natural integer greater than or equal to 1, we denote respectively by $a _ { n }$ and $b _ { n }$ the numbers of fish in basins A and B after $n$ years. At the beginning of the first year, the number of fish in basin A is $a _ { 0 } = 200$ and that in basin B is $b _ { 0 } = 100$.

1. Justify that $a _ { 1 } = 400$ and $b _ { 1 } = 300$ then calculate $a _ { 2 }$ and $b _ { 2 }$.
2. We denote by $A$ and $B$ the matrices such that $A = \left( \begin{array} { l l } 0 & 2 \\ 1 & 0 \end{array} \right)$ and $B = \binom { 200 } { 100 }$ and for every natural integer $n$, we set $X _ { n } = \binom { a _ { n } } { b _ { n } }$. a. Explain why for every natural integer $n , X _ { n + 1 } = A X _ { n } + B$. b. Determine the real numbers $x$ and $y$ such that $\binom { x } { y } = A \binom { x } { y } + B$. c. For every natural integer $n$, we set $Y _ { n } = \binom { a _ { n } + 400 } { b _ { n } + 300 }$. Prove that for every natural integer $n , Y _ { n + 1 } = A Y _ { n }$.
3. For every natural integer $n$, we set $Z _ { n } = Y _ { 2 n }$. a. Prove that for every natural integer $n , Z _ { n + 1 } = A ^ { 2 } Z _ { n }$. Deduce that for every natural integer $n , Z _ { n + 1 } = 2 Z _ { n }$. b. We admit that this recurrence relation allows us to conclude that for every natural integer $n$, $$Y _ { 2 n } = 2 ^ { n } Y _ { 0 }$$ Deduce that $Y _ { 2 n + 1 } = 2 ^ { n } Y _ { 1 }$ then prove that for every natural integer $n$, $$a _ { 2 n } = 600 \times 2 ^ { n } - 400 \text { and } a _ { 2 n + 1 } = 800 \times 2 ^ { n } - 400 .$$
4. Basin A has a capacity limited to 10000 fish. a. An algorithm is given that, for a given value of $p$, computes the number of fish $a$ in basin A after $p$ years using the formulas $a_{2n} = 600 \times 2^n - 400$ and $a_{2n+1} = 800 \times 2^n - 400$. Use this algorithm to determine from which year the capacity of basin A is exceeded.

1. We consider the equation (E) to solve in $\mathbb { Z }$ : $$7 x - 5 y = 1$$ a. Verify that the pair (3; 4) is a solution of (E). b. Show that the pair of integers $( x ; y )$ is a solution of (E) if and only if $7 ( x - 3 ) = 5 ( y - 4 )$. c. Show that the integer solutions of the equation (E) are exactly the pairs ( $x ; y$ ) of relative integers such that: $$\left\{ \begin{array} { l } x = 5 k + 3 \\ y = 7 k + 4 \end{array} \text { where } k \in \mathbb { Z } . \right.$$
2. A box contains 25 tokens, some red, some green and some white. Out of the 25 tokens there are $x$ red tokens and $y$ green tokens. Knowing that $7 x - 5 y = 1$, what can be the numbers of red, green and white tokens?
In the rest, we will assume that there are 3 red tokens and 4 green tokens.
3. We consider the following random walk of a pawn on a triangle $A B C$. At each step, we randomly draw one of the tokens from the 25, then put it back in the box.

• When at A: If the token drawn is red, the pawn goes to B. If the token drawn is green, the pawn goes to C. If the token drawn is white, the pawn stays at A.
• When at B: If the token drawn is red, the pawn goes to A. If the token drawn is green, the pawn goes to C. If the token drawn is white, the pawn stays at B.
• When at C: If the token drawn is red, the pawn goes to A. If the token drawn is green, the pawn goes to B. If the token drawn is white, the pawn stays at C.

Initially, the pawn is on vertex A. For any natural integer $n$, we denote $a _ { n } , b _ { n }$ and $c _ { n }$ the probabilities that the pawn is respectively on vertices $\mathrm { A } , \mathrm { B }$ and C at step $n$. We denote $X _ { n }$ the row matrix $\left( a _ { n } \quad b _ { n } \quad c _ { n } \right)$ and $T$ the matrix $\left( \begin{array} { l l l } 0,72 & 0,12 & 0,16 \\ 0,12 & 0,72 & 0,16 \\ 0,12 & 0,16 & 0,72 \end{array} \right)$. Give the row matrix $X _ { 0 }$ and show that, for any natural integer $n$, $X _ { n + 1 } = X _ { n } T$.
4. We admit that $T = P D P ^ { - 1 }$ where $P ^ { - 1 } = \left( \begin{array} { c c c } \frac { 3 } { 10 } & \frac { 37 } { 110 } & \frac { 4 } { 11 } \\ \frac { 1 } { 10 } & - \frac { 1 } { 10 } & 0 \\ 0 & \frac { 1 } { 11 } & - \frac { 1 } { 11 } \end{array} \right)$ and $D = \left( \begin{array} { c c c } 1 & 0 & 0 \\ 0 & 0,6 & 0 \\ 0 & 0 & 0,56 \end{array} \right)$.

(For candidates who have followed the specialization course)
An organization offers online foreign language learning. Two levels are presented: beginner or advanced. At the beginning of each month, an internet user can register, unregister or change level. At the beginning of month 0, there were 300 internet users at the beginner level and 450 at the advanced level. Each month, half of the beginners move to the advanced level, the other half remain at the beginner level and half of the advanced users who have completed their training unregister from the site. Each month, 100 new internet users register as beginners and 70 as advanced. This situation is modeled by two sequences of real numbers $( d _ { n } )$ and $( a _ { n } )$. For every natural number $n$, $d _ { n }$ and $a _ { n }$ are respectively approximations of the number of beginners and the number of advanced users at the beginning of month $n$. For every natural number $n$, we denote by $U _ { n }$ the column matrix $\binom { d _ { n } } { a _ { n } }$. We set $d _ { 0 } = 300$, $a _ { 0 } = 450$ and, for every integer $n \geqslant 0$
$$\left\{ \begin{aligned} d _ { n + 1 } & = \frac { 1 } { 2 } d _ { n } + 100 \\ a _ { n + 1 } & = \frac { 1 } { 2 } d _ { n } + \frac { 1 } { 2 } a _ { n } + 70 \end{aligned} \right.$$

1. a. Justify the equality $a _ { n + 1 } = \frac { 1 } { 2 } d _ { n } + \frac { 1 } { 2 } a _ { n } + 70$ in the context of the exercise. b. Determine the matrices $A$ and $B$ such that for every natural number $n$, $$U _ { n + 1 } = A U _ { n } + B$$
2. Prove by induction that for every natural number $n \geqslant 1$, we have $$A ^ { n } = \left( \frac { 1 } { 2 } \right) ^ { n } \left( I _ { 2 } + n T \right) \quad \text { where } T = \left( \begin{array} { l l } 0 & 0 \\ 1 & 0 \end{array} \right) \quad \text { and } I _ { 2 } = \left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right) .$$
3. a. Determine the matrix $C$ that satisfies the equality $C = A C + B$. b. For every integer $n \geqslant 0$, we set $V _ { n } = U _ { n } - \binom { 200 } { 340 }$.

Candidates who have followed the specialization course
A smoker decides to quit smoking. We choose to use the following model:

• if they do not smoke on a given day, they do not smoke the next day with a probability of 0.9;
• if they smoke on a given day, they smoke the next day with a probability of 0.6.

We call $p_{n}$ the probability of not smoking on the $n$-th day after their decision to quit smoking and $q_{n}$, the probability of smoking on the $n$-th day after their decision to quit smoking. We assume that $p_{0} = 0$ and $q_{0} = 1$.

1. Calculate $p_{1}$ and $q_{1}$.
2. We use a spreadsheet to automate the calculation of successive terms of the sequences $(p_{n})$ and $(q_{n})$. A screenshot of this spreadsheet is provided below:
   

   \cline{2-5} \multicolumn{1}{c|}{}	A	B	C	D
   1	$n$	$p_{n}$	$q_{n}$
   2	0	0	1
   3	1
   4	2
   5	3

   
   Column A contains the values of the natural integer $n$. What formulas can be written in cells B3 and C3 so that by copying them downward, we obtain respectively in columns B and C the successive terms of the sequences $(p_{n})$ and $(q_{n})$?
3. We define the matrices $M$ and, for every natural integer $n$, $X_{n}$ by
   $$M = \left(\begin{array}{ll} 0,9 & 0,4 \\ 0,1 & 0,6 \end{array}\right) \quad \text{and} \quad X_{n} = \binom{p_{n}}{q_{n}}.$$
   We admit that $X_{n+1} = M \times X_{n}$ and that, for every natural integer $n$, $X_n = M^{n} \times X_{0}$. We define the matrices $A$ and $B$ by $A = \left(\begin{array}{ll} 0,8 & 0,8 \\ 0,2 & 0,2 \end{array}\right)$ and $B = \left(\begin{array}{cc} 0,2 & -0,8 \\ -0,2 & 0,8 \end{array}\right)$. a) Prove that $M = A + 0,5 B$. b) Verify that $A^{2} = A$, and that $A \times B = B \times A = \left(\begin{array}{ll} 0 & 0 \\ 0 & 0 \end{array}\right)$.
   We admit in the following that, for every strictly positive natural integer $n$, $A^{n} = A$ and $B^{n} = B$. c) Prove that, for every natural integer $n$, $M^{n} = A + 0,5^{n} B$. d) Deduce that, for every natural integer $n$, $p_{n} = 0,8 - 0,8 \times 0,5^{n}$. e) In the long term, can we assert with certainty that the smoker will quit smoking?

Exercise 5 — Candidates who have chosen the specialisation option
Consider the matrix $A = \left( \begin{array} { l l } - 4 & 6 \\ - 3 & 5 \end{array} \right)$.

1. We call $I$ the identity matrix of order 2.
   Verify that $A ^ { 2 } = A + 2 I$.
2. Deduce an expression for $A ^ { 3 }$ and an expression for $A ^ { 4 }$ in the form $\alpha A + \beta I$ where $\alpha$ and $\beta$ are real numbers.
3. Consider the sequences $\left( r _ { n } \right)$ and $\left( s _ { n } \right)$ defined by $r _ { 0 } = 0$ and $s _ { 0 } = 1$ and, for all natural integer $n$,
   $$\left\{ \begin{array} { l } r _ { n + 1 } = r _ { n } + s _ { n } \\ s _ { n + 1 } = 2 r _ { n } \end{array} \right.$$
   Prove that, for all natural integer $n , A ^ { n } = r _ { n } A + s _ { n } I$.
4. Prove that the sequence ( $k _ { n }$ ) defined for all natural integer $n$ by $k _ { n } = r _ { n } - s _ { n }$ is geometric with common ratio $- 1$. Deduce, for all natural integer $n$, an explicit expression for $k _ { n }$ as a function of $n$.
5. We admit that the sequence ( $t _ { n }$ ) defined for all natural integer $n$ by $t _ { n } = r _ { n } + \frac { ( - 1 ) ^ { n } } { 3 }$ is geometric with common ratio 2. Deduce, for all natural integer $n$, an explicit expression for $t _ { n }$ as a function of $n$.
6. From the previous questions, deduce, for all natural integer $n$, an explicit expression for $r _ { n }$ and $s _ { n }$ as a function of $n$.
7. Deduce then, for all natural integer $n$, an expression for $A ^ { n }$.

Part A - Hill Cipher
Here are the different encryption steps for a word with an even number of letters:

Step 1	The word is divided into blocks of two consecutive letters, then for each block, each of the following steps is performed.
Step 2	To the two letters of the block are associated two integers $x_1$ and $x_2$ both between 0 and 25, which correspond to the two letters in the same order, in the following table: \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

\hline Step 3 & The matrix $X = \binom{x_1}{x_2}$ is transformed into the matrix $Y = \binom{y_1}{y_2}$ satisfying $Y = AX$, where $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$. \hline Step 4 & The matrix $Y = \binom{y_1}{y_2}$ is transformed into the matrix $R = \binom{r_1}{r_2}$, where $r_1$ is the remainder of the Euclidean division of $y_1$ by 26 and $r_2$ is the remainder of the Euclidean division of $y_2$ by 26. \hline Step 5 & To the integers $r_1$ and $r_2$ are associated the two corresponding letters from the table in step 2. The encrypted block is the block obtained by concatenating these two letters. \hline \end{tabular}
Use the encryption method presented to encrypt the word ``HILL''.
Part B - Some mathematical tools necessary for decryption

1. Let $a$ be an integer relatively prime to 26. Prove that there exists an integer $u$ such that $u \times a \equiv 1$ modulo 26.
   
2. Consider the following algorithm:
   

   VARIABLES : PROCESSING :	\begin{tabular}{l} $a, u$, and $r$ are numbers ($a$ is a natural number and relatively prime to 26)
   Read $a$
   $u$ takes the value 0, and $r$ takes the value 0
   While $r \neq 1$
   $u$ takes the value $u + 1$
   $r$ takes the value of the remainder of the Euclidean division of $u \times a$ by 26
   End While
   Display $u$

   \hline \end{tabular}
   The value $a = 21$ is entered into this algorithm. a. Reproduce on your paper and complete the following table, until the algorithm stops.
   

   $u$	0	1	2	$\ldots$
   $r$	0	21	$\ldots$	$\ldots$

   
   b. Deduce that $5 \times 21 \equiv 1$ modulo 26.
   
3. Recall that $A$ is the matrix $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$ and denote by $I$ the matrix: $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$. a. Calculate the matrix $12A - A^2$. b. Deduce the matrix $B$ such that $BA = 21I$. c. Prove that if $AX = Y$, then $21X = BY$.

Part C - Decryption
We want to decrypt the word VLUP. We denote by $X = \binom{x_1}{x_2}$ the matrix associated, according to the correspondence table, to a block of two letters before encryption, and $Y = \binom{y_1}{y_2}$ the matrix defined by the equality: $Y = AX = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right) X$. If $r_1$ and $r_2$ are the respective remainders of $y_1$ and $y_2$ in the Euclidean division by 26, the block of two letters after encryption is associated with the matrix $R = \binom{r_1}{r_2}$.

1. Prove that: $\left\{ \begin{aligned} 21x_1 &= 7y_1 - 2y_2 \\ 21x_2 &= -7y_1 + 5y_2 \end{aligned} \right.$
   
2. Using question B.2., establish that: $\begin{cases} x_1 \equiv 9r_1 + 16r_2 & \text{modulo } 26 \\ x_2 \equiv 17r_1 + 25r_2 & \text{modulo } 26 \end{cases}$
   
3. Decrypt the word VLUP, associated with the matrices $\binom{21}{11}$ and $\binom{20}{15}$.

Part A

We consider matrices $M$ of the form $M = \left( \begin{array} { l l } a & b \\ 5 & 3 \end{array} \right)$ where $a$ and $b$ are integers. The number $3 a - 5 b$ is called the determinant of $M$. We denote it $\operatorname { det } ( M )$. Thus $\operatorname { det } ( M ) = 3 a - 5 b$.

1. In this question we assume that $\operatorname { det } ( M ) \neq 0$ and we set $N = \frac { 1 } { \operatorname { det } ( M ) } \left( \begin{array} { c c } 3 & - b \\ - 5 & a \end{array} \right)$. Justify that $N$ is the inverse of $M$.
2. We consider the equation $( E ) : \quad \operatorname { det } ( M ) = 3$.
   We wish to determine all pairs of integers ( $a ; b$ ) that are solutions of equation ( $E$ ). a. Verify that the pair (6; 3) is a solution of $( E )$. b. Show that the pair of integers ( $a$; $b$ ) is a solution of ( $E$ ) if and only if $3 ( a - 6 ) = 5 ( b - 3 )$. Deduce the set of solutions of equation ( $E$ ).

Part B

1. We set $Q = \left( \begin{array} { l l } 6 & 3 \\ 5 & 3 \end{array} \right)$.
   Using Part A, determine the inverse matrix of $Q$.
2. Encoding with matrix $Q$
   To encode a two-letter word using the matrix $Q = \left( \begin{array} { l l } 6 & 3 \\ 5 & 3 \end{array} \right)$ we use the following procedure: Step 1: We associate with the word the matrix $X = \binom { x _ { 1 } } { x _ { 2 } }$ where $x _ { 1 }$ is the integer corresponding to the first letter of the word and $x _ { 2 }$ the integer corresponding to the second letter of the word according to the correspondence table below:
   

   A	B	C	D	E	F	G	H	I	J	K	L	M
   0	1	2	3	4	5	6	7	8	9	10	11	12
   N	O	P	Q	R	S	T	U	V	W	X	Y	Z
   13	14	15	16	17	18	19	20	21	22	23	24	25

   
   Step 2: The matrix $X$ is transformed into the matrix $Y = \binom { y _ { 1 } } { y _ { 2 } }$ such that $Y = Q X$. Step 3: The matrix $Y$ is transformed into the matrix $R = \binom { r _ { 1 } } { r _ { 2 } }$ such that $r _ { 1 }$ is the remainder of the Euclidean division of $y _ { 1 }$ by 26 and $r _ { 2 }$ is the remainder of the Euclidean division of $y _ { 2 }$ by 26.

Encryption Method (Hill cipher)
The following table gives a correspondence between letters and numbers:
Encryption proceeds as follows:

1. We replace the letters with the values associated using the table above, and we place the pairs of numbers obtained in column matrices: $C _ { 1 } = \binom { 12 } { 0 }$, $C _ { 2 } = \binom { 19 } { 7 }$
2. We multiply the column matrices on the left by the matrix $A = \left( \begin{array} { l l } 9 & 4 \\ 7 & 3 \end{array} \right)$: $A C _ { 1 } = \binom { 108 } { 84 }$, $A C _ { 2 } = \binom { 199 } { 154 }$
3. We replace each coefficient of the column matrices obtained by its remainder in the Euclidean division by 26: $108 = 4 \times 26 + 4$, $84 = 3 \times 26 + 6$, we obtain $\binom { 4 } { 6 }$
4. We use the correspondence table between letters and numbers to obtain the encrypted word: EGRY

Question 1: By encrypting the word ``PION'' using this method, we obtain ``LZWH''. By detailing the steps for the letters ``ES'', encrypt the word ``ESPION''.
2. Decryption Method
Let $a, b, x, y, x^{\prime}$ and $y^{\prime}$ be relative integers. We know that if $x \equiv x^{\prime}$ modulo 26 and $y \equiv y^{\prime}$ modulo 26 then $ax + by \equiv ax^{\prime} + by^{\prime}$ modulo 26. This result allows us to write that, if $A$ is a $2 \times 2$ matrix, and $B$ and $C$ are two column matrices $2 \times 1$, then $B \equiv C$ modulo 26 implies $AB \equiv AC$ modulo 26.
a. Establish that the matrix $A = \left( \begin{array} { l l } 9 & 4 \\ 7 & 3 \end{array} \right)$ is invertible, and determine its inverse. b. Decrypt the word: XQGY.

Several transmission lines are assembled end to end, and we assume they introduce errors independently of one another. Each line transmits a bit correctly with probability $p$, and incorrectly with probability $1 - p$. We study the transmission of a single bit, which has value 1 at the beginning of transmission. After passing through $n$ transmission lines, we denote:

• $p _ { n }$ the probability that the received bit has value 1;
• $q _ { n }$ the probability that the received bit has value 0.

We therefore have $p _ { 0 } = 1$ and $q _ { 0 } = 0$. We define the following matrices:
$$A = \left( \begin{array} { c c } p & 1 - p \\ 1 - p & p \end{array} \right) \quad X _ { n } = \binom { p _ { n } } { q _ { n } } \quad P = \left( \begin{array} { c c } 1 & 1 \\ 1 & - 1 \end{array} \right) .$$
We admit that, for every integer $n$, we have: $X _ { n + 1 } = A X _ { n }$ and therefore, $X _ { n } = A ^ { n } X _ { 0 }$.

1. a. Show that $P$ is invertible and determine $P ^ { - 1 }$. b. We set: $D = \left( \begin{array} { c c } 1 & 0 \\ 0 & 2 p - 1 \end{array} \right)$. Verify that: $A = P D P ^ { - 1 }$. c. Show that, for every integer $n \geqslant 1$, $$A ^ { n } = P D ^ { n } P ^ { - 1 } .$$ d. Using the screenshot of a computer algebra system given below, determine the expression of $q _ { n }$ as a function of $n$.
   

   1	$X 0 : = [ [ 1 ] , [ 0 ] ]$
   	$\left[ \begin{array} { l } 1 \\ 0 \end{array} \right]$	M
   2	$\mathrm { P } : = [ [ 1,1 ] , [ 1 , - 1 ] ]$
   	$\left[ \begin{array} { c c } 1 & 1 \\ 1 & - 1 \end{array} \right]$	M
   3	$\mathrm { D } : = [ [ 1,0 ] , [ 0,2 * p - 1 ] ]$
   	$\left[ \begin{array} { c c } 1 & 0 \\ 0 & 2 * p - 1 \end{array} \right]$	M
   4	$P * \left( D ^ { \wedge } n \right) * P ^ { \wedge } ( - 1 ) * X 0$
   	$\left[ \frac { ( 2 * p - 1 ) ^ { n } + 1 } { 2 } \right]$
   	$\frac { - ( 2 * p - 1 ) ^ { n } + 1 } { 2 }$	M

   
   
2. We assume in this question that $p$ equals 0.98. We recall that the bit before transmission has value 1. We wish the probability that the received bit has value 0 be less than or equal to 0.25. What is the maximum number of such transmission lines that can be aligned?

Exercise 5 (5 points) — Candidates who have followed the speciality course
In a given territory, we are interested in the coupled evolution of two species: the buzzards (the predators) and the voles (the prey). Scientists model, for all natural integer $n$, this evolution by:
$$\left\{ \begin{aligned} b _ { 0 } & = 1000 \\ c _ { 0 } & = 1500 \\ b _ { n + 1 } & = 0,3 b _ { n } + 0,5 c _ { n } \\ c _ { n + 1 } & = - 0,5 b _ { n } + 1,3 c _ { n } \end{aligned} \right.$$
where $b _ { n }$ represents approximately the number of buzzards and $c _ { n }$ the approximate number of voles on June 1st of the year $2000 + n$ (where $n$ denotes a natural integer).

1. We denote $A$ the matrix $\left( \begin{array} { c c } 0,3 & 0,5 \\ - 0,5 & 1,3 \end{array} \right)$ and, for all natural integer $n , U _ { n }$ the column matrix $\binom { b _ { n } } { c _ { n } }$. a. Verify that $U _ { 1 } = \binom { 1050 } { 1450 }$ and calculate $U _ { 2 }$. b. Verify that, for all natural integer $n , U _ { n + 1 } = A U _ { n }$.
2. We are given the matrices $P = \left( \begin{array} { l l } 1 & 0 \\ 1 & 1 \end{array} \right) , T = \left( \begin{array} { c c } 0,8 & 0,5 \\ 0 & 0,8 \end{array} \right)$ and $I = \left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right)$. We admit that $P$ has as its inverse a matrix $Q$ of the form $\left( \begin{array} { l l } 1 & 0 \\ a & 1 \end{array} \right)$ where $a$ is a real number. a. Determine the value of $a$ by justifying. b. We admit that $A = P T Q$. Prove that, for all non-zero integer $n$, we have $$A ^ { n } = P T ^ { n } Q .$$ c. Prove using a proof by induction that, for all non-zero integer $n$, $$T ^ { n } = \left( \begin{array} { c c } 0,8 ^ { n } & 0,5 n \times 0,8 ^ { n - 1 } \\ 0 & 0,8 ^ { n } \end{array} \right)$$
3. Lucie executes the algorithm below and obtains as output $N = 40$. What conclusion can Lucie state for the buzzards and the voles? \begin{verbatim} Initialization: N takes the value 0 B takes the value 1000 C takes the value 1500 Processing: While B > 2 or C > 2 N takes the value N + 1 R takes the value B B takes the value 0,3 R + 0,5 C C takes the value -0,5 R + 1,3 C End While Output: Display N \end{verbatim}
4. We admit that, for all non-zero natural integer $n$, we have $$U _ { n } = \binom { 1000 \times 0,8^n + 500 n \times 0,8^{n-1} }{ \text{(expression for } c_n\text{)}}$$

Exercise 4 — For candidates who have followed the speciality course Part A We consider the sequence $(u_{n})$ defined by: $u_{0} = 1,\ u_{1} = 6$ and, for every natural number $n$: $$u_{n+2} = 6u_{n+1} - 8u_{n}$$

1. Calculate $u_{2}$ and $u_{3}$.
2. We consider the matrix $A = \left(\begin{array}{cc} 0 & 1 \\ -8 & 6 \end{array}\right)$ and the column matrix $U_{n} = \binom{u_{n}}{u_{n+1}}$. Show that, for every natural number $n$, we have: $U_{n+1} = A U_{n}$.
3. We also consider the matrices $B = \left(\begin{array}{cc} 2 & -0.5 \\ 4 & -1 \end{array}\right)$ and $C = \left(\begin{array}{cc} -1 & 0.5 \\ -4 & 2 \end{array}\right)$. a. Show by induction that, for every natural number $n$, we have: $A^{n} = 2^{n}B + 4^{n}C$. b. We admit that, for every natural number $n$, we have: $U_{n} = A^{n}U_{0}$. Show that, for every natural number $n$, we have: $u_{n} = 2 \times 4^{n} - 2^{n}$.

Part B We say that a natural number $N$ is perfect when the sum of its (positive) divisors equals $2N$. For example, 6 is a perfect number because its divisors are $1, 2, 3$ and 6 and we have: $1 + 2 + 3 + 6 = 12 = 2 \times 6$. In this part, we seek perfect numbers among the terms of the sequence $(u_{n})$ studied in Part A.

1. Verify that, for every natural number $n$, we have: $u_{n} = 2^{n}p_{n}$ with $p_{n} = 2^{n+1} - 1$.
2. We consider the following algorithm where $N, S, U, P$ and $K$ are natural numbers.

A rabbit moves in a burrow composed of three galleries, denoted $\mathrm{A}$, $\mathrm{B}$ and $\mathrm{C}$, in each of which it is confronted with a particular stimulus. Each time it is subjected to a stimulus, the rabbit either stays in the gallery where it is or changes gallery. This constitutes a step.
Let $n$ be a natural number. We denote by $a_n$ the probability of the event: ``the rabbit is in gallery A at step $n$''. We denote by $b_n$ the probability of the event: ``the rabbit is in gallery B at step $n$''. We denote by $c_n$ the probability of the event: ``the rabbit is in gallery C at step $n$''.
At step $n = 0$, the rabbit is in gallery A.
A previous study of the rabbit's reactions to different stimuli allows us to model its movements by the following system: $$\left\{ \begin{aligned} a_{n+1} &= \frac{1}{3}a_n + \frac{1}{4}b_n \\ b_{n+1} &= \frac{2}{3}a_n + \frac{1}{2}b_n + \frac{2}{3}c_n \\ c_{n+1} &= \frac{1}{4}b_n + \frac{1}{3}c_n \end{aligned} \right.$$
The objective of this exercise is to estimate in which gallery the rabbit has the greatest probability of being found in the long term.

Part A

Using a spreadsheet, we obtain the following table of values:

	A	B	C	D
1	$n$	$a_n$	$b_n$	$c_n$
2	0	1	0	0
3	1	0,333	0,667	0
4	2	0,278	0,556	0,167
5	3	0,231	0,574	0,194
6	4	0,221	0,571	0,208

It is admitted that $P$ is invertible and that $$P^{-1} = \frac{1}{121}\begin{pmatrix} 120 & 1 \\ -1 & 1 \end{pmatrix}$$
Determine the matrix $D$ defined by $D = P^{-1}AP$.
Prove that, for every natural number $n$, $A^n = PD^nP^{-1}$.
It is admitted henceforth that, for every natural number $n$, $$A^n = \frac{1}{121}\begin{pmatrix} 120 + 0{,}395^n & 1 - 0{,}395^n \\ 120(1 - 0{,}395^n) & 1 + 120 \times 0{,}395^n \end{pmatrix}$$
Deduce an expression for $a_n$ as a function of $n$.
Determine the limit of the sequence $(a_n)$. Conclude.

Part B - Study of a second medium

In this part, we consider a second medium (medium 2), in which we do not know the probability that an atom passes from the excited state to the stable state. We denote by $a$ this probability assumed to be constant. We know, on the other hand, that at each nanosecond, the probability that an atom passes from the stable state to the excited state is 0.01.

1. Give, as a function of $a$, the transition matrix $M$ in medium 2.
2. After a very long time, in medium 2, the proportion of excited atoms stabilizes around $2\%$. It is admitted that there exists a unique vector $X$, called the stationary state, such that $XM = X$, and that $X = (0.98 \quad 0.02)$. Determine the value of $a$.

Exercise 4 (5 points)

Candidates who followed the specialization course

We denote $u_n$ as the number of voles and $v_n$ as the number of foxes on July $1^{\text{st}}$ of the year $2012 + n$.

Part A - A simple model

We model the evolution of populations using the following relations: $$\left\{\begin{array}{l} u_{n+1} = 1{,}1\, u_n - 2000\, v_n \\ v_{n+1} = 2 \times 10^{-5}\, u_n + 0{,}6\, v_n \end{array}\right. \quad \text{for all integers } n \geqslant 0, \text{ with } u_0 = 2000000 \text{ and } v_0 = 120.$$

1. a. We consider the column matrix $U_n = \binom{u_n}{v_n}$ for all integers $n \geqslant 0$.
   Determine the matrix $A$ such that $U_{n+1} = A \times U_n$ for all integers $n$ and give the matrix $U_0$. b. Calculate the number of voles and foxes estimated using this model on July $1^{\text{st}}$ 2018.
2. Let the matrices $P = \left(\begin{array}{cc} 20000 & 5000 \\ 1 & 1 \end{array}\right)$, $D = \left(\begin{array}{cc} 1 & 0 \\ 0 & 0{,}7 \end{array}\right)$ and $P^{-1} = \dfrac{1}{15000}\left(\begin{array}{cc} 1 & -5000 \\ -1 & 20000 \end{array}\right)$.
   We admit that $P^{-1}$ is the inverse matrix of matrix $P$ and that $A = P \times D \times P^{-1}$. a. Show that for all natural integers $n$, $U_n = P \times D^n \times P^{-1} \times U_0$. b. Give without justification the expression of matrix $D^n$ as a function of $n$. c. We admit that, for all natural integers $n$: $$\left\{\begin{array}{lcl} u_n & = & \dfrac{2{,}8 \times 10^7 + 2 \times 10^6 \times 0{,}7^n}{15} \\[6pt] v_n & = & \dfrac{1400 + 400 \times 0{,}7^n}{15} \end{array}\right.$$ Describe the evolution of the two populations.

Part B - A model more in line with reality

We construct another model using the following relations: $$\left\{\begin{array}{l} u_{n+1} = 1{,}1\, u_n - 0{,}001\, u_n \times v_n \\ v_{n+1} = 2 \times 10^{-7}\, u_n \times v_n + 0{,}6\, v_n \end{array}\right. \quad \text{for all integers } n \geqslant 0, \text{ with } u_0 = 2000000 \text{ and } v_0 = 120.$$

1. What formulas must be written in cells B4 and C4 and copied downwards to fill columns B and C?
2. With the second model, from what year do we observe the phenomenon described (decrease in foxes and increase in voles)?

Part C

In this part we use the model from Part B. Is it possible to give $u_0$ and $v_0$ values such that the two populations remain stable from one year to the next, that is, such that for all natural integers $n$ we have $u_{n+1} = u_n$ and $v_{n+1} = v_n$? (We then speak of a stable state.)

(Candidates who have followed the specialisation course)
We define the sequence of real numbers $(a_{n})$ by: $$\begin{cases} a_{0} & = 0 \\ a_{1} & = 1 \\ a_{n+1} & = a_{n} + a_{n-1} \text{ for } n \geqslant 1 \end{cases}$$ This sequence is called the Fibonacci sequence.

1. Copy and complete the algorithm below so that at the end of its execution the variable $A$ contains the term $a_{n}$. \begin{verbatim} $A \leftarrow 0$ $B \leftarrow 1$ For $i$ going from 1 to $n$ : $C \leftarrow A + B$ $A \leftarrow \ldots$ $B \leftarrow \ldots$ End For \end{verbatim} We thus obtain the first values of the sequence $a_{n}$:
   

   $n$	0	1	2	3	4	5	6	7	8	9	10
   $a_{n}$	0	1	1	2	3	5	8	13	21	34	55

   
   
2. Let the matrix $A = \left(\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right)$.
   Calculate $A^{2}$, $A^{3}$ and $A^{4}$. Verify that $A^{5} = \left(\begin{array}{ll} 8 & 5 \\ 5 & 3 \end{array}\right)$.
3. We can prove, and we will admit, that for every non-zero natural number $n$, $$A^{n} = \left(\begin{array}{cc} a_{n+1} & a_{n} \\ a_{n} & a_{n-1} \end{array}\right)$$ a. Let $p$ and $q$ be two non-zero natural numbers. Calculate the product $A^{p} \times A^{q}$ and deduce that $$a_{p+q} = a_{p} \times a_{q+1} + a_{p-1} \times a_{q}$$ b. Deduce that if an integer $r$ divides the integers $a_{p}$ and $a_{q}$, then $r$ also divides $a_{p+q}$.

Exercise 4 (Candidates who have followed the specialization course)
Two column matrices $\binom { x } { y }$ and $\binom { x ^ { \prime } } { y ^ { \prime } }$ with integer coefficients are said to be congruent modulo 5 if and only if $\left\{ \begin{array} { l } x \equiv x ^ { \prime } [ 5 ] \\ y \equiv y ^ { \prime } [ 5 ] \end{array} \right.$. Two square matrices of order $2 \left( \begin{array} { l l } a & c \\ b & d \end{array} \right)$ and $\left( \begin{array} { l l } a ^ { \prime } & c ^ { \prime } \\ b ^ { \prime } & d ^ { \prime } \end{array} \right)$ with integer coefficients are said to be congruent modulo 5 if and only if $\left\{ \begin{array} { l } a \equiv a ^ { \prime } [ 5 ] \\ b \equiv b ^ { \prime } [ 5 ] \\ c \equiv c ^ { \prime } [ 5 ] \\ d \equiv d ^ { \prime } [ 5 ] \end{array} \right.$.
Alice and Bob want to exchange messages using the procedure described below.

• They choose a square matrix M of order 2, with integer coefficients.
• Their initial message is written in capital letters without accents.
• Each letter of this message is replaced by a column matrix $\binom { x } { y }$ deduced from the table below: $x$ is the digit located at the top of the column and $y$ is the digit located to the left of the row; for example, the letter T in an initial message corresponds to the column matrix $\binom { 4 } { 3 }$.
• We calculate a new matrix $\binom { x ^ { \prime } } { y ^ { \prime } }$ by multiplying $\binom { x } { y }$ on the left by the matrix $M$:

$$\binom { x ^ { \prime } } { y ^ { \prime } } = \mathrm { M } \binom { x } { y } .$$

	0	1	2	3	4
0	A	B	C	D	E
1	F	G	H	I	J
2	K	L	M	N	O
3	P	Q	R	S	T
4	U	V	X	Y	Z