Posted 24 Aug 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. 0 Share this post Link to post Share on other sites

0 Posted 25 Aug 2013 1, 2, 8, 40, 91, 120, 140, 144 0 Share this post Link to post Share on other sites

0 Posted 25 Aug 2013 1, 3, 6, 35, 75, 108, 121, 130 0 Share this post Link to post Share on other sites

0 Posted 26 Aug 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... 0 Share this post Link to post Share on other sites

0 Posted 26 Aug 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. 0 Share this post Link to post Share on other sites

0 Posted 20 Sep 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? 0 Share this post Link to post Share on other sites

0 Posted 25 Sep 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. 0 Share this post Link to post Share on other sites

0 Posted 25 Sep 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. 0 Share this post Link to post Share on other sites

0 Posted 30 Sep 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.) 0 Share this post Link to post Share on other sites

0 Posted 9 Oct 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. 0 Share this post Link to post Share on other sites

0 Posted 11 Oct 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 11 Oct 2013 by Anza Power 0 Share this post Link to post Share on other sites

0 Posted 18 Oct 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?) 0 Share this post Link to post Share on other sites

0 Posted 8 April 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. 0 Share this post Link to post Share on other sites

0 Posted 10 April 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). 0 Share this post Link to post Share on other sites

Posted

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.

## Share this post

## Link to post

## Share on other sites