To allow new users to solve this puzzle and earn reputation points, I encourage all users whose reputation is 200 or more to not post an answer until 48 hours after this question is posted. Thank you!
You are at a crossroads with five roads leading away from it, and you don't know which direction to go. You would like to choose randomly, with equal probability for each road.
If your only way of making random choices is to flip a fair coin (one that could come up heads or tails with equal probability), you could assign one of the roads to each of the sequences HHH, HHT, HTH, HTT, and THH. Those outcomes are all equally likely, so you know that if you flip three times and choose the corresponding option, each one of them will have an equal chance. The problem is that there are three outcomes that are not assigned to any road, so if one of those three comes up you will have to try again. Therefore, it could take you arbitrarily long to make your decision, if you are unlucky and keep getting one of the unassigned outcomes.
You don't have all day to stand around, so you'd like a better method. But it turns out that people have proved there is no process with a single fair coin that is guaranteed to finish in a finite amount of time and choose one of five options with equal probability.
Now suppose you are allowed to have more than one type of coin, each one marked with the probability that it comes up heads. What's the fewest flips you would need to choose your direction? How many coins do you need, and what's a set of probabilities for the coins that lets you do it in that minimal number of flips?
Bonus question: Can you do it with just one coin?
Clarification of bonus question: In other words, does there exist a single coin with a certain fixed probability (you can pick the probability) of landing heads when randomly flipped such that there is a process that is guaranteed to allow you to select one of the roads randomly (each with probability 1/5) with a finite number of coin flips?
This puzzle comes from THE PRISON MATHEMATICS PROJECT NEWSLETTER FALL 2023 - ITERATION 7
I created the roadway diagram.