A bubble jumps between the vertices of the square $A B C D$, starting from vertex $A$. With each jump, it has a $\frac{1}{2}-\frac{1}{2}$ probability of landing on one of the adjacent vertices. The bubble stops when it reaches the last vertex it hasn't visited yet. Determine the probability that each vertex will be the last one visited.
# I. solution. 1

Due to symmetry, the probability we are looking for is the same for vertices $B$ and $D$; let this common value be $p$, and the probability for vertex $C$ be $q$. It is easily verifiable that the bubble will, with probability 1, eventually reach every vertex, and thus $2p + q = 1$. Indeed, in 3 consecutive jumps, there is a $1/4$ probability that it will move in the same direction all the time - and thus visit every vertex - so the probability that after $3k$ jumps it has not visited every vertex is at most $(3/4)^k$, which tends to 0 as $k \rightarrow \infty$.

Now we will show that $p = q$, for which we examine the probability that $C$ will be the last visited vertex. By symmetry, we can assume that after the first jump, it is at $B$. We need to determine the probability that it will reach $D$ before $C$. If it reaches $D$ before $C$, it must also visit $A$ in between, so precisely those jump sequences satisfy the condition where the sequence of jumps starting from $B$ ends with a jump to $C$, i.e., to an adjacent vertex. By symmetry, this probability is $p$, so indeed $q = p$.

Thus, $p = q = 1/3$, and the sought probability for each of the three vertices is $1/3$.

II. solution. The probability that $B$ will be the last is the same as the probability that $D$ will be, since the square is symmetric about the $AC$ diagonal.

Let's see what the probability is that the $D$ vertex will be the last. For this, it is necessary that it first step to $B$, then jump between $A$ and $B$, and finally step to $C$. Then it is certain that the $D$ vertex will be the last (assuming that the jumping eventually ends - see the proof in the first solution). So the possible paths look like this: $A-B-C-\ldots, A-B-A-B-C-\ldots, A-B-A-B-A-B-C-\ldots, \ldots$. Their probabilities are, respectively:

$$
\left(\frac{1}{2}\right)^{2}=\frac{1}{4}, \quad\left(\frac{1}{2}\right)^{4}=\left(\frac{1}{4}\right)^{2}, \quad\left(\frac{1}{2}\right)^{6}=\left(\frac{1}{4}\right)^{3}
$$

and so on, each being $\left(\frac{1}{2}\right)^{2}=\frac{1}{4}$ times the previous. The sum of these probabilities is:

$$
\frac{1}{4}+\left(\frac{1}{4}\right)^{2}+\left(\frac{1}{4}\right)^{3}+\ldots+\left(\frac{1}{4}\right)^{n}=\frac{\frac{1}{4} \cdot\left(\left(\frac{1}{4}\right)^{n}-1\right)}{\frac{1}{4}-1}
$$

Since $\left(\frac{1}{4}\right)^{n} \rightarrow 0$ as $n \rightarrow \infty$, the limit of the sum of the probabilities as $n \rightarrow \infty$ is

$$
\frac{\frac{1}{4} \cdot(0-1)}{\frac{1}{4}-1}=\frac{-\frac{1}{4}}{-\frac{3}{4}}=\frac{1}{3}
$$

Similarly, the probability that the $B$ vertex will be the last is $\frac{1}{3}$. Thus, the probability for the $C$ vertex is $P_{C}=1-P_{B}-P_{D}=$ $1-\frac{1}{3}-\frac{1}{3}=\frac{1}{3}$.

Remark. Some wrote equations for $P_{D}$. If the bubble jumps from vertex $A$ to $D$, then it is certain that $D$ will not be the last. If it jumps to $B$ and then to $C$, then it is certain that $D$ will be the last. If it jumps back to $A$ after $B$, then from there on, the probability is again $P_{D}$. Adding these up:

$$
P_{D}=\frac{1}{2} \cdot 0+\frac{1}{2} \cdot \frac{1}{2} \cdot 1+\frac{1}{2} \cdot \frac{1}{2} \cdot P_{D}
$$

from which

$$
\frac{3}{4} P_{D}=\frac{1}{4} \quad \text { and thus } \quad P_{D}=\frac{1}{3}
$$

follows.[^0]

[^0]:    ${ }^{1} \mathrm{~A}$ The solution can be found on the www.komal.hu website. Solutions to the problems are generally available on our website a few days after the deadline.