**Solution**.

We heard from Chris Bistryski (PMP), Robert Noll (PMP), and Randy Schwartz (Schoolcraft College) on this one. The first construction below, of a single coin that works in six flips, was submitted by Chris.

Note that it is just the number of heads and tails in a given sequence that determines the probability of that sequence, not their order. In other words, all sequences of six heads and tails with the same number of heads have the same probability, regardless of the value of $p$. Counting, there is just one sequence with six heads, six with five heads, 15 with four heads, 20 with three heads, 15 with two heads, six with one occurrence of heads, and one with none. Therefore, we can make four disjoint collections of sequences, each of which contains one with five heads, three with four heads, five with three heads, three with two heads, and one with a single occurrence of heads. Regardless of $p$, each of these collections will have the same probability of occurring.

Calculating, this probability is

$${p}^{5}(1-p)+3{p}^{4}(1-p{)}^{2}+5{p}^{3}(1-p{)}^{3}+3{p}^{2}(1-p{)}^{4}+p(1-p{)}^{5}.$$

By simplifying this expression into a sixth-degree polynomial, you can find that there is a unique value of such that this probability comes out to exactly $1/5$; it can be approximated numerically as $p\approx 0.4326366$. It turns out also to be possible to find an exact expression for this $p$ in terms of square roots and cube roots, for example using symbolic mathematics software; in case you are curious, it is

$$p=\frac{1}{2}(1-\sqrt{1+\frac{4}{3}(-1-\sqrt[3]{\frac{20}{2+3\sqrt{6}}}+\sqrt[3]{\frac{4+6\sqrt{6}}{5}})}).$$

Therefore, if you have a coin with this value of $p$, you can assign one of the five roads to each of these four equally likely collections of outcomes of six flips, and the remaining road to all of the other outcomes. Since each of the first four has a probability of $1/5$, the remaining outcome must have whatever probability is left over, i.e. 1 – $4(1/5)=1/5$ as well. Hence, each of the five options will be chosen with equal probability.

As for the second part, the Problem Warden is not aware of any solution that works with fewer than six flips, and suspects that six is the minimum possible, but does not have a complete proof for that statement. Chris was able to successfully argue that his scheme could not work with five or fewer flips, because no four sets of outcomes that are equally likely regardless of the value of $p$ can each have probability higher than 19%. However, that argument does not establish definitively that there can’t be some particular value of $p$ for which there just happen to be five sets of outcomes that are equally likely — sets that might not correspond with each other in terms of the numbers of heads in different sequences as the ones in Chris’s strategy do. If anyone discovers such a configuration or a proof that it can’t exist for five of fewer flips, please send it in!

We are able, however, to show that it can’t be done with just *three* flips of any unfair coin: there are only eight outcomes from three flips, so two of the groups of outcomes that are assigned to roads must consist of just a single outcome. However, assuming by symmetry that , the outcome TTT has the unique largest probability. Hence it can’t be one of the single outcomes with probability $1/5$, since no other outcome has equal probability. But therefore its probability is larger than $1/5$, which means it can’t be part of any group, so no assignment is possible.

That leaves us with the third part. No matter what coins you have, you’ll always have to make at least three flips, because there are only four different outcomes for two flips (HH, HT, TH, and TT), and you can’t choose among five options with only four possibilities. On the other hand, Randy points out that with one fair coin and one coin with a probability of heads equal to $1/5$, you can make a fair choice in only three flips: assign one road to heads on the unfair coin and flip that first; if it comes up tails, use the fair coin twice to choose fairly among the other four roads.

But we can’t make a fair choice among five roads with one flip each of all unfair coins with heads probabilities , by the same argument as in the single-coin case. In this situation, TTT is still the outcome with the unique largest probability, leading to the same obstacle as before. That might seem to establish that you can’t choose in three flips with only unfair coins, but actually you can!

The secret is to have more than three types of coins available, and choose which coin to use based on the outcomes of the earlier flips. For example, you can do it using coins with heads probabilities $2/5$, $\sqrt{1/2}$, $5/12$, $1/5$, and $3/7$, as follows. First flip the $2/5$ coin. If it comes up heads, use the $\sqrt{1/2}$ coin to choose one of two roads fairly (since such a coin comes up HH exactly half of the time, and some other way the the other half of the time). If it comes up tails, we have to choose one of the other three roads fairly; call them $R$, $S$, and $T$. Flip the $5/12$ coin. If it comes up heads, flip the $1/5$ coin and choose $R$ on heads and $S$ on tails. If the $5/12$ coin came up tails (a $7/12$ chance), flip the $3/7$ coin, but this time choose $R$ on heads and $T$ on tails. For these two flips, you will choose road $R$ exactly $\frac{5}{12}\cdot \frac{1}{5}+\frac{7}{12}\cdot \frac{3}{7}=\frac{1}{3}$ of the time, and similarly for roads $S$ and $T$. If you find a method to choose fairly among five roads in only three flips with fewer different probabilities of coins, send that in, too.

Incidentally, Robert Noll constructed a set of just three unfair coins with which the choice can be made in four flips: The heads probabilities are $2/5$, $1/3$, and $\sqrt{1/2}$. You start the same way as in the previous construction: if the $2/5$ coin comes up heads, choose between two of the roads using the $\sqrt{1/2}$ coin twice. If the $2/5$ coin comes up tails, flip the $1/3$ coin. If it comes up heads, that corresponds to one of the remaining three roads; if tails, you choose fairly between the other two with two flips of the $\sqrt{1/2}$ coin.