23
$\begingroup$

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.

5 roads intersecting at a center point

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.

$\endgroup$
9
  • 3
    $\begingroup$ That's not a crossroad $\endgroup$
    – Richard
    Dec 31, 2023 at 14:40
  • 3
    $\begingroup$ @Richard For the purposes of this question, let’s define crossroads as the meeting place of the 5 roads in the diagram I provided. By the way, I didn’t pick the word crossroads, it was chosen by the person that originally made this question. I don’t like changing the wording of other people’s questions. $\endgroup$ Dec 31, 2023 at 20:38
  • 7
    $\begingroup$ Draw an arrow on each side of the coin. Spin the coin. Eventually it will fall flat with the arrow pointing at one of the roads. (Or at least at one of five 72 degree sectors representing the roads.) $\endgroup$
    – Neil
    Jan 1 at 0:35
  • 5
    $\begingroup$ Presumably I reached the crossroads via one of the five roads. Retracing my steps seems futile, as I already know what was there. So I flip once for left/right, and again for acute/obtuse angle. And I'm done. $\endgroup$ Jan 2 at 10:08
  • 4
    $\begingroup$ @Paul_Pedant you were obviously dropped from the sky in this scenario. $\endgroup$
    – Falco
    Jan 2 at 12:00

7 Answers 7

9
$\begingroup$

A solution is:

I pick a 5-sided coin like this one. I let it land vertically on one side (between two plates or other surfaces, or inside a string bag maybe) with equal probability and choose the road based on that. 😎

$\endgroup$
18
  • 3
    $\begingroup$ This doesn’t match the description given in the problem. $\endgroup$
    – Sneftel
    Dec 31, 2023 at 17:24
  • 7
    $\begingroup$ @Someone - It's quite clearly a coin. $\endgroup$
    – Richard
    Dec 31, 2023 at 20:43
  • 5
    $\begingroup$ @Sneftel I agree with you that this imaginative answer does not match the intention of my puzzle but I see nothing in the wording of my puzzle that would disallow this solution. $\endgroup$ Dec 31, 2023 at 21:23
  • 4
    $\begingroup$ @LamarLatrell I like everything about this answer (and the user’s reputation) but I will hold off before accepting an answer since this question is generating a lot of answers. $\endgroup$ Dec 31, 2023 at 21:43
  • 3
    $\begingroup$ Creative, but this requires that all 5 edges are equiprobable, which I don't think we can guarantee. I think this unfairly extrapolates the ability to pick a coin with specified binary probability to the ability to have a specified 5-way probability. How do you know each edge comes up 20% of the time? That is not a defined feature of the coin you're choosing to flip, only the probability of heads is defined. This erroneously concludes that since there are 5 edges on the coin, they must each come up equally often, despite nothing actually requiring that $\endgroup$ Jan 2 at 14:26
23
+50
$\begingroup$

I can do it in

three flips of two coins by

Have one coin that shows heads with probability $\frac 15$ and one that shows heads with probability $\frac 12$. Flip the first coin. If it shows heads you choose the first road. If the first coin shows tails two flips of the fair coin selects between the other four.

To show we can't do it in less

With only two flips you have a coin that you flip first. It can give only two results. For each result you must choose a coin for the second flip but that gives no information. You flip that one and have only four possible results at most, so you can't choose from five roads.

$\endgroup$
3
  • 2
    $\begingroup$ Bonus question: Can you do it with just one coin? $\endgroup$ Dec 31, 2023 at 6:20
  • 2
    $\begingroup$ @WillOctagonGibson: I saw that and so far cannot, but I also cannot prove it impossible. Still thinking on that. $\endgroup$ Dec 31, 2023 at 6:24
  • 1
    $\begingroup$ I don't understand why this isn't the accepted answer. $\endgroup$
    – Plop
    Jan 3 at 13:17
22
$\begingroup$

Bonus question

What if there is a single coin? There is a simple way to prove that to obtain 5 equally probable choices is...

possible. As it is possible for any number of choices.

And here is why

With $N$ flips you get $2^N$ outcomes.
The probability of each outcome depends on the number of heads. The probability $p_h$ to get get one specific outcome with $h$ heads is
$p_h = (P^h (1-P)^{N-h}$, where $P$ is the probability to get heads in a single flip.

The number of outcomes with $h$ heads is given by the binomial coefficients.
$a_h = C(N,h)$.
For $N=6$ the number of outcomes by heads count is
$a_h = [1, 6, 15, 20, 15, 6, 1]$.

The trick is to distribute the outcomes evenly not in 5 groups but in 4. We can make 4 equivalent groups by taking the following counts: $b_h = [0, 1, 3, 5, 3, 1, 0]$.
This means take 1 outcomes with 1 heads, 3 outcomes with 2 heads, 5 with 3 heads, etc.
With four such groups you use up most but not all of the outcomes. The remaining counts are as follows.
$c_h = a_h - 4 b_h = [1, 2, 3, 0, 3, 2, 1]$
One outcome with no heads, 2 outcomes with 1 heads, etc... From this you form the 5th group.

The four groups with counts $b_h$ sum up to the same probability. But what about the probability of the last group with counts $c_h$? You can adjust that probability by adjusting $P$. You just need to solve the following.
$\sum p_h c_h = 0.2$ (i.e. 1/nb. of choices)

This might not solve if N is too small. $N=6$ is just large enough.

This amounts to solving a polynomial of degree 6. I am not sure whether there is a way to solve it analytically given the symmetry. Anyway, I solved it numerically.
$P = 0.567363422297041...$

With this $P$ the probability of an outcome in the 5th group is 20%. And since the first four groups are identically composed, their probability is ${1 \over 4} 80\% = 20\%$.

This works for any number of choices. The size of the remainder group grows linearly with N while the total number of outcomes grows exponentially. As soon as the size of the last group is below $2^n \over choices$ there is a solution to the equation.

With a computer I can improve this result.

enter image description here

With five flips and a coin bias at $P = 0.7236067977499784$ you can group the outcomes in five groups that sum up to exactly 20%.

In the table, h is the number of heads, p_h the probabiliy of one outcome with h heads, b_hg are the number of outcomes of each heads count by group, each row is a group, and the value at the right is $\sum p_h b_{gh}$ which is the total probability of each group. It always sums to $0.2$. The bottom row is the sum, it matches the binomial coefficients of the distribution of the outcomes.

The value of P is the solution of $P^5 + (1-P)^5 = 0.2$.

Wolfram alpha solves it as $5 + \sqrt{5} \over 10$

$\endgroup$
3
  • 3
    $\begingroup$ Well done. I was looking for a specific value for $P$ and think I ruled out all rationals plus $\phi$, the golden ratio. Using continuity to prove existence is a better approach. $\endgroup$ Jan 1 at 4:29
  • 2
    $\begingroup$ Actually, the $p_h$ increase with a factor $\phi+1$. You were on the right track. $\endgroup$
    – Florian F
    Jan 1 at 20:41
  • $\begingroup$ So, your coin getting HHHHH or TTTTT is one road. This is obvious. What about the rest? HHHHT and many other combinations is second road, HHHTH + etc is third and so on? $\endgroup$ Jan 3 at 9:52
6
$\begingroup$

Sitting in the middle of the road and spinning a round coin and going down road above the heads or below the tails that way the direction is always pointing the same whether heads or tails.

$\endgroup$
1
  • $\begingroup$ this won't be completely random because it'll be affected by the ripple affect... due to a slightly larger amount in traffic one way that direction could be influenced to be chosen more often due to warps and ruts in the road... but to be honest if you are in this saturation it's probably because you're lost and need to find civilization so... $\endgroup$
    – AnimeNate
    Dec 31, 2023 at 22:03
3
$\begingroup$

This is not an original answer. It only adds how to derive @Florian F's 5-toss answer analytically.

Let $B = P - \frac 1 2$ be the coin's bias.

We'll reference the 5 groups of outcomes by the numbers of outcomes with 5,4,3,2,1 and 0 heads, respectively. The groups are then 1-0-0-0-0-1, 0-1-3-3-1-0 (2x), 0-2-0-4-1-0 and 0-1-4-0-2-0.

To get the right probability for the 1-0-0-0-0-1 group we need to solve $\left (\frac 1 2 + B\right )^5 +\left (\frac 1 2 - B\right )^5=\frac 1 5$. Because odd powers of $B$ cancel this simplifies to $\frac 1 {2^4} + \frac {10} {2^2} B^2 + 5 B^4 = \frac 1 5$. Substituting $b=B^2$ yields a quadratic equation $b^2 + \frac 1 2 b = \frac 1 {25} - \frac 1 {80}$ with solutions $b=-\frac 1 4 \pm \frac 3 {10}$ of which only the positive one $b=\frac 1 {20}$ is usable because we need to take its square root to obtain $B=\frac 1 {2\sqrt 5}$

It remains to show that the four other groups all have the same probability. The difference between 0-1-3-3-1-0 and 0-2-0-4-1-0 is $P^4Q-3P^3Q^2+P^2Q^3 = P^2Q (P^2-3PQ+Q^2)$ where $Q=1-P$. The difference between 0-1-3-3-1-0 and 0-1-4-0-2-0 is $P^3Q^2-3P^2Q^3+PQ^4 = PQ^2 (P^2-3PQ+Q^2)$. It will suffice to establish $P^2-3PQ+Q^2=0$. Substituting $P,Q$ using $B$: $\left(\frac 1 2 + B\right)^2 - 3 \left(\frac 1 2 + B\right)\left(\frac 1 2 - B\right)+\left(\frac 1 2 - B\right)^2 = -\frac 1 4 + 5B^2 = -\frac 1 4 + 5b = 0$.

A biased coin with probabilities $\frac 1 2 \pm \frac 1 {2\sqrt 5}$ therefore "works".

$\endgroup$
-1
$\begingroup$

I believe it can be done with a single unbiased coin

Stand on the first road. Throw a coin. If it lands heads then move 2 roads clockwise, otherwise if it lands tails then move 3 roads clockwise. Repeat this $N$ times to obtain your final road. In other words we are computing $(2H+3T) \mod 5$, where $H$ is the number of heads and $T$ is the number of tails thrown with $N=H+T$. I chose $2$ and $3$, because they are small and relatively prime to each other giving you a uniform distribution over final results. Now we just need to find a good value for $N$. I found that $N=50$ is the smallest value that works well. I wrote some code that simulates the above and ran it for 1 million simulations. Here are the counts for each result: 0: 199725, 1: 199580, 2: 200235, 3: 200088, 4: 200372. The average deviation from the expected 200000 is only 278, which is just 0.1% from 200000.

UPDATE:

Will Octagon Gibson has kindly pointed out that this procedure works with 0/1 steps too, which makes it even simpler. So if the coin lands tails then move by 1 road, otherwise stay where you are.

An alternative solution

is to use an unbiased coin to simulate any biased coin. This way we can choose any solution posted here and simulate it with a single unbiased coin. If there are multiple coins involved then just repeat the simulation for each coin.

$\endgroup$
5
  • 1
    $\begingroup$ Your first procedure with a single unbiased coin is virtually perfect for randomly selecting a road. For N=50, moving 0 or 1 roads gives EXACTLY the same results as moving 2 or 3 roads because at each step the 2/3 method will move exactly two roads further than the 0/1 method; in total moving exactly 50x2=100 roads further which is exactly 20 extra laps around the five roads. $\endgroup$ Jan 3 at 20:28
  • $\begingroup$ Nice observation. Ok let's go with the 0/1 moves - even simpler. I believe this answers the puzzle, including the bonus question. $\endgroup$ Jan 3 at 23:11
  • $\begingroup$ Why the minuses? Please explain. My answer solves the problem. $\endgroup$ Jan 4 at 11:44
  • $\begingroup$ Dmitry, I upvoted your answer. $\endgroup$ Jan 4 at 11:47
  • $\begingroup$ yep I know you did and I thank you for that. I don't understand why others have downvoted me :( $\endgroup$ Jan 4 at 12:44
-2
$\begingroup$

1 coin, 1 flip

Number the roads, then flip a single coin over soft mud or sand. Assign a range of possible 'angles of entry' to one each of the five roads.

  • Flat - Road 1
  • Almost flat - Road 2
  • About 45 degrees - Road 3
  • Mostly upright - Road 4
  • Upright - Road 5

As you can see from the example below, the coin has landed 'mostly upright', so you would take Road #4.

enter image description here

$\endgroup$
5
  • 2
    $\begingroup$ It might take you a while to work out precisely what angles represent a totally random 1:5 chance... $\endgroup$
    – Richard
    Dec 31, 2023 at 20:41
  • 2
    $\begingroup$ +1 Cool answer despite it being challenging to implement. $\endgroup$ Dec 31, 2023 at 21:00
  • $\begingroup$ "You would like to choose randomly, with equal probability for each road." is not satisfied here. $\endgroup$
    – Nij
    Dec 31, 2023 at 21:47
  • 2
    $\begingroup$ @nij - As I've said, you'd need to work out precisely what range of angles would meet the requirement for random chance. $\endgroup$
    – Richard
    Dec 31, 2023 at 21:53
  • 3
    $\begingroup$ "Mostly upright" is not an angle though, it's a subjective observation. Unless you are allowing other equipment for their random determination, in which case you just create RNG devices and also flip a coin for no reason. $\endgroup$
    – Nij
    Jan 1 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.