phil1882 13 Posted August 24, 2013 Report Share Posted August 24, 2013 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. Quote Link to post Share on other sites

0 superprismatic 11 Posted August 25, 2013 Report Share Posted August 25, 2013 1, 2, 8, 40, 91, 120, 140, 144 Quote Link to post Share on other sites

0 Anza Power 9 Posted August 25, 2013 Report Share Posted August 25, 2013 1, 3, 6, 35, 75, 108, 121, 130 Quote Link to post Share on other sites

0 Pickett 13 Posted August 26, 2013 Report Share Posted August 26, 2013 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... Quote Link to post Share on other sites

0 Anza Power 9 Posted August 26, 2013 Report Share Posted August 26, 2013 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. Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted September 20, 2013 Report Share Posted September 20, 2013 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? Quote Link to post Share on other sites

0 phil1882 13 Posted September 20, 2013 Author Report Share Posted September 20, 2013 highest numbered side Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted September 25, 2013 Report Share Posted September 25, 2013 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. Quote Link to post Share on other sites

0 phil1882 13 Posted September 25, 2013 Author Report Share Posted September 25, 2013 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. Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted September 30, 2013 Report Share Posted September 30, 2013 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.) Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted October 9, 2013 Report Share Posted October 9, 2013 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. Quote Link to post Share on other sites

0 Anza Power 9 Posted October 11, 2013 Report Share Posted October 11, 2013 (edited) 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 Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted October 18, 2013 Report Share Posted October 18, 2013 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?) Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted April 8, 2015 Report Share Posted April 8, 2015 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^{2} + x^{3} + ... + 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. Quote Link to post Share on other sites

0 Quantum.Mechanic 0 Posted April 10, 2015 Report Share Posted April 10, 2015 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). Quote Link to post Share on other sites

## Question

## phil1882 13

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.

## Link to post

## Share on other sites

## 14 answers to this question

## Recommended Posts

## Join the conversation

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