20
$\begingroup$

You shall form three dice, placing 18 distinct integers on the faces of three cubes. Your goal is to be able to obtain all the integers between 1 and 216, inclusive, as the sum of the integers on the top faces of these three dice with a single throw.

What can be the minimum value for the largest of these integers?

(Integers: ...-2,-1,0,1,2,...)

$\endgroup$
  • $\begingroup$ My intuition says it should be 0 :) $\endgroup$ – ABcDexter Jul 9 '16 at 16:46
  • 1
    $\begingroup$ @ABcDexter : In that case the largest sum would be $-3 = 0+(-1)+(-2)$. Lower limit should be increased to 73 at least ($216 = 73+72+71$). $\endgroup$ – z100 Jul 9 '16 at 17:22
  • $\begingroup$ @z100 I was not saying about sum of numbers on a single dice, but on a single face. And never did i ever say that my intuition can't be wrong! $\endgroup$ – ABcDexter Jul 9 '16 at 17:34
14
$\begingroup$

The answer is

74

First I show that a lower number is not possible:

The best way we could achieve 216 as a sum of three distinct integers is 71 + 72 + 73. That is the only way 216 could be achieved without using an integer larger than 73. It is however not possible to fill in the rest of the sides using distinct integers. If we try to fill in the rest of the numbers we will first find having the number 70 on the first die is the only way to get 215 without reusing a number. Next we will see that the first die also needs 69 in order for 214 to be possible. This will continue until all six sides on the first die are used, and we are left with no way to get 210.

This establishes a lower bound. The upper bound is established by providing an actual solution.

First die:

9, 12, 15, 63, 66, 69

Second die:

44, 45, 46, 71, 72, 73

Third die:

-52, -43, -34, 56, 65, 74

To find the numbers, I first tried base-6 with the numbers on each die offset to get the correct maximums. But that approach did not work as the one die with six consecutive numbers always ended up conflicting with another die where the largest two numbers differ by 6.

Instead I realized that since 2$\times$3 = 6, I can alternate between base-2 and base-3 (similar to how historical number systems have alternated between base-6 and base-10). And I did not have to assign consecutive digit positions to each die. With that approach, trial and error led to a solution after about a handful of attempts.

The actual bases I ended up using, from least significant to most significant were:


  • 1s position base 3 (on second die)
  • 3s position base 3 (on first die)
  • 9s position base 3 (on third die)
  • 27s position base 2 (on second die)
  • 54s position base 2 (on first die)
  • 108s position base 2 (on third die)

So in the case of the first die, the values I need to subtract from the maximum to get each other value are 3 and 6 because it has the 3s position, as well as 54 because it has the 54s position.

$\endgroup$
  • $\begingroup$ This looks really nice! Could you add some more detail to show how you would get all of the sums using your dice? $\endgroup$ – Shagnik Jul 10 '16 at 15:51
  • $\begingroup$ I wonder how far up we can push the lower bound. According to my back-of-the-envelope calculations, 74 68 62 56 50 44, 73 72 71 -35 -36 -37 and 69 66 33 30 -3 -6 also work. $\endgroup$ – Neil Jul 10 '16 at 18:27
  • $\begingroup$ @Shagnik There are two ways to verify that. Either verify that the numbers match up with the mixed-base number system used to choose the values. (I have added the exact bases used to my answer, and example calculations for the first dice). The other way is to verify all 216 possible combinations (which I let a computer do after having computed the values on the dice by hand). $\endgroup$ – kasperd Jul 10 '16 at 18:44
  • $\begingroup$ @Neil Your numbers also work. I haven't tried how high a value would be possible for the lowest number. But it certainly will be necessary to have at least one negative number somewhere. It seems likely that the bound on how high you can push the lowest number depends on whether you want to maintain the current maximum value, or whether you will accept a higher maximum value. $\endgroup$ – kasperd Jul 10 '16 at 18:51
  • 1
    $\begingroup$ According to my calculations -37 is the highest lower bound (7 of 72 solutions) while still keeping the upper bound of 74. (The lowest lower bound I found was -89: 69 68 63 62 57 56, 73 55 1 -17 -71 -89 and 74 72 70 38 36 34.) $\endgroup$ – Neil Jul 10 '16 at 20:53
10
$\begingroup$

A lower bound is

$73$: when getting the sum to be $216$, the average value must be $72$. However, this would require three of the numbers to be the same. Hence at least one number must be $73$ or bigger.

An upper bound is

$77$: achieved by the dice $\{ 72, 73, 74, 75, 76, 77 \}, \{ 40, 46, 52, 58, 64, 70 \}$ and $\{ -111, -75, -39, -3, 33, 69 \}$. These dice come from taking the units, sixes and thirty-sixes in the base-six representation, which represent the integers between $0$ and $215$ uniquely. We then shift the units by $72$, the sixes by $40$ and the thirty-sixes by $-111$ to get the numbers from $1$ to $216$ without repeating any faces of the dice.

$\endgroup$
  • 1
    $\begingroup$ I don't understand what question your second block answers. Why can't I just take a very large integer $N$ and add it to each side on your first die and subtract it from each side on your third die? $\endgroup$ – Peregrine Rook Jul 9 '16 at 22:21
  • 3
    $\begingroup$ @PeregrineRook it is showing what an upper bound on the minimum achievable largest integer is (rather than an upper bound on the largest integer). $\endgroup$ – Jonathan Allan Jul 9 '16 at 22:49
7
$\begingroup$

The smallest number I could find was 75. I think the way to prove it is to prove that the only way to get 216 distinct consecutive numbers by summing 3 three dice is for each die to be of the form, $a + n*6^b$

Here is what I did:

I started with these 3 sequences which are able to reproduce the number 1-216. Basically this is the first three digits of a base 6 representation. Each row represents one die.

1, 2, 3, 4, 5, 6
0, 6, 12, 18, 24, 30
0, 36, 72, 108, 144, 180

Then I added or subtracted from each row (die). The numbers I used were +68 +37 -105. Since the sum of these 3 numbers is 0, the new set is still able to produce the numbers 1-216:

Here are the resulting 3 dice:

69, 70, 71, 72, 73, 74
37, 43, 49, 55, 61, 67
-105, -69, -33, 3, 39, 75

I was able to find an option where the largest number was 73, but it required a repeat. The only way I could find where there were no repeats was to have every number in the first row (die) greater than every number in the second row (die)

$\endgroup$
  • $\begingroup$ That's a very nice construction - I don't know why I didn't try to make two of the faces bigger than 72. I suspect your answer may be optimal; it would be nice to see a proof! $\endgroup$ – Shagnik Jul 10 '16 at 7:35
4
$\begingroup$

Edit: This is wrong, I missed the part about the numbers needing to be distinct.

The largest die must be

72

or more. Otherwise, the largest number you could roll would be

71 + 71 + 71 = 213 < 216.

Here's a labeling which achieves that minimum:

67, 68, 69, 70, 71, 72
42, 48, 54, 60, 66, 72
-108, -72, -36, 0, 36, 72

$\endgroup$
  • 2
    $\begingroup$ In the specification of the puzzle, the 18 numbers are meant to be distinct, but you have 72 repeated three times here. $\endgroup$ – Shagnik Jul 9 '16 at 17:21
  • $\begingroup$ @Mike Earnest, Upvoted the answer, I believe it will be modified quickly with a correct solution for 73 or 74 or 75. $\endgroup$ – z100 Jul 9 '16 at 17:25
  • $\begingroup$ Whoops! Totally missed that part! $\endgroup$ – Mike Earnest Jul 9 '16 at 17:27
  • 1
    $\begingroup$ Decreasing all values on one die by one while increasing all values on another die will achieve the lower bound shown by Shagnik. Assuming the other conditions for the sum hold, of course. $\endgroup$ – Nij Jul 9 '16 at 19:40
  • $\begingroup$ @Nij Good idea to use transformation which preserves the sum, but 66, 67 and 71 does not allow it. $\endgroup$ – z100 Jul 9 '16 at 22:04
2
$\begingroup$

I wrote a program to search for such dice.
It found $29$ with maximum faces of

$74$
as has already been stated by kasperd in another answer.

It finds none with maximum faces of less.

Here are those dice:

(the sixth one is kasperd's example)

 1: [-73,-70, -1,  2, 71, 74],  [ 62, 63, 64, 68, 69, 70],  [ 12, 24, 36, 48, 60, 72]
 2: [-88,-70,-16,  2, 56, 74],  [ 54, 57, 60, 63, 66, 69],  [ 35, 36, 37, 71, 72, 73]
 3: [-70,-52,-34, 38, 56, 74],  [ 54, 57, 60, 63, 66, 69],  [ 17, 18, 19, 71, 72, 73]
 4: [-79,-70, -7,  2, 65, 74],  [ 27, 30, 33, 63, 66, 69],  [ 53, 54, 55, 71, 72, 73]
 5: [-79,-70, -7,  2, 65, 74],  [ 45, 48, 51, 63, 66, 69],  [ 35, 36, 37, 71, 72, 73]
 6: [-52,-43,-34, 56, 65, 74],  [  9, 12, 15, 63, 66, 69],  [ 44, 45, 46, 71, 72, 73]
 7: [-52,-43,-34, 56, 65, 74],  [ 36, 39, 42, 63, 66, 69],  [ 17, 18, 19, 71, 72, 73]
 8: [-76,-70, -4,  2, 68, 74],  [ 18, 21, 42, 45, 66, 69],  [ 59, 60, 61, 71, 72, 73]
 9: [-73,-70, -1,  2, 71, 74],  [ 56, 57, 58, 68, 69, 70],  [ 18, 24, 42, 48, 66, 72]
10: [-76,-70, -4,  2, 68, 74],  [ 42, 45, 54, 57, 66, 69],  [ 35, 36, 37, 71, 72, 73]
11: [ 47, 50, 59, 62, 71, 74],  [-40,-39,-38, 68, 69, 70],  [ -6,  0, 30, 36, 66, 72]
12: [-73,-70, -1,  2, 71, 74],  [ 50, 51, 52, 68, 69, 70],  [ 24, 30, 36, 60, 66, 72]
13: [-46,-40,-34, 62, 68, 74],  [ 30, 33, 48, 51, 66, 69],  [ 17, 18, 19, 71, 72, 73]
14: [-73,-70, -1,  2, 71, 74],  [ 32, 33, 34, 68, 69, 70],  [ 42, 48, 54, 60, 66, 72]
15: [ 44, 50, 56, 62, 68, 74],  [ -6, -3, 30, 33, 66, 69],  [-37,-36,-35, 71, 72, 73]
16: [-82,-70,-10,  2, 62, 74],  [ 23, 25, 47, 49, 71, 73],  [ 60, 61, 64, 65, 68, 69]
17: [-82,-70,-10,  2, 62, 74],  [ 59, 61, 63, 65, 67, 69],  [ 24, 25, 48, 49, 72, 73]
18: [-58,-46,-34, 50, 62, 74],  [ 59, 61, 63, 65, 67, 69],  [  0,  1, 36, 37, 72, 73]
19: [-76,-70, -4,  2, 68, 74],  [ 29, 31, 33, 65, 67, 69],  [ 48, 49, 60, 61, 72, 73]
20: [-76,-70, -4,  2, 68, 74],  [ 53, 55, 57, 65, 67, 69],  [ 24, 25, 48, 49, 72, 73]
21: [-46,-40,-34, 62, 68, 74],  [ 11, 13, 15, 65, 67, 69],  [ 36, 37, 54, 55, 72, 73]
22: [-38,-36,-34, 70, 72, 74],  [ 32, 33, 50, 51, 68, 69],  [  7, 13, 19, 61, 67, 73]
23: [ 52, 54, 56, 70, 72, 74],  [ -4, -3, 32, 33, 68, 69],  [-47,-41,-35, 61, 67, 73]
24: [-46,-40,-34, 62, 68, 74],  [ 47, 49, 51, 65, 67, 69],  [  0,  1, 36, 37, 72, 73]
25: [-74,-70, -2,  2, 70, 74],  [ 19, 21, 43, 45, 67, 69],  [ 56, 57, 64, 65, 72, 73]
26: [-74,-70, -2,  2, 70, 74],  [ 23, 25, 47, 49, 71, 73],  [ 52, 53, 60, 61, 68, 69]
27: [-74,-70, -2,  2, 70, 74],  [ 51, 53, 59, 61, 67, 69],  [ 24, 25, 48, 49, 72, 73]
28: [-74,-70, -2,  2, 70, 74],  [ 55, 57, 63, 65, 71, 73],  [ 20, 21, 44, 45, 68, 69]
29: [-42,-38,-34, 66, 70, 74],  [ 43, 45, 55, 57, 67, 69],  [  0,  1, 36, 37, 72, 73]

The program works by first finding all ($71$ after accounting for die permutation) dice with faces valued between $0$ and $215$ for which the rolls cover the range $[0,215]$ such that the only repeated faces are three $0$s, such as that given by Tony Ruth (but with his $1$s dice shifted down by $1$), or one I found manually when thinking about the program design:

[[0,  1,  2, 108, 109, 110],
 [0,  3,  6,   9,  12,  15], 
 [0, 18, 36,  54,  72,  90]]

It then attempts to add and subtract from the three dice such that the end result is to add $1$ (fitting the range $[1,216]$) with no repeated faces.

Note: If anyone can work out how I could go about avoiding filtering out $5$ out of every $6$ "zero dice" performed by zeroDiceFiltered on those dice found by zeroDice I'd appreciate the advice!

Python code:

from itertools import permutations, product

def zeroDice(curDice=[[0],[0],[0]], curRolls=set((0,)), curStart=1):
    if all(len(die) == 6 for die in curDice):
        yield curDice
    else:
        for dieIndex in range(3):
            if len(curDice[dieIndex]) < 6:
                for face in range(curStart, 215):
                    if face not in curRolls:
                        newRolls = set(curRolls)
                        for otherFaces in product(*[die for i, die in enumerate(curDice) if i != dieIndex]):
                            roll = sum(otherFaces) + face
                            if roll > 215 or roll in newRolls:
                                break
                            newRolls.add(roll)
                        else:
                            if all(r in newRolls for r in range(curStart, face)):
                                newDice = [die + [face] if i == dieIndex else list(die) for i, die in enumerate(curDice)]
                                for dice in zeroDice(newDice, newRolls, face + 1):
                                    yield dice

def zeroDiceFiltered():
    made = set()
    for zDice in zeroDice():
        rep = tuple(tuple(die) for die in zDice)
        for pRep in permutations(rep):
            if pRep in made:
                break
        else:
            made.add(rep)
            yield rep

def uniqueDiceFromZeroDice(zDice, maxFace):
    for dieIndex, deltaDie in enumerate(zDice):
        delta = maxFace - deltaDie[-1]
        if delta < 0:
            stop = 2 - delta
            step = 1
        else:
            stop = 1 - delta
            step = -1
        diff = 1 - delta
        for otherDelta1 in range(0, stop, step):
            otherDelta2 = diff - otherDelta1
            dice = [[], [], []]
            for deltaIndex, dieDelta in enumerate((delta, otherDelta1, otherDelta2)):
                for face in zDice[dieIndex - deltaIndex]:
                    nv = face + dieDelta
                    if nv <= maxFace:
                        dice[deltaIndex].append(nv)
                    else:
                        break
                else:
                    continue
                break
            else:
                if len(set(face for die in dice for face in die)) == 18:
                    yield dice

def uniqueDice(maxFaceRange=range(72, 75)):
    for zDice in zeroDiceFiltered():
        for maxFace in maxFaceRange:
            for dice in uniqueDiceFromZeroDice(zDice, maxFace):
                yield dice

Output the aligned values given above:

>>> for i, d in enumerate(uniqueDice()):
...     print('{0:>2}: [{1}],  [{2}],  [{3}]'.format(i + 1, ','.join('{0:>3}'.format(v) for v in d[0]), ','.join('{0:>3}'.format(v) for v in d[1]), ','.join('{0:>3}'.format(v) for v in d[2])))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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