## Two Dice

My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.

Problem.Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?

The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.

I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let *a _{i}* (correspondingly

*b*) be the probabilities that die A (correspondingly B) shows

_{i}*i*+ 1. It would be very useful later that that

*i*ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ a

_{i}z

^{i}and g(z) = ∑ b

_{i}z

^{i}. Then the desired result is that f(z)g(z) = ∑

_{j=0}

^{10}z

^{j}/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a

_{5}=b

_{5}=0 and the coefficient of z

^{10}in their product is also 0, contradiction.

Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a_{0}b_{0} = a_{5}b_{5} = 1/11. Then the probability of a total 7 is at least a_{0}b_{5} + a_{0}b_{5}. The geometric mean of a_{0}b_{5} and a_{0}b_{5}
is 1/11 (from above), so their arithmetic mean is at least 1/11 and
their sum is at least 2/11. Therefore, the uniform distribution for sums
is impossible.

So 1/11 is impossible, but how close to it can you get?

Share:
## Kknop:

Lower bound 14/144. Example (3,0,0,0,0,3) (1,1,1,1,1,1).

14 December 2018, 1:47 am## Oscar Cunningham:

Lower bound 3/32. Example (1,0,0,0,0,1)/2 (2,3,3,3,3,2)/16.

14 December 2018, 12:19 pm## Oscar Cunningham:

I asked reddit for help: https://www.reddit.com/r/math/comments/a6tv25/two_dice_puzzle/

16 December 2018, 5:59 pm## Jim Roche:

Great blog, Tanya! I wish I’d found it years ago.

The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.

Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5) be

(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.

The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:

(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and \sum_{1 <= i <= m} x[i] = C, then

\sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then

\sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so

p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).

Now we relax the conditions of the original problem and seek the minimum of \sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when

p = (2,3,3,3,3,4,3,3,3,3,2)/32.

Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.

To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.

Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1. Furthermore, for any fixed value of

p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):

min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }

s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u 0, b[0] = b[5] > 0, and

either (a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).

We continue by considering p[2] and p[8], obtaining more and more constraints on the a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible swapping of the a[] and b[] distributions).

31 March 2019, 12:42 pm## Jim Roche:

Sorry, my previous post seems to be missing various lines. I’ll try again, breaking into 2 pieces:

Part 1:

The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.

Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5) be

(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.

The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:

(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and \sum_{1 <= i <= m} x[i] = C, then

\sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then

\sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so

p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).

Now we relax the conditions of the original problem and seek the minimum of \sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when

p = (2,3,3,3,3,4,3,3,3,3,2)/32.

Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.

To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.

Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1. Furthermore, for any fixed value of

p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):

min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }

s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.

31 March 2019, 12:52 pm## Jim Roche:

Ugh, my previous 2 comments were mangled, probably because some mathematical symbols were misinterpreted. Here’s one more attempt.

The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.

Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5 on each die) be

(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.

The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:

(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and sum_{1 <= i <= m} x[i] = C, then

sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then

sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so

p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).

Now we relax the conditions of the original problem and seek the minimum of

sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when

p = (2,3,3,3,3,4,3,3,3,3,2)/32.

Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.

To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.

Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints

0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.

Furthermore, for any fixed value of

p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):

min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }

31 March 2019, 11:16 pms.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u <= 1, Q + u 0, b[0] = b[5] > 0, and

either (a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).

We continue by considering p[2] and p[8], obtaining more and more constraints on the a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible swapping of the a[] and b[] distributions).

## Jim Roche:

Here’s a fourth attempt to post an ungarbled solution to the dice problem.

Great blog, Tanya! I wish I’d found it years ago.

The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice —

the unique pair of dice that achieves the minimum is Oscar’s:

{(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}.

A proof sketch is below.

Let the distribution (pmf) of the sum of the values on the 2 dice

(translated from 1-6 to 0-5 on each die) be (p[0], …, p[10]), and

let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for

the 2 individual dice. The 2 key lemmas we need were already (essentially)

given in Tanya’s 13 December 2018 post:

(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and sum_{1 <= i <= m} x[i] = C,

then

sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and

then

sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality],

so

p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).

Now we relax the conditions of the original problem and seek the minimum of

sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum

for this relaxed problem is 3/32, uniquely achieved when

p = (2,3,3,3,3,4,3,3,3,3,2)/32.

Then we will argue that this unique p is achieved as a convolution of a and b only

for the pair of pmf’s {a,b} that Oscar found.

To solve the relaxed optimization problem, define r[0] := sqrt(p[0]),

r[10] := sqrt(p[10]), and define the slack variable

u >= 0 as u := p[5] – 2*r[0]*r[10].

It will turn out to be more convenient to work instead with the “product” variable

P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.

Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of

P, Q, and u with the linear inequality constraints

0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.

Furthermore, for any fixed value of p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize

the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal.

After a little algebra, we obtain the following transformed minimization problem

(whose global minimum might not be achievable for the original problem, but which will

not lose any solutions to the original problem):

min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }

s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u <= 1, Q + u 0, b[0] = b[5] > 0, and either

(a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).

We continue by considering p[2] and p[8], obtaining more and more constraints on

6 April 2019, 9:36 amthe a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible

swapping of the a[] and b[] distributions).