25
$\begingroup$

The exact question is: You need an 8-sided die for a game. You only have a coin, two four-sided and one 10-sided dice. How can you replace the 8-sided die? Re-rolls are not allowed.

There are several solutions to this I've been told, I found one, but my solution wasn't one of the expected solutions. What solutions can you think of?

My solution was:

Roll 10-sided and 2x 4-sided dice, sum up the result and roll and substract 2-sided die (the coin) which you divide by 2 at the end to get the result (round up)

$\endgroup$
  • 10
    $\begingroup$ Your solution doesn't replace an 8-sided die, because it produces some values (such as 4) much more frequently than others (such as 1). $\endgroup$ – MJD Nov 14 '16 at 18:30
  • 23
    $\begingroup$ Remember that you need to not only generate random numbers between 1 and 8, but they also need to be uniformly distributed. $\endgroup$ – Riccardo Orlando Nov 14 '16 at 18:30
  • 49
    $\begingroup$ Isn't flipping the coin 3 times sufficient? $\endgroup$ – kennytm Nov 14 '16 at 18:32
  • 41
    $\begingroup$ Rolling a 4 sided die, and then adding 4 if a coin toss is heads, accurately simulates an 8 sided die. $\endgroup$ – Riccardo Orlando Nov 14 '16 at 18:39
  • 29
    $\begingroup$ Not sure if this is allowed, but I would just roll the 10-sided die, and re-roll if it landed on a value above 8. $\endgroup$ – BradC Nov 14 '16 at 20:41

13 Answers 13

64
$\begingroup$

We need to not only generate numbers between 1 and 8, but also to make sure they are uniformly distributed.

Your solution does not produce uniformly distributed results (at least according to MJD, in the comments).

However, this procedure does: you can roll a 4-sided die for a value between 1 and 4, and then toss a coin: if heads, add 4 to the result.

It is easy to see that each number from 1 to 8 is produced by exactly one outcome: for example, a result of 3 requires a roll of 3 and a toss of tails, while a result of 5 requires a roll of 1 and a toss of heads.

$\endgroup$
  • 5
    $\begingroup$ For bonus points, you can simulate the coin toss by rolling again and taking evens/odds. $\endgroup$ – Hurkyl Nov 15 '16 at 10:53
  • 16
    $\begingroup$ @Hurkyl for extra bonus points, you can use your simulated 8-die to simulate a 4-die, and a coin toss, to then simulate a different 8-die! $\endgroup$ – Riccardo Orlando Nov 15 '16 at 12:34
  • 2
    $\begingroup$ Roll the ten sided die to get t, and the four sided die to get f. Calculate (t+10*f)/5. $\endgroup$ – richard1941 Nov 15 '16 at 18:04
  • $\begingroup$ An even more interesting problem is how to test a die to determine if it is "fair". (We all know that dice games are never fair and that we are guaranteed by "gambler's ruin" to be wiped out.) $\endgroup$ – richard1941 Nov 15 '16 at 18:06
  • $\begingroup$ @RiccardoOrlando is my maths right? Getting any number between 1 to 4 is 1/4 and getting head and tail is 1/2 so every number have 1/2*1/4=1/8 chance of being thrown. $\endgroup$ – noman pouigt Nov 16 '16 at 1:38
46
$\begingroup$

There are essentially three basic ways to generate a number from $\{1\dots k\}$ for $k\ne n$ with an $n$-sided die that preserves the uniform probability of all results:

  • Truncation: if $k\lt n$, you can simply ignore (reroll) results greater than $k$
  • Division: if $n=mk$ for some integer $m$, you can designate $m$ different results as giving a result $i$ for $1\le i\le k$ (i.e. to simulate a $3$-sided die with a $6$-sided die, you can designate $\{1,2\}\rightarrow 1$, $\{3,4\}\rightarrow 2$ and $\{5,6\}\rightarrow 3$)
  • Exponentiation: if $k=n^m$ for some integer $m$ you can roll the die $m$ times, interpreting the results as the digits of an $m$-digit integer in base $n$ (and interpreting a result of $n$ as $0$, and a string of all $0$'s as $k$) Example: percentile dice

Any combination of these can be used, thus for instance you could simulate an $8$-sided die with a $6\text{-sided}$ die by exponentiation by 2 (simulating a $36$-sided die) followed by division by 4 (simulating a $9$-sided die) followed by truncation to $8$. Since you have multiple dice to start with, more solutions are possible, but you only ever need one die. For instance you could simulate an $n\text{-sided}$ die for any $n$ with just a coin using exponentiation (generating binary strings with head $\rightarrow 1$ and tail $\rightarrow 0$) and truncation (rerolling results greater than $n$), and going the other way, you can simulate a coin with an $n$-sided die for any $n\ge 2$ by truncation to an even number (if $n$ is odd), followed by division to $2$.

If you have multiple die sizes, exponentiation can be generalized to multiplication (as is used in the accepted answer): if $k=mn$, and you have dice of sizes $m$ and $n$, you can roll the $n$-sided die (interpreting a result of $n$ as $0$) and add $n$ times the result of rolling the $m$-sided die (interpreting $m$ as $0$), and interpret $0$ as $k$. In the accepted answer $n=4$, $m=2$ and $k=8$, but an alternate solution would use $n=2$ and $m=4$ so you could (for instance) roll the $4$-sided die (interpreting $4$ as 0), multiply the result by $2$ then add $1$ if you flip heads, and interpret an overall result of $0$ (that is $[4,\text{tails}]$) as $8$. It's equivalent (and simpler) to multiply the $\text{d}4$ result by $2$ and subtract $1$ if you flip tails.

$\endgroup$
  • 1
    $\begingroup$ Good generalization yet, the question implied no rerolls. so first and third options are not applicable. and you can't do second since there aren't any 16-sided or more die you can roll. $\endgroup$ – Volkan Ulukut Nov 14 '16 at 18:47
  • $\begingroup$ Fair enough, I missed that part. I actually came up with these rules based on an old Google interview question about simulating a $8$-sided die using a $5$-sided die. I was quite happy that my solution (exponentiation to $25$, truncation to $24$, division to $8$) required fewer rolls on average than the supposed "correct" answer (truncation to $4$, division to $2$, exponentiation to $8$), even if you generated the three "bits" by $4 \times 2$ rather than $2 \times 2 \times 2$. $\endgroup$ – Gabriel Burns Nov 14 '16 at 18:53
  • $\begingroup$ Anything requiring a reroll could potentially (however unlikely) result in infinite rerolls (or a very long finite series) if the reroll number is continually repeated. $\endgroup$ – GRW Nov 14 '16 at 20:26
  • $\begingroup$ @GRW If by "anything requiring a reroll" you mean truncation (as opposed to exponentiation, which requires a fixed number of rolls), then yes, of course. What is your point? (no disrespect intended, I just honestly don't know what you're driving at here). $\endgroup$ – Gabriel Burns Nov 14 '16 at 20:28
  • 1
    $\begingroup$ @GRW If you're trying to say that truncation should be avoided because it requires a potentially infinite number of rolls, that's all well and good except that in the general case of simulating a $k$-sided die with an $n$-sided die, truncation is necessary if $k$ has any prime factors which are not also factors of $n$. $\endgroup$ – Gabriel Burns Nov 14 '16 at 20:35
32
$\begingroup$

Roll the D10 and if you roll 9 or 10, re-roll it. It's easy to remember and easy to do. And it gives uniform results.

$\endgroup$
  • $\begingroup$ reroll is not allowed i'm afraid. $\endgroup$ – Volkan Ulukut Nov 14 '16 at 20:43
  • 12
    $\begingroup$ I like this one, although once in a very great while you may be home extremely late from game night. $\endgroup$ – BradC Nov 14 '16 at 20:44
  • 5
    $\begingroup$ This is a simple implementation of rejection sampling. As a monte-carlo simulation person, I approve. en.wikipedia.org/wiki/Rejection_sampling $\endgroup$ – drxzcl Nov 14 '16 at 22:45
  • $\begingroup$ This is the best answer $\endgroup$ – Tony Ennis Nov 16 '16 at 2:14
  • 4
    $\begingroup$ @VolkanUlukut I'm afraid this solution is allowed until you update the question. No fair changing the rules in the comments. $\endgroup$ – candied_orange Nov 16 '16 at 3:47
14
$\begingroup$

I'm assuming that all dice (counting the coin as 2-sided die) are rolled in parallel, and rerolls are not allowed. I'll use the standard notation D$n$ for an $n$-sided die (D2 for the coin).

Since we have to simulate a D8, which is a power of 2, we need to multiply uniform distributions with powers of 2; we can consider them as random bits.

  • The D2 delivers one random bit.

  • Each D4 delivers two random bits.

  • The D10 delivers only one random bit, as 2 is the highest power of 2 that divides 10. Since rerolls are not allowed, the factor 5 is useless for generating uniform distributions for powers of 2.

So we have 6 bits in total, of which we can select arbitrary 3 to generate a single D8 roll.

For example, you can use one D4 (2 bits) and the D2 (1 bit) to get 3 bits (this is the solution other answers gave).

You can also take both D4s, and use only one bit for one of them, for example by adding 4 to the result of the second D4 if the first D4 gives an odd result.

Or you could select arbitrary 3 dice, and take their bit value as 0 if the roll result is even and 1 if the result is odd, and then from the three bits form $4a+2b+c+1$ where $a$, $b$ and $c$ are the bits derived from the three dice.

Indeed, you could use the four given dice to simulate rolling two D8 in parallel!

$\endgroup$
3
$\begingroup$

Let the following denote:

  • $a$: the value of the $10$-sided die , i.e., $a\in[1,10]$
  • $b$: the value of the 1st $4$-sided die, i.e., $b\in[1,4]$
  • $c$: the value of the 2nd $4$-sided die, i.e., $c\in[1,4]$
  • $d$: the value of the $2$-sided coin , i.e., $d\in[1,2]$

Then the value of the $8$-sided die as a function of the above variables is:

$$f(a,b,c,d)=[32(a-1)+8(b-1)+2(c-1)+(d-1)]\bmod8+1$$


Here is a short Python script which confirms uniform distribution:

dict = {1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0}

for a in range(1,10+1):
    for b in range(1,4+1):
        for c in range(1,4+1):
            for d in range(1,2+1):
                dict[(32*(a-1)+8*(b-1)+2*(c-1)+(d-1))%8+1] += 1

print dict

The output is {1: 40, 2: 40, 3: 40, 4: 40, 5: 40, 6: 40, 7: 40, 8: 40}.

$\endgroup$
  • 1
    $\begingroup$ But a and b have no effect in your equation, since 32 mod 8 = 0 and 8 mod 8 = 0. $\endgroup$ – Justin Nov 14 '16 at 20:05
  • 2
    $\begingroup$ Of course $32(a-1)\equiv 0 \pmod{8}$ and $8(b-1)\equiv 0 \pmod{8}$, so your first two terms amount to nothing but an elaborate way to write $0$. Moreover for all possible values of $c$ and $d$, we have $2(c-1)+(d-1)<8$, therefore after removing the first two terms, the $\mod 8$ also becomes superfluous, so the formula simplifies to $2(c-1)+d$. $\endgroup$ – celtschk Nov 14 '16 at 20:12
  • $\begingroup$ @Justin: You're right, the $8$-sided die can be simulated using $c$ and $d$ only (i.e., one of the $4$-sided die and the coin). $\endgroup$ – barak manos Nov 14 '16 at 21:45
  • $\begingroup$ @celtschk: You're right, the $8$-sided die can be simulated using $c$ and $d$ only (i.e., one of the $4$-sided die and the coin). $\endgroup$ – barak manos Nov 14 '16 at 21:45
3
$\begingroup$

Roll 2 four-sided dice. Take the result of the first die. Check the second die; if odd, keep the result of the first die. If even, add four the result of the first die.

This method is essentially the same as rolling a d4 plus a coin flip, but can be done more easily as both dice can be rolled at once.

$\endgroup$
  • 1
    $\begingroup$ It would be less confusing to roll a 4-sided die and the 10-sided die. (Use the 10-sided die's oddness or evenness to decide whether to add 4.) This would prevent getting confused about which 4-sided die is being used for each purpose. $\endgroup$ – Jasper Nov 17 '16 at 4:30
  • $\begingroup$ @Jasper As someone who regularly rolls many dice at once, it's not confusing at all. Use two different colored dice, or roll the same d4 twice in a row. $\endgroup$ – LegendaryDude Nov 17 '16 at 13:19
2
$\begingroup$

I would only use the coin, flipping it three times. Each time you flip tails you mark down a 0 and when you flip heads you mark down a 1. Because you are flipping 3 coins this method can give you $2^3 = 8$ different binary numbers (e.g. 000, 001, 010, 011 etc...) in the range from 0 to 7. Just add 1 to the result and you are good to go!

This is valid because every result is equally likely to happen, with probability $\frac{1}{2}^3 = \frac{1}{8}$ just like it is on a 8 sided die.

$\endgroup$
  • $\begingroup$ The question says re-rolls are not allowed. Flipping the coin multiple times counts as a re-roll. $\endgroup$ – LegendaryDude Nov 17 '16 at 20:12
  • $\begingroup$ When I first read the question in my mind I somehow applied this restriction just for dice since you don't "roll" a coin. But you are right and this makes the question more interesting of course. $\endgroup$ – Enuff Nov 21 '16 at 7:52
1
$\begingroup$

There are many solutions. It is a 3 bits problem, since the numbers from 1 to 8 can be represented by 3 bits. Lets use a 4-side dice to decide on 2 bits, and any uniform binary solution for the 3rd one: the coin is the most evident way (as in the accepted answer), but not the only one.

$\endgroup$
  • $\begingroup$ how is this different from the accepted answer? $\endgroup$ – Volkan Ulukut Nov 16 '16 at 12:55
  • $\begingroup$ You are right, Volkan, it was the same answer. Hope the new edition shall clarify my reasoning. Thanks! $\endgroup$ – MJim Nov 16 '16 at 19:13
0
$\begingroup$

An ugly way to do it:

Roll all three dice. (4 * 4 * 10 = 160 possibilities)

If the d10 is in the range of [1, 8], use the d10 value. (4 * 4 * 8 = 128 ways)
Else: . (32 ways left:)
If the total is 11, use 1. . (1 way to get 1)
If the total is 12, use the d10 value minus 7. . (2 ways to get 2; 1 way to get 3)
If the total is 13, use 12 minus the d10 value. . (3 ways to get 3; 2 ways to get 2)
If the total is 14 and the d10 value is 9, use 4. (4 ways to get 4)
If the total is 14 and the d10 value is 10, use 1. (3 ways)
If the total is 15 and the d10 value is 9, use 8. (3 ways)
If the total is 15 and the d10 value is 10, use 5. (4 ways to get 5)
If the total is 16, use 16 minus the d10 value. . (3 ways to get 6; 2 ways to get 7)
If the total is 17, use the d10 value minus 3. . (2 ways to get 7; 1 way to get 6)
If the total is 18, use 8. . (1 way to get 8)

$\endgroup$
  • $\begingroup$ Or assign a number to each outcome and then do $mod\ 8 + 1$. You don't even need the d10. $\endgroup$ – Syncrossus Jun 12 at 14:09
0
$\begingroup$

Assuming a D10 is numbered [1-10] and a D4 [0-3]: Roll the D10. keep the value for [1-8] For 9 and 10, roll a D4. Result is 1+D4 for 9 and 5+D4 for 10.

You have to roll 1 1/5 times in average for each D8 emulation.

$\endgroup$
0
$\begingroup$
  • D2 results $a$ in $\{0,4\}$
  • first D4 results $b$ in $\{1,2,3,4\}$
  • second D4 and D10 are just for fun

Roll all dices and coin and get $x=a+b$

$\endgroup$
0
$\begingroup$

Theoretically, you can do $1d24\ mod\ 8 + 1$, but 24-sided dice are uncommon.

Limiting yourself to the 6 standard D&D dice, you can do $n = ((1d4 - 1) * 10 + 1d10)$ to generate $n$ from a uniform distribution over $[\![1;40]\!]$ and then do $n\ mod\ 8 + 1$.

Using only platonic solids, you can replace the d10 by a d20, resulting in a distribution over $[\![1;80]\!]$.

Using only "tumbling" dice, i.e. dice with right or obtuse angles between their adjacent faces, i.e. not d4, you can replace the $1d4 - 1$ with $1d12\ mod\ 4$.

Using only the d20: $((1d20\ mod\ 4) * 20 + 1d20)\ mod\ 8 + 1$.

$\endgroup$
-1
$\begingroup$

To keep the uniform repartition, here are some proposals :

  • Roll the 10-face dice, re-roll on 9 and 10.
  • Roll the 4-face dice, then flip the coin. Add 4 on heads.
  • Roll the 4-face dice and multiply the result by 2. Flip a coin, and substract 1 on heads.

There are probably a number of other solutions, the important part is to keep the repartition uniform.

$\endgroup$

protected by Daniel Fischer Nov 17 '16 at 21:58

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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