• 0

dice problem

Question

Posted · Report post

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

14 answers to this question

  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 · Report post

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 · Report post

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 · Report post

highest numbered side

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 · Report post

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 · Report post

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 · Report post

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 (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

 

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.