13. Small Tetris. A tall rectangle of width 2 is open at the top, and $\Gamma$-trimino (see figure) falls into it in a random orientation.

a) (from 9th grade. 3 points). $k$ trimino have fallen. Find the expected height of the resulting polygon.

b) (from 10th grade. 6 points). 7 trimino have fallen. Find the probability that the figure formed by the trimino will have a height of 12.
Solution. a) Let the random variable "height of the resulting polygon" be denoted by $X$. Clearly, $X=2 k-\left(I_{2}+I_{3}+\ldots+I_{k}\right)$, where $I_{j}$ is the indicator of the event "trimino with numbers $j$ and $j-1$ form a block of height 3". This can only happen in two cases, as shown in the left figure. The probability of this is $\frac{1}{8}$. Thus, $\mathrm{E} I_{j}=\frac{1}{8}$. Therefore, $\mathrm{E} X=2 k-\frac{1}{8}(k-1)=\frac{15 k+1}{8}$.

b) Let $u_{k, n}$ and $d_{k, n}$ be the probabilities that a figure consisting of $k$ fallen triminos reaches a height of $n$, and the top trimino is oriented with the protrusion facing up (down). The sum of these probabilities, i.e., the probability that the height of the polygon from $k$ triminos is $n$, we denote by $p_{k, n}$. Then

$$
u_{k, n}=\frac{1}{2} p_{k-1, n-2}, \quad d_{k, n}=\frac{1}{4} u_{k-1, n-1}+\frac{1}{4} u_{k-1, n-2}+\frac{1}{2} d_{k-1, n-2}
$$

The total probability is

$$
p_{k, n}=u_{k, n}+d_{k, n}=\frac{1}{2} p_{k-1, n-2}+\frac{1}{2} d_{k-1, n-2}+\frac{1}{4} u_{k-1, n-2}+\frac{1}{4} u_{k-1, n-1}=p_{k-1, n-2}-\frac{1}{4} u_{k-1, n-2}+\frac{1}{4} u_{k-1, n-1},
$$

from which $p_{k, n}=p_{k-1, n-2}+\frac{1}{8} p_{k-2, n-3}-\frac{1}{8} p_{k-2, n-4}$.

For the start of the recursion, we set: $p_{0,0}=p_{1,2}=1$, and also $p_{k, n}=0$ for $n>2 k$. We get: $p_{2,3}=p_{1,1}+\frac{1}{8} p_{0,0}-\frac{1}{8} p_{0,-1}=0+\frac{1}{8}-0=\frac{1}{8}, p_{2,4}=p_{1,2}+\frac{1}{8} p_{0,1}-\frac{1}{8} p_{0,0}=1+0-\frac{1}{8}=\frac{7}{8}$, and so on. The calculation can be performed, for example, using Excel (see the example in the figure). For convenience, we can introduce $n=-1$, setting the corresponding probabilities to zero. In the figure, this corresponds to the empty column C. Then it will remain to fill in the corresponding formula only for the cells starting from $k=2, n=3$ (G5 in our example).

At the intersection of row 7 and column 12, we find: $p_{7,12} \approx 0.133$.

Answer: a) $\frac{15 k+1}{8}$; b) approx. $0.133$.

IX Olympiad in Probability Theory and Statistics for Schoolchildren. Correspondence Round.

© Laboratory of Probability Theory and Statistics, MCCME, 2015-2016