dice problem

[phil1882]

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.

[superprismatic]

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

[Anza Power]

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

[Pickett]

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...

[Anza Power]

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.

[Quantum.Mechanic]

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?

[phil1882]

highest numbered side

[Quantum.Mechanic]

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.

[phil1882]

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.

[Quantum.Mechanic]

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.)

[Quantum.Mechanic]

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.

[Anza Power]

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 October 11, 2013 by Anza Power

[Quantum.Mechanic]

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?)

[Quantum.Mechanic]

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 + x² + x³ +  ...  + x^M-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.

[Quantum.Mechanic]

 

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).