Results 1 to 7 of 7

Math Help - Dice problem

  1. #1
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,080
    Thanks
    66

    Dice problem

    If I roll four six-sided dice and add up the three highest, I will generate a number
    from 3 to 18. There are 1296 (6^4) combinations possible. I want to calculate how
    many combinations will add up to each of the possible totals.

    By brute force methods I've determined that the distribution is as follows:

    Result, # of combinations yielding that result
    3 1
    4 4
    5 10
    6 21
    7 38
    8 62
    9 91
    10 122
    11 148
    12 167
    13 172
    14 160
    15 131
    16 94
    17 54
    18 21

    Although I can determine the distribution by brute force, I'm trying to find a method of
    calculating a certain sum: like, a formula that would give 91 as solution to sum of 9.
    Is it possible?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,080
    Thanks
    66
    Thanks; interesting; but does not apply to my problem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by Wilmer View Post
    Thanks; interesting; but does not apply to my problem.
    Learn to read. (Did you even look at the link?)

    It says: The probability of obtaining p points (a roll of p) on n s-sided dice can be computed as follows. The number of ways in which p can be obtained is the coefficient of x^p in

    f(x)=(x+x^2+...+x^s)^n

    f(x)=x^n(\frac{1-x^s}{1-x})^n

    f(x)=x^n(1-x^s)^n (1-x)^{-n}

    Here n=4, s=6.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Wilmer View Post
    If I roll four six-sided dice and add up the three highest, I will generate a number
    from 3 to 18. There are 1296 (6^4) combinations possible. I want to calculate how
    many combinations will add up to each of the possible totals.

    By brute force methods I've determined that the distribution is as follows:

    Result, # of combinations yielding that result
    3 1
    4 4
    5 10
    6 21
    7 38
    8 62
    9 91
    10 122
    11 148
    12 167
    13 172
    14 160
    15 131
    16 94
    17 54
    18 21

    Although I can determine the distribution by brute force, I'm trying to find a method of
    calculating a certain sum: like, a formula that would give 91 as solution to sum of 9.
    Is it possible?
    I can't think of a formula that's easier to calculate than brute force (any formula I could think of would involve considering a cumbersome number of cases), but I can offer a more efficient algorithm. The advantage will only really be felt if you are rolling more dice. Let n be the number dice rolled. Then brute force will be fast up to about n = 10, but beyond that this algorithm will be much better.

    Now, I'm not sure which generalisation to higher n you'd be more interested in: the total of the highest 3 dice, or of the highest n-1 dice. So, I'll just explain the algorithm for finding the distribution of total value of all dice; it'll be easier to follow that way anyway.

    I'll try to keep the syntax/notation general. We'll need an array/list notation of some sort; I'll use brackets, so if we have a list L, then the ith element will be denoted L[i]. Indexing starts at 0, not 1. So a list L of size 3 will have elements L[0], L[1], and L[2]. The size of the list will be denoted len(L).

    Start out with a list L1 of size 1, and set L1[0] = 1.

    This part will be performed n times: Create a new list L2 of size len(L1) + 6. All elements of L2 are initialised to 0. For all i from 0 to len(L1) - 1, and for all j from 1 to 6, increment L2[i+j] by L1[i]. Then set L1 = L2.

    The final L1 will contain the distribution of all possible totals. These numbers get large very fast, so for certain programming languages, care should be taken regarding integer overflow.

    I'd have to think how to modify the algorithm to only deal with certain dice rather than all dice, but I'm confident it could be done without too much trouble.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    After a little thought:

    The generalisation to highest n-1 dice is easy. Just make it a 2-dimensional list; we can think of the first index as rows and second index as columns, denoting the element at ith row and jth column as L[i][j] and denoting the size by rows(L) and cols(L). So in our variation, rows(L) will always be 7, containing the value of the lowest die, and cols(L) will increase by 6 each time as in the above description. Then the total of the highest n-1 dice is given by the column index minus the row index.

    There may be more efficient ways to do that, but it's straightforward and still fast.

    Then for highest 3 dice: using a 3-dimensional 7 x 7 x 7 list (whose size would not grow from one iteration to the next) would be straightforward, again maybe not the most efficient, but still fast.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,080
    Thanks
    66
    Quote Originally Posted by alexmahone View Post
    Learn to read. (Did you even look at the link?)

    It says: The probability of obtaining p points (a roll of p) on n s-sided dice can be computed as follows.
    OK...just signed up for a reading course; thanks for the suggestion.

    That is NOT a solution to my problem.
    What if we roll 11 dice, and want the total of highest 8 ?

    I think Mr. Undefined is correct: only way is a computer program.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. dice problem.
    Posted in the Statistics Forum
    Replies: 2
    Last Post: February 18th 2011, 04:45 PM
  2. Dice problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 23rd 2010, 07:10 AM
  3. Dice Problem
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: November 3rd 2008, 03:22 PM
  4. dice problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 15th 2008, 08:42 PM
  5. Dice Problem
    Posted in the Statistics Forum
    Replies: 5
    Last Post: January 15th 2008, 05:04 PM

Search Tags


/mathhelpforum @mathhelpforum