On a circuit board, chips $P, Q, R, S$ are connected by wires in every possible way. For economic reasons, the $Q S$ wire runs underneath, while the others run above. An electron starts wandering from $P$ in such a way that at each chip, it chooses one of the 3 possible directions with equal probability. What is the probability that the electron first reaches the bottom side of the circuit board only on the 1995th step?
The electron first reaches the bottom of the circuit board precisely at the 1995th step if, within the first 1994 steps, it reaches the $Q$ or $S$ chip without passing through the $Q S$ wire, and then takes the $Q S$ path at the 1995th step. Therefore, if $p_{i}, q_{i}, r_{i}, s_{i}$ denote the probabilities that the electron reaches the $P, Q, R, S$ chips, respectively, within the first $i$ steps while avoiding the $Q S$ path, then the probability sought in the problem is given by $\left(q_{1994}+s_{1994}\right) / 3$. Clearly,

$$
p_{0}=1, \quad q_{0}=0, \quad r_{0}=0, \quad s_{0}=0
$$

Furthermore, by the theorem of conditional probability,

$$
p_{i+1}=\frac{q_{i}+r_{i}+s_{i}}{3}, \quad q_{i+1}=\frac{p_{i}+r_{i}}{3}, \quad r_{i+1}=\frac{p_{i}+q_{i}+s_{i}}{3}, \quad s_{i+1}=\frac{p_{i}+r_{i}}{3}
$$

It is useful to introduce the notations $a_{i}=p_{i}+r_{i}$ and $b_{i}=q_{i}+s_{i}$, with which the sought probability is $b_{1994} / 3$, and from the above,

$$
a_{0}=1 \quad \text { and } \quad b_{0}=0, \quad \text { and } \quad a_{i+1}=\frac{a_{i}+2 b_{i}}{3} \quad \text { and } \quad b_{i+1}=\frac{2 a_{i}}{3} \text {. }
$$

From this, a linear recurrence relation for $a_{i}$ is obtained: $a_{i+1}=\frac{1}{3} a_{i}+\frac{4}{9} a_{i-1}$ with initial conditions $a_{0}=1$ and $a_{1}=\frac{1}{3}$. We seek $a_{i}$ in the form $c_{1} x_{1}^{i}+c_{2} x_{2}^{i}$ with suitable constants $c_{1}$ and $c_{2}$ and the roots $x_{1,2}$ of the equation $x^{2}=\frac{1}{3} x+\frac{4}{9}$, since every sequence of this form satisfies the recurrence relation. The constants are determined from the initial conditions, leading to a linear system of equations that can be uniquely solved; the final result is that

$$
a_{i}=\frac{3}{\sqrt{17}}\left[\left(\frac{1+\sqrt{17}}{6}\right)^{i+1}-\left(\frac{1-\sqrt{17}}{6}\right)^{i+1}\right]
$$

Thus, the probability sought in the problem is

$$
P=\frac{b_{1994}}{3}=\frac{2 a_{1993}}{9}=\frac{2}{3 \sqrt{17}}\left[\left(\frac{1+\sqrt{17}}{6}\right)^{1994}-\left(\frac{1-\sqrt{17}}{6}\right)^{1994}\right]=2.42 \cdots \times 10^{-138}
$$

Based on the work of Márton Makai (Debrecen, Fazekas M. Gymnasium, III. grade)