Some time ago I took part in an entry mathematics exam to a masters programme of one of the universities in my country. I solved most of the tasks, but the last one. Since the admission committee refused to publish any solution, even after the examination session has already finished, I decided to publish a modified version of the exam task (so that the original task is unrecognizable from what I wrote) here, in hope to at least get some advice or help on how to attempt this question, since it really interests me on what are the possible ways to solve it.
The body of the task is as follows:
There are 5 cities $A$, $B$, $C$, $D$ and $E$. The Traveller is initially located in city $A$. We know that some cities are connected (so that one can travel by the path in any direction), but there’s no information on which exactly.
Let us say that the Traveller can go along any path, that connects to the current city of their visit. Assuming that city $A$ has at least one connection to some other city, we know that after five consecutive iterations, the probability for the Traveller to occur in city $A$ is $\frac{3}{8}$ and the probability for them to occur in city $B$ is $\frac{5}{8}$. What should be the minimal number of connections between the cities, for the given probabilities to hold true?
My “attempt”:
Initially I thought that we can try to depict the collection of cities as some kind of a graph, defined by a transition matrix. Next I thought of a possibility to apply the principle of limiting probability in Markov chains with no self-loops, but essentially, as we do not know, which cities are connected (except for the fact that city A has at least one connection), it was quite hard for me to design some appropriate transition scheme, so that to understand how the given probabilities can form.
After that I thought, that probably, as we are only given that at the last step we either occur in $A$ or $B$ with both respective probabilities having an odd numerator, then we have to probably somehow rely on the fact, that we need to have odd path loops in our graph of connections, and thus the minimal number of connections should be odd, but this didn’t lead me anywhere at the end.
I still think that this task can be attempted by considering a Markov chain as the descriptive model, but I am not exactly sure how to apply it here.
Any ideas, hints; basically any help will be much appreciated.
Thank you in advance!
I am afraid your "modified version of the exam task" does not make sense.
Note that the Traveller must end up at either $A$ or $B$ since $\frac38+\frac58=1.$
$A$ must connect some city; otherwise the Traveller cannot end up at $B$.
Suppose $A$ connects city $x$. Since with path $A\to x\to A\to x\to A\to x$ the Traveller will end up at $x$, $x$ must either be $A$ or $B$. We do not consider $A$ connects $A$. So $x$ must be $B$. That is, $A$ connects only to $B$.
There are two cases.
The Traveller will always end up at $B$.
Suppose $B$ connects to city $y$ that is not $A$. Towards a contradiction suppose $y$ connects city $z$ that is not $B$. $\ z$ is not $A$ either since $A$ connects $B$ only but $z$ connects $y$. With path $A\to B\to y\to z\to y\to z$, the Traveller will end up at $z$, which must be either $A$ or $B$. That is a contradiction. So $y$ connects only to $B$.
Since $y$ is arbitrary, we get a star graph with $B$ at the center. After $1$, $3$ or $5$ iterations the Traveller will always occur at $B$. In particular, the Traveller will always end up at $B$.
In all cases, the Traveller will always end up at $B$, which is not true.
The reasoning above shows that it is not possible for any number of cities such that a Traveller starting at $A$ will after 5 iterations end up at either $A$ or another fixed city each with nonzero probability.