Jump to content
BrainDen.com - Brain Teasers
  • 0
phil1882

dice problem

Question

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

14 answers to this question

Recommended Posts

  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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?

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

 

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

Share this post


Link to post
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...