Lucas Garron's "Three Indistinguishable Dice" Problem
For my solution, skip down to the section "Adjacent Dice Values".
Contents
Lucas' Problem and Ground Rules
The Huge Table as Existence Proof
Robert Munafo's Bogglingly-Easy Solution to Lucas Garron's Dice Challenge
The Quirky Single-Die Change (Rule 4)
Alternative Ordering of the Rules
Three Indistinsuishable Dice From Four?
Description of the Problem
This is a puzzle posed by Lucas Garron to Matt Parker, and described in this video by Parker. The puzzle originates with this little cube-shaped capsule containing three tiny dice, possibly intended1 for playing chuck-a-luck outdoors, or for use in those numerous and common situations where one needs exactly three dice and does not want to risk them being lost or separated2.
with this you may roll 3 dice at once
The puzzle arises in the mind of one who possesses this three-dice object, and for some reason does not have access to any other (regular) dice, but would nevertheless like to obtain the result one would get by rolling two dice. Perhaps one wishes to play a slightly less corrupt game of chance, like, say, craps. Since the three dice in the capsule are indistinguishable, and must all be rolled at once, there is a puzzle:
Can one use the result from three indistinguishable dice to simulate two?
More precisely, we want a result that is statistically equivalent, meaning that we care about the odds: We want the odds of rolling a 2 and a 5 together to be exactly 2/36, just like with a real pair of dice. Also, both simulated dice values matter, not just their sum: If we're using this thing to play backgammon, a 2 and 4 is different from a pair of 3's.
To illustrate the idea, consider the simpler question:
Can you use the result from two indistinguishable dice to simulate one?
The answer is simple: just add their values and if the answer is larger than 6, subtract 6:
|
Part of the reason this solution works is because the answer is invariant across different orderings of the two dice: rolling A+B always gives the same answer as rolling B+A. (For example, rolling a 3 and a 5 gives the same result (a 2) as rolling a 5 and a 3, because 5+3 = 3+5 = 8, and you subtract 6 to get 2.)
Lucas' Problem and Ground Rules
Right about now many readers will be having somewhat clever or devious ideas like Why don't you just paint dots on the outside of the Perspex cube and roll the thing twice? So it helps to point out some ground rules:
- This problem is not about the physics of the thing. Rolling the dice and viewing a replay in slo-mo to see which two landed first is not allowed.
- Spotting which two of the three dice lands closest to each other, or closest to you, and using that to choose which to ignore, is not allowed3.
- You may not alter the plastic cube or its component dice in any way, including by magnets, relativistic mesons, or nanobots.
- Modifying one or more dice scorched-lemon style by focussing the rays of the Sun onto one die to make it noticeably darker is right out.
- For that matter, any nonmathematical way of choosing one die to ignore is disallowed. This is a maths problem. You're given three numbers, in a completely arbitrary and unspecific order, which happen to have been rolled with dice, and you're to take those and give me back two dicelike numbers whose distribution will pass all tests of statistical fairness and independence.
As Matt puts it, "this is not a lateral thinking problem, it's a maths problem." Now that we've got that out of the way...
The "Huge Table" as Proof-of-Existence
For the original question, we're using three dice to simulate two, and ideally we'd like those two dice to be distinguishable; for example, knowing if we rolled a 2 and then a 5, as opposed to a 5 and then a 2.
As Matt states in the video setting this problem, we know that this is possible to do somehow, if only by creating a huge table, like the table above but with 36 "rows", each listing six of the 3-dice roll outcomes:
|
An astute reader might return to this chart later and notice that all examples listed here actually match my solution, given below. An adventurous reader may wish to pause upon seeing this for the first time, and work out what my solution actually is.
We know that it's possible because the indistinguishable sets of 3-dice roll outcomes can all happen either in six ways (when rolling three distinct values), three ways (when you roll one pair), or one way (when you roll three-of-a-kind). So the groups of six can be put on one row each, groups of three can be paired to make rows of six, and the single cases can be thrown into whatever space is left over at the end. For example, in the first row above we see the three ways to roll 1+6+6 and the three ways to roll 1+3+3; the second row has all six ways to roll 2+5+6.
Adjacent Dice Values
Two dice are said to have "adjacent" values if they differ by 1, or if one is a 1 and the other is a 6. Using "modulo" arithmetic, their difference is 1 or -1 modulo 6. It's much like how an Ace in cards can be considered to be highest in the suit (next to the King) or lowest (next to the 2).
Equal or Adjacent
Most of the time you'll be looking for two dice that are equal or adjacent. Equal is obvious: you have two equal dice if you rolled a pair. "Equal or adjacent" means you either rolled a pair, or failing that, you have two dice that differ by 1 (including the notion that a 6 and a 1 are adjacent). It's important to remember that a pair (exact match) takes priority over adjacent (differs by 1). For example, if you roll 1 1 2, the two 1's are considered a pair. 2 is adjacent to 1, but that's not relevant when you have an equal pair.
The Odd One Out
Most of the time, we'll be able to get our answer using a simple rule: single out one die by identifying two that are "equal or adjacent", and using the third value — the "odd one out" — as the answer. The odd one out is said to be "lonely" because it is furthest (numerically)3 from the other two. In cases where all the dice are equally close or equally lonely, we pull a couple tricks to try to force a pairing, thereby leaving an odd one out. For the few remaining cases, we celebrate their trinity by declaring that they signify a pair of 3's, a pair of 6's or a 3 and a 6.
Robert Munafo's Bogglingly-Easy Solution to Lucas Garron's Dice Challenge
(It's not that easy really, but it's the best I could do.)
Now that we have established the idea of "equal or adjacent", and the "odd one out", we're ready to roll our three identical dice, and then determine what we could have rolled if we had two real, separate distinguishable dice: two "virtual dice", which we'll lovingly call D1 and D2.
1. First, by time-honoured tradition, we always determine D1 by a reasonably simple method I call "casting out sixes". It's very much like casting out nines. Add the three dice values together, and if the total is greater than 6, subtract 6 (or subtract 12) to get a number from 1 to 6. This is the first number of your "virtual pair of dice", and we call it "D1".
2. If D1 is 3 or 6, skip step 3 for now (though you might return to it).
3. If D1 is not a multiple of 3 (that is, if it's 1, 2, 4, or 5) then we have it pretty easy. Use the Lonely Die Rule:
The Lonely Die Rule: Look at the three dice, and spot the two that are closest: either equal or adjacent. Remember, a 6 and a 1 are "adjacent", just like the King and Ace in cards can be treated as adjacent in value.
After you've spotted your two equal or adjacent dice, ignore them. The remaining die, the "lonely die", is the second number of your "virtual pair of dice"4. Call it D2, and you're done!
4. If D1 is 3 or 6: Look at your three dice, and see if one (and only one) of them is a 3 or a 6. If that is the case, then use the Singlet Rule: pretend that die is a 1 (but do not change D1). Now go back up to step 3 and use the Lonely Die Rule.
5. If you get here, then it's because D1 is 3 or 6, and either none of your three dice are 3's or 6's, or all of them are 3's and 6's. It might also be the case that you rolled three-of-a-kind.
If you rolled three-of-a-kind, or if you rolled all 3's and 6's — congratulate yourself. You rolled doubles on your virtual dice. Let D2 be the same as D1, and you're done!
In the remaining case, you rolled no 3's or 6's and also didn't roll three-of-a-kind. This is the Huis Clos of dice rolls: our three numbers are unable to accomplish a pairing between them, nor achieve supreme threenity. Let D2 be the other multiple of 3, that is, 9 minus D1. (Your "virtual dice" are a 3 and a 6, or they're a 6 and a 3. Even in their threeness, they are a mismatched pair.) You're done!
The Quirky Single-Die Change (Rule 4)
In step 4 you'll notice that I arbitrarily singled out a lone die with value 3 or 6 and changed it to the even more arbitrary value 1. (I "singled it out" by making it "numerically single"... get it? ... but we digress.)
Why does this have to be 1? It doesn't! You may enjoy seeing what happens if we instead have this rule replace the 3 or 6 with the value 2, or with 4, or with 5. All versions of Rule 4 will work. In that sense, the rule isn't quite as asymmetrical as it seems at first glance. I chose 1 because it was the first number I happened to think of.
However, that does not imply that we could make Rule 4 say something like, "take the single 3 or 6 and change it into anything that is not 3 or 6". Such a rule would introduce a choice, which would make the algorithm non-deterministic, which could be used for deliberate cheating. Whatever value you use, it must be written into the rule and agreed to in advance.
Personally, I'd recommend 1. 1's and 2's are easy to spot, and there won't be a 6 because you've just changed it — so you'll have an easy time recognising the other member of the pair if that 1 ends up being part of the "equal or adjacent pair" (which happens 3/4 of the time). Using 1 also supports my mnemonic that you have a "single" 3 or 6 die which you make "single" by turning it into 1.
Examples
Roll: 2 4 1 ⚁ ⚃ ⚀
First, add 2+4+1 to get 7, then subtract 6: The first virtual die is a 1.
The 1 and 2 are adjacent, so ignore them. The remaining die is our other "virtual" die, a 4.
→ We rolled a 1, then a 4.
Roll: 5 5 3 ⚄ ⚄ ⚂
First, add 5+5+3 to get 13, then subtract 12: The first virtual die is a 1.
The two 5's are equal, so ignore them. The remaining die is our other "virtual" die, a 3.
→ We rolled a 1, then a 3.
Roll: 3 1 6 ⚂ ⚀ ⚅
First, add 3+1+6 to get 10, then subtract 6: The first virtual die is a 4.
The 1 and 6 are adjacent (like an Ace and King in cards), so we ignore them. The remaining die is our other "virtual" die, a 3.
→ We rolled a 4, then a 3.
Roll: 2 2 3 ⚁ ⚁ ⚂
First, add 2+2+3 to get 7, then subtract 6: The first virtual die is a 1.
The 2's are equal, so we ignore them. The remaining die is our other "virtual" die, a 3.
→ We rolled a 1, then a 3.
Roll: 2 6 1 ⚁ ⚅ ⚀
First, add 2+6+1 to get 9, then subtract 6: The first virtual die is a 3.
Because our first "virtual" die is a 3 or 6, we now look for 3's and 6's in our three real dice. We have exactly one 6, so we can change it to a 1 and use the Lonely Die Rule:
Changed roll: 2 1 1
The 1's are equal, so we ignore them. The remaining die is our other "virtual" die, a 2.
→ We rolled a 3, then a 2.
Roll: 3 6 3 ⚂ ⚅ ⚂
First, add 3+6+3 to get 12, then subtract 6: The first virtual die is a 6.
Because our first "virtual" die is a 3 or 6, we now look for 3's and 6's in our three real dice. All of them are 3's and 6's! This means we "rolled doubles" on our virtual dice: Our second "virtual" die is also a 6.
→ We rolled a 6, then a 6.
Roll: 4 1 4 ⚃ ⚀ ⚃
First, add 4+1+4 to get 9, then subtract 6: The first virtual die is a 3.
Because our first "virtual" die is a 3 or 6, we now look for 3's and 6's in our three real dice. None of them are 3's and 6's — this means we cannot apply the Lonely Die Rule; nor did we "roll doubles" on our virtual dice. In this situation we always get a 3 and a 6 or vice versa. Since our first "virtual" die is a 3, our second "virtual" die must be a 6.
→ We rolled a 3, then a 6.
Table of all 56 equivalence-classes of the 216 combinations of 3 dice
As in Katie and Paul's "dead easy" solution, I began by sorting all the cases into columns according to the modulo sum (A+B+C modulo 6) which is also the first virtual die "D1".
I solved this problem by staring at the large list of 3-number triplets in the block comment near the top of my program and looking for methodical ways to single out and/or compute a number from each triplet in the table. The table you see here is refined and formatted to show how my solution works.
In each case where the Lonely Die Rule is used, the "lonely die" value that becomes D2 is highlighted in bold. In the D1=3 and D1=6 columns, this entails first changing a lone 3 or 6 to a 1 and proceeding as if you had rolled that. This is signified with an arrow "→" and a second set of three numbers in brackets, showing what I changed the dice into. In only one row (the cases of rolling 4+5+6 or 3+4+5) does the 1 end up becoming D2.
Also in the D1=3 and D1=6 columns, the "one pair" and "3 of a kind" cases are treated as 3's and 6's. These cases are shown with D2 underlined.
|
Demonstration Source Code
This Perl source code demonstrates that the algorithm works. It generates all 216 combinations of three dice (called $i, $j, and $k in the code). For each combination it sorts the dice in descending order, calling these $a, $b, and $c. Then it runs the algorithm described above to derive the two "virtual dice" values $d1 and $d2. The hash %population is used to count how many times each combination of two dice is rolled. When it has generated all 216 combinations, it reports how many times each of the 36 possibilities occurred. If all happen equally often (i.e. 6 times each), it declares success.
The code also allows testing of my claim that Rule 4 is not as arbitrarily asymmetrical as it might first appear, by letting you change $singletonchange (normally 1) to something else, like 2.
Alternative Ordering of the Rules
The rules for my solution to this puzzle are a bit involved, and some may find the ordering I used (with jumping from rule 2 to rule 4 and then back to rule 3) to be awkward to say the least. Here's another way they could be written, which deals with the rarest cases first and the most common cases last:
A. First, by time-honoured tradition, we always determine D1 by a reasonably simple method I call "casting out sixes". It's very much like casting out nines. Add the three dice values together, and if the total is greater than 6, subtract 6 (or subtract 12) to get a number from 1 to 6. This is the first number of your "virtual pair of dice", and we call it "D1".
(If D1 is not a multiple of 3, you can skip right down to step E, because the other steps won't apply.)
B. If D1 is 3 or 6, and if the three dice are all 3's and 6's or if you rolled three-of-a-kind, then you've accomplished "supreme threenity". For this you receive the benefit of rolling doubles: let D2 be the same as D1. You're done.
C. If D1 is 3 or 6 and you rolled no 3's or 6's at all, nor did you roll three-of-a-kind — then you got a "failure of threeness". In this case let D2 be 9 minus D1, so your virtual dice roll is a mismatched pair: 3 and 6, or 6 and 3. You're done.
D. If D1 is 3 or 6 and you're still reading this, that means you have a single 3 or 6. Now we use the Singlet Rule: "single out" this die by ignoring its true identity and pretending it's a one (1). Do not change D1, but proceed to the final step as if your 3 or 6 was actually a 1. (For example, if you rolled 1+2+6, imagine that you rolled 1+2+1).
E. If you didn't get a D2 from rule B or C, you'll get it now using The Lonely Die Rule:
Look at the three dice, and spot the two that are closest: If you have a pair, they're the closest; otherwise there will be two that are "adjacent" (their value differs by 1, or the pair (6, 1) which is "adjacent" the same way an Ace in cards is next to the King).
Ignore the two closest dice: the remaining die is the "lonely die" and its value is D2, the second of your virtual dice. You're done!
Hagen von Eitzen's Solution
Hagen von Eitzen found a solution, explained in his video Two Dice from Three Dice, that is brilliant and elegant, and can be done in one's head. He does not aspire to use the "sum modulo 6" method of calculating the first die result.
Here I have arranged the 56 cases the same way as in the table for my own system, though this arrangement is not particularly relevant to von Eitzen's solution. I just arranged the table this way to make for easier comparisons with my table.
|
von Eitzen's algorithm is really nice and uses a more visual or geometrical method, where you picture the six die result values 1 through 6 as being arranged around the vertices of a regular hexagon, and then visualise what type of shape (like a right triangle) is made when you connect the points represented by the values on your three dice.
Roll 3,4,6 Roll 5,1,6 Roll 3,3,1 [6]. . . 1 [6]* * *[1] 6 . . .[1] ** . * * . . * .* * . * * . . *. 5 . * * . 2 [5]* . 2 5 . * . 2 .* * . . . . *. * * . . . . * [4]* * *[3] 4 . . . 3 4 . . .[3] right isosceles line segment triangle triangle (no triangle) Use 4 (right angle) Use 6 (apex of Use both numbers and 6 (next after 4 triangle) twice in clockwise order) Larger number first Smaller number first Result: 6,4 Result: 6,6 Result: 1,3 Not pictured: equilateral triangle 1,3,5 -> result 4,1 equilateral triangle 2,4,6 -> result 5,2 three of a kind e.g. 2,2,2 -> result 6,3It's also very nice in that the values of the virtual two dice are almost always taken directly from the values you rolled on your physical three dice. That happens in the three main cases, illustrated in the ASCII graphic above with three hex diagrams. Those cases cover 11/12 of the possibilities. The remaining 1/12 include all cases of the three points being equidistant on the hex diagram: either an equilateral triangle from rolling a 1-3-5 or 2-4-6 combination (which become 4,1 ⚃⚀ and 5,2 ⚄⚁ respectively), or the three-of-a-kind case (which become 6,3 ⚅⚂). Watch his video for his explanation, a very nice presentation with lots of slides.
Three Dice From Four?
After the simple [two-dice] version and all of the above regarding three dice, one might wonder whether one can take the next logical step: rolling four indistinguishable dice, and somehow using the outcome to "simulate" three dice.
Sadly, the answer is no. To see why, consider the total number of combinations of 4 dice, which is 64=1296, and notice that there are many cases of rolling four different numbers (such as ⚂ ⚃ ⚄ ⚅) where there are 4!=24 different ways to roll the same thing. So, there are groups of 24, in much the same way that our three-dice problem had groups of 6. But if we want to discern 216 possibilities of rolling three dice, we can't handle these indistinguishable groups of 24.
Three Indistinguishable Dice From Four?
On the other hand, suppose we just want to emulate three indistinguishable dice, that is to say, we don't need to know which of the three virtual dice is "first". In this case we wish to distribute the 1296 outcomes of the four dice onto the 56 cases in the table, and ensure proper weightings.
When rolling four dice there are
- 6 ways to get 4-of-a-kind each with probability 1/1296
- 6×5 = 30 ways to get 3-of-a-kind each with probability 4/1296 (example: ⚀⚀⚀⚂, ⚀⚀⚂⚀, ⚀⚂⚀⚀, or ⚂⚀⚀⚀)
- 6×5/2 = 15 ways to get two pairs each with probability 6/1296 (example: ⚀⚀⚂⚂, ⚀⚂⚀⚂, ⚀⚂⚂⚀, ⚂⚀⚀⚂, ⚂⚀⚂⚀, or ⚂⚂⚀⚀)
- 6×5×4/2 = 60 ways to get one pair, each with probability 12/1296 (example: ⚀⚁⚂⚂, ⚀⚂⚁⚂, ⚀⚂⚂⚁, ⚁⚀⚂⚂, ⚁⚂⚀⚂, ⚁⚂⚂⚀, ⚂⚀⚁⚂, ⚂⚀⚂⚁, ⚂⚁⚀⚂, ⚂⚁⚂⚀, ⚂⚂⚀⚁, and ⚂⚂⚁⚀. Alternatively, to see that it is 12, consider all 4!=24 permutations, but then notice that the two ⚂'s are equivalent so there are really just half as many possibilities.)
- 6×5×4×3/4! = 15 ways to get all different numbers, each with probability 24/1296 (example: ⚀⚁⚂⚃, in all of the 4!=24 permutations)
all of which we could call "cases". There are 6+30+15+60+15 = 126 "cases", and 6×1 + 30×4 + 15×6 + 60×12 + 15×24 = 1296, so it all adds up as one would expect. These 126 cases of 4-indistinguishable-dice outcomes need to be grouped into 56 classifications ("classes") of 3-indistinguishable-dice outcomes, speficically: 20 with probability 36/1296, 30 with probability 18/1296, and 6 with probability 6/1296.
Problem: Repartition 6×1 + 30×4 + 15×6 + 60×12 + 15×24 (6+30+15+60+15 = 126 "cases") into 6×6 + 30×18 + 20×36 (56 "classes"); multiple cases may be combined to make classes, but cases may not be split up.
Clearly, the cases of multiplicity 24 each need to be part of one of the desired 20 classes that have probability 36/1296. Let's just take those away now, and reformulate the problem accordingly. The original problem can be solved if and only if we can solve:
Problem (reduced): Repartition 6×1 + 30×4 + 15×6 + 60×12 (111 cases) into 6×6 + 15×12 + 30×18 + 5×36 (56 classes)
We have 60 cases of multiplicity 12 to deal with. The very best we could hope to do is to use 15 of them when forming the 5×36, and one each on the 15×12 and 30×18. That would give us:
Repartition 6×1 + 30×4 + 15×6 into 36×6
But the 4's are useless now. Only three of them can be combined with the 1's to make 6's, we'll have 27 left. If we don't get rid of these 4's while we still have some classes of size 12 or larger to fill, we'll be stuck with useless 4's.
The 4's can be taken 3 at a time and combined with 12's when making up the 5×36; but we'd be left with troublesome 12's that can't be used anywhere. Similarly, 4's can be used when building the 18's, but again it's a tradeoff with the 12's. We can use the 1's to do 12+4+1+1→18 three times, but that doesn't get rid of enough of the 4's.
Regardless of how we do it, we'll always end up with too many 12's (or too many 4's, or both) to be able to fulfill the task. So the reduced problem cannot be solved, and we must conclude that there is no way to emulate three indistinguishable dice using four indistinguishable dice.
Reducing our expectations even further, let's just try to emulate two dice. There are 36 possible outcomes, each with probability 1/36 = 36/1296. Can we at least manage to do this?
Problem: Repartition 6×1 + 30×4 + 15×6 + 60×12 + 15×24 (6+30+15+60+15 = 126 "cases") into 36×36 (36 "classes")
Here, at least, it's easy. Combine the 24's with 15 of the 12's to make 15 classes with probability 36/1296; use the remaining 45 cases of multiplicity 12 to make another 15 classes of probability 36/1296; use 27 of the 4's grouped as 9×4 three times to make three more 36's; then use the remaining 3×4 + 15×6 by doing 1+1+4+6+6+6+6+6=36 three times.
So it's possible to emulate two distinguishable dice using four indistinguishable dice. The 6×1 + 30×4 + 15×6 cases represent the more rare and notable combinations, so these would be used to form the pairs outcomes (⚀ ⚀, ⚁ ⚁, etc.). Regardless of what system we come up with and how easy we manage to make it, we're still likely to be unfulfilled when considering to the fact that we can do the same thing from three indistinguishable dice.
Also dice-related:
Exponentially Distributed Dice
Footnotes contain spoilers.
1 : The aptly-named "3-in-a-cube dice" are made by Koplow Games. Available from The Dice Shop at Mathartfun.com. (Other sellers I found: here (UK), and here (USA). Apparently they're intended for rolling up characters in classic D&D... yeah, I guess they'd be good for that. Several Amazon sellers had them with distinct colours, but sold out. If you want fifty, you might try previewsworld or wondertrail.
2 : Ironically, being lost or separated evokes loneliness, a theme I used in my solution.
3 : furthest is far in abstract, figurative, or metaphorical terms; farthest implies actual physical distance. It's somewhat ironic that, though the "look at which two dice land touching or closest to each other" idea is not a desired solution to this puzzle, my solution does involve the same idea in the more abstract sense of numerical closeness. So there's that.
4 : Since that die was lonely, we decided to give it a partner, and D1 is that partner. D1 and D2 are a pair, albeit virtual, and will never be lonely again. Yay!
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2016 May 15.
s.27