Use a 20 sided die and a 6 sided die to represent number 1-45 with equal probability

Question

I wonder if anyone could help me with this question:

Use a 20 sided die and a 6 sided die to represent all numbers from 1-45 with equal probability.

Also, it is okay to use one die repeatedly as long as the probability of getting each of 1-45 are equal.

I tried different ways such as use the 1-4 from the 6 sided die to represent the tenth bit and the 1-9 to represent the 1th bit...but none of them really works. I would appreciate if anyone could give me a good hint. Thanks

Answer 1

HINT: Roll the $20$-sided die once and the $6$-sided die twice, recording the three outcomes in order. Then use the fact that $20\cdot6\cdot6=720=16\cdot45$. (This approach requires that you make a reference table or else keep a lot of information in your head.)

Added: A more efficient alternative is to roll the $6$-sided die twice, reducing each outcome modulo $3$, and interpret the result as a two-digit number in base $3$. This gives you an integer in the range $\{0,1,\ldots,8\}$ with uniform probability. Roll the $20$-sided die once and reduce modulo $5$ to get $0,1,2,3$, or $4$, each with equal probability. Can you see how to combine these to get an integer uniformly distributed in $\{0,1,\ldots,44\}$?

Answer 2

Here's a way to do it with just three rolls: Roll the $6$-sided die twice, and reduce the value of each roll modulo $3$ to produce (in order) values $A, B \in \{0, 1, 2\}$. Then, roll the $20$-sided die once and reduce the value of the roll modulo $5$ to produce a value $C \in \{0, 1, 2, 3, 4\}$. Then, by construction, the value of $$(3 \cdot 5) A + 5 B + C + 1 = 15 A + 5 B + C + 1$$ is uniformly distributed over $\{1, \ldots, 45\}$ as desired.

This works as follows: Just as one can write a nonnegative integer uniquely as $$a_{n - 1} \cdot 10^{n - 1} + \cdots + a_1 \cdot 10 + a_0$$ for integers $0 \leq a_0 \leq 9$---indeed, the literal expression $a_n \cdots a_0$ is the usual decimal representation of the number, given a sequence $\{b_0, \ldots, b_n\}$ of integers $b_k > 1$, we can write an integer $0 \leq r < b_0 \cdots b_n$ uniquely as $$a_{n - 1} (b_1 \cdots b_{n - 1}) + \cdots + a_1 b_1 + a_0,$$ where each $a_k$ is an integer $0 \leq a_k \leq b_k$. I suppose one could think of this as a sort of variable-base representation.

In our case, we want to produce an integer in the range $0 \leq r < 45 = 5 \cdot 3 \cdot 3$ (and then, by adding one, produce one in $1 \leq r \leq 45$), so we've taken the sequence $(b_0, b_1, b_2) = (5, 3, 3)$. (We could just as well have taken $(3, 5, 3)$ or $(3, 3, 5)$, but NB that this changes the coefficients of the reduced roll values: Taking $(3, 3, 5)$, for example, leads to the expression $9 C + 3 A + B + 1$.)

Alternatively, one could think of this as using the $6$-sided die to generate a random $2$-digit number in base $3$ (equivalently, an integer $0 \leq r_3 < 9$) and using the $20$-sided die to generate a random digit in base $9$ (an integer $0 \leq r_5 < 5$) and then applying the Chinese Remainder Theorem.

Answer 3

Go for simplicity. Ignore the 6, 19, and 20.

1) roll the 6-sided die ONCE, unless comes up 6, then roll until it's a non-6.

2) roll the 20-sided die ONCE, unless comes up with 10 or 20, then roll again until it's neither 10 nor 20. Consider outcomes 1,11 identical, 2,12 identical, and so on up to 9,19 identical.

You would roll a total of two times a little less than 5/6 of the time, perhaps assisted by Bayesian probability to obtain an exact probability but this should not be of any great concern.

Answer 4

Roll the d$20$ until you get $x=18$ or less; roll the d$6$ until you get $y=5$ or less. The number $$9y+(x{\text{ mod }}9)-8$$ is equally likely to be any number from $1$ to $45$. To see this, note that $9(y-1)$ is uniform over $\{0,9,18,27,36\}$, and $(x{\text{ mod }}9)+1$ is chosen randomly from $1$ through $9$.