Last week I provided a logic puzzle involving finding a substitute system to dice based on coins, and also mentioned that I’m interested in solutions that are not based on coins. You can find details about the puzzle here.
I got many interesting ideas and would like to thank all those who sent solutions, whether as comments to the blog entry, via e-mail, in a private SQL MVPs newsgroup, or in the pub.
I got solutions from: Pesomannen, mjswartd2l, Marcello Poletti (Marc), Plamen Ratchev, benflanaghan, Joe Celko, Michael Coles, Regan Wick, Peter DeBetta, Jonathan Kehayias, Steve Kass, Geoff N. Hiten, Hugo Kornelis, and Lilach Ben-Gan.
I won’t cover all solutions here—there are simply too many—rather the ones I liked best. I’ll start with the solutions that are based on coins, since this was the original puzzle. I’ll follow with some interesting ideas that are not based on coins.
Solutions Based on Coins
1. Coins to mimic numbers in base 2
Suggested by: Pesomannen, mjswartd2l, Geoff N. Hiten
You can represent numbers in base 2, where each digit, or bit, has a position reflecting a different power of 2, and a state 1 (on) or 0 (off). You can then use coins to represent the digits of a number in base 2 (say heads means on and tails means off). Since you need at least six different numbers for the six different states of a die, you would need three digits. With three digits in base 2 you can represent numbers in the range 0 through 7. You ignore the values 0 (all tails – TTT) and 7 (all heads – HHH), and consider only 1 through 6 (HHT, HTH, HTT, THH, THT, TTH).
You can mimic the three digits in base 2 either with one or with three coins. If you want to use only one coin, you simply flip it three times repeatedly, each flip representing a different power of 2 (1, 2, 4). Then sum all values where you got heads. But with this system, it takes a long time each round to produce the two values of the dice. You can imagine that it can take away a lot of the fun in the backgammon game, which is the reason for looking for the dice substitute.
Another option is to use three coins, and throw them all at once on the table, after shaking them up in a cup or between the palms of your hands. Of course, with the three coins approach, you need a way to distinguish between the coins. You can either use three different types of coins, or use three coins of the same type, but somehow mark them differently (say, with a pen or pencil).
The downside of this approach is that there are states that you need to ignore, and then retry. In average, this happens in every one of four cases.
2. Solution based on an algorithm by Knuth & Yao
Suggested by: Plamen Ratchev
You flip a coin several times repeatedly and on heads/tails take a different path in the diagram shown in Figure 1. On heads take the right branch and on tails take the left branch.
The third coin flip needs to have a loop back to the second coin flip to both eliminate the additional outcomes and to provide fair chances for all numbers. You can find an online reference to this method with implementation here.
The nice part about this method is that it relies on a single coin. But you need to be familiar with it, and memorize the figure so that you will be able to draw it on a piece of paper and use it when in need. I think that once you get familiarized with the algorithm and the figure, it’s not that hard to remember, but you need to know it.
Considering our pub scenario that started the whole thing, since this method requires you to flip a coin repeatedly several times, it takes a while until you get the two dice values. It’s more convenient in a pub to use a solution that doesn’t take a long time.
3. Solution Based on Patterns
Suggested by: Steve Kass
This requires successive flips, and it can take any number of flips to result in an answer (but rarely a large number):
Flip one coin repeatedly until one of the following eight patterns occurs. The die roll and probability of each is shown.
HHTHH (die roll is 1) -- pattern appears first with probability 1/6
HHTHT (die roll is 2) -- pattern appears first with probability 1/6
HHTTH (die roll is 3) -- pattern appears first with probability 1/6
HHTTT (die roll is 4) -- pattern appears first with probability 1/6
HTHHH (die roll is 5) -- pattern appears first with probability 1/12
HTHHT (die roll is 5) -- pattern appears first with probability 1/12
HTHTH (die roll is 6) -- pattern appears first with probability 1/12
HTHTT (die roll is 6) -- pattern appears first with probability 1/12
Also with this solution, the upside is that you need only one coin, and the downside is that it takes a long time to get the two dice values.
4. Solution Based on Order
Suggested by: Dejan Sarka, Regan Wick, Steve Kass
This is one of the two solutions based on coins that I like best, because it requires only one throw of coins, with no cases that need to be ignored, resulting in retrying throws.
Use three different types of coins, or three coins of the same type that are marked differently. I’ll call them A, B and C for the purposes of explaining the logic. Designate a number in the range 1 trough 6 to each of the six possible orders of the letters (3! = 6), e.g.,
1 – ABC
2 – ACB
3 – BAC
4 – BCA
5 – CAB
6 – CBA
Shake the coins up in a cup or between the palms of your hands, and throw them on the table. Determine the order of the coins based on their x coordinates (say, lowest wins). In case of ties in the x coordinates, use the lowest y coordinate as a tiebreaker. In case of ties in both x and y coordinates (meaning coins are on top of each other), use the lowest z coordinate as a tiebreaker.
As an example, consider the state of the coins in Figure 2.
The order of the coins is ACB because A and C share the same x coordinates, but A has a lower y coordinate than C. Both A and C have lower x coordinates than B. And remember earlier you designated the value 2 to the order ACB, so the state of the coins in Figure 2 represents the value 2.
Of course there’s some chance for arguments between the players regarding which coin appears before another on any given axis (besides z, naturally). But in case of doubt, you can always decide on a rule that says that you then rely on the tiebreaker.
I find this solution beautiful. While sitting in another pub (this time it was Vienna), I gave this puzzle to my friends, among them Dejan Sarka, Fernando G. Guerrero, and Herbert Albert. I was quite impressed when Dejan came up with this idea after only a few minutes, and after quite a few pints, mind you!
5. Solution Based on One Coin with Three Evenly Spaced Marks on Each Side
Suggested by: Michael Coles, Hugo Kornelis
Use some marking tool (pen, pencil or other) to mark a coin with three marks on one side, and three on the other side, evenly spaced. Designate each mark with a value: 1, 2, 3, 4, 5, and 6. Flip the coin and let it fall on a sheet of paper. Choose the value on the side facing up whose mark has the lowest x coordinate, and in case of ties choose the one with the lowest y coordinate. At most two can have the same x coordinate, in which case they will have different y coordinates.
As an example, consider the state of the coin in Figure 3.
The side facing up (heads in this case) has the values 1, 2 and 3. 1 and 3 have lower x coordinates than 2, but since 1 and 3 share the same x coordinate, and 3 has a lower y coordinate, 3 "wins."
6. Solution Based on Three Coins, Choosing 1 of 3, and then Flipping
Suggested by: Regan Wick
Coins are from one of 3 mints: Denver (“D”), Philadelphia (“P”), or Washington DC (blank). If you can find 3 of the same-valued coin (i.e. penny) each from a different mint, you can put the three in a container, draw out one (1/3 probability), then flip it (1/2 probability) to get 1/6 probability.
Denver Heads = 1
Denver Tails = 2
Philly Heads = 3
Philly Tails = 4
Washington DC Heads = 5
Washington DC Tails = 6
I got several other suggestions based on coins, but the ones I covered here are those I liked best.
Solutions that are Not Based on Coins
1. Solution Based on Paper and Pen or Pencil
Suggested by: Marcello Poletti (Marc)
Draw a circle on a piece of paper, divide it into six 60-degree fragments, and mark them with the numbers 1 through 6. Rotate a pen or pencil in the center, and choose the number that appears in the fragment that the head of the pan points to. In case it points on a line between two fragments, the fragment that “wins” is the one that appears to the right of the pen’s head. This solution is simple to implement, gives the same probability to each of the six states, and doesn’t have states that need to be ignored. Also, it is less disturbing to the other folks sitting in the pub than throwing coins on the table.
2. Solution Based on Choosing One of Six Identical Items
Suggested by: Lilach Ben-Gan, benflanaghan, Regan Wick, Michael Coles, Peter DeBetta
Write the numbers 1-6 on small identical squares that you cut from a coaster, or mark the numbers on six coins of the same type. Shake them up in a cup, and pull one without looking.
3. Solution Based on Cards
Suggested by: Michael Coles
If you happen to carry cards with you, just take the cards A, 2, 3, 4, 5, 6 out of the deck, shuffle well and pull one. To get the same odds you have to reshuffle between each pull.
I got also several other solutions without using coins, but I found the ones I presented the simplest.
Cheers,
BG
