phil1882 13 Report post 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 Share this post Link to post Share on other sites
0 superprismatic 11 Report post Posted August 25, 2013 1, 2, 8, 40, 91, 120, 140, 144 Quote Share this post Link to post Share on other sites
0 Anza Power 9 Report post Posted August 25, 2013 1, 3, 6, 35, 75, 108, 121, 130 Quote Share this post Link to post Share on other sites
0 Pickett 13 Report post 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 Share this post Link to post Share on other sites
0 Anza Power 9 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 phil1882 13 Report post Posted September 20, 2013 highest numbered side Quote Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 phil1882 13 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 Anza Power 9 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
0 Quantum.Mechanic 0 Report post 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 Share this post Link to post Share on other sites
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