BrainDen.com - Brain Teasers
• 0

# dice problem

## Question

you want to throw three 8 sided dice; such that: all three dice are numbered the same, and 120 different totals are possible; and the maximum number is as small as possible.

with 7 sided dice, the best possible is: 1, 2, 8, 51, 60, 79, 83

but your challenge is to go one more side.

## Recommended Posts

• 0

1, 2, 8, 40, 91, 120, 140, 144

##### Share on other sites
• 0

1, 3, 6, 35, 75, 108, 121, 130

##### Share on other sites
• 0

you want to throw three 8 sided dice; such that: all three dice are numbered the same, and 120 different totals are possible; and the maximum number is as small as possible.

with 7 sided dice, the best possible is: 1, 2, 8, 51, 60, 79, 83

but your challenge is to go one more side.

but I'm only seeing 84 different totals possible with those 7 sides:
[3, 4, 5, 6, 10, 11, 12, 17, 18, 24, 53, 54, 55, 60, 61, 62, 63, 64, 67, 69, 70, 76, 81, 82, 83, 85, 86, 87, 88, 89, 92, 93, 95, 99, 103, 104, 110, 112, 113, 119, 121, 122, 128, 131, 132, 135, 136, 138, 140, 141, 142, 144, 145, 147, 151, 153, 159, 160, 162, 163, 164, 166, 167, 168, 170, 171, 174, 180, 181, 185, 190, 194, 199, 203, 209, 213, 217, 218, 222, 226, 237, 241, 245, 249]
However, using that same program, I validated that both superprismatic and Anza Power's solutions do indeed have 120 different totals combinations...I'm still working to see if I can get lower than Anza's, but so far, no luck...
##### Share on other sites
• 0

There is no mistake, 84 is the maximum for 7 sides, 120 is the maximum for 8 sides...

In general, (n)*(n+1)*(n+2)/6 is the maximum for n sides.

##### Share on other sites
• 0

you want to throw three 8 sided dice; such that: all three dice are numbered the same, and 120 different totals are possible; and the maximum number is as small as possible.

with 7 sided dice, the best possible is: 1, 2, 8, 51, 60, 79, 83

but your challenge is to go one more side.

Maximum sum, or highest numbered side?

##### Share on other sites
• 0

highest numbered side

##### Share on other sites
• 0

Brute force searches will take a long time. Is there any literature on the structure of solutions?

I've looked at sum-free sets, triple-free sets, and prime number of measurement, to name a few, but none seem quite useful in this problem.

##### Share on other sites
• 0

http://www.mathpuzzle.com/ no, or at least not much.

we know it for d2 -d7, and if you want to cheat you can look at the solution for d8 at IBM's page, but as far as I'm aware there's no general solution.

##### Share on other sites
• 0

It seems that this puzzle is NP-hard and not NP-complete (if I understand this correctly), as there is not an efficient way to prove that the solution is minimal, without an exhaustive search for a better one. (Though a solution can be proved to be valid easily enough, just not minimal.)

##### Share on other sites
• 0

Faces (1,4,12,24,87,94,123,125) = 119 distinct sums. 130 might be the answer though.

Still, lots of brute forcing, not much elegance.

##### Share on other sites
• 0

It seems that this puzzle is NP-hard and not NP-complete (if I understand this correctly), as there is not an efficient way to prove that the solution is minimal, without an exhaustive search for a better one. (Though a solution can be proved to be valid easily enough, just not minimal.)

Actually it's O(1).

Your comment got me thinking, I couldn't say that it's in NP because there is no n in the problem, We have 130 as a starting point and we want to see if any of the binome(129,8) dice combinations have 120 different sum...

Unless you are referring to the problem with "N-sided Dice", then yeah that's crazy exponential...

Edited by Anza Power
##### Share on other sites
• 0

It seems that this puzzle is NP-hard and not NP-complete (if I understand this correctly), as there is not an efficient way to prove that the solution is minimal, without an exhaustive search for a better one. (Though a solution can be proved to be valid easily enough, just not minimal.)

Actually it's O(1).

Your comment got me thinking, I couldn't say that it's in NP because there is no n in the problem, We have 130 as a starting point and we want to see if any of the binome(129,8) dice combinations have 120 different sum...

Unless you are referring to the problem with "N-sided Dice", then yeah that's crazy exponential...

If you assume a specific problem, with specific inputs, then yes, people get lazy and say O(1), because the problem itself is a constant. That's cheating.

NP-complete requires a polynomial method to prove that a given solution is valid for a problem in NP. And these are generalized problems, so we never use O() notation for the specific ones (what would be the point?).

To be NP-complete, verifying a solution to the "smallest max face value for distinct sums of (s=sides, d=dice)" would have to scale as some power of s and/or d. There seems to be no way to do this short of duplicating the search, and the search is exponential (perhaps (s**d)**k?)

##### Share on other sites
• 0

At http://www.numericana.com/answer/dice.htm#split I've found an interesting method.

It seems we need to find some M such that 1 + x + x2 + x3 +  ...  + xM-1 is a cube, and the polynomial cube root must have all nonnegative coefficients. If the largest face is F, then M = 3F+1. (The cube root could itself be composite, though I'm not sure if being composite implies anything about the minimization of F.)

Given that we have a solution for F=130, then F=129 implies M=388.

On that page there is also mention of cyclotomic factors, which I'll have to go read up on.

##### Share on other sites
• 0

you want to throw three 8 sided dice; such that: all three dice are numbered the same, and 120 different totals are possible; and the maximum number is as small as possible.

with 7 sided dice, the best possible is: 1, 2, 8, 51, 60, 79, 83

but your challenge is to go one more side.

Maximum sum, or highest numbered side?

But according to Wolfram Alpha, x^388-1/x-1 isn't a cube (it's rather ugly).

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.