Dice with k-sides

Computer Science Level 4

A standard 6 sided die rolls the numbers 1 through 6 with equal probability. Likewise, a k -sided die rolls the numbers from 1 through k with equal probability.

Let D(S, N, k) equal the number of ways to roll a total of S with N k -sided dice. D(3, 2, 6) = 2 because you can roll a 3 with a (1, 2) or a (2, 1).

Let T = D(20, 7, 12) + D(31, 6, 4) + D(15, 3, 7) + D(111, 17, 7) + D (17, 3, 57) + D(1, 2, 2) + D(10, 17, 12) + D(9, 3, 0).

What are the last three digits of T?

The answer is 413.

1 solution

Agnishom Chattopadhyay
May 11, 2014

Mathematica Code:

Dice[S_, N_, k_] := Coefficient[Expand[Sum[x^y, {y, 1, k}]^N], x, S]

In[51]:= Dice[20, 7, 12] + Dice[31, 6, 4] + Dice[15, 3, 7] + 
 Dice[111, 17, 7] + Dice[17, 3, 57] + Dice[1, 2, 2] + 
 Dice[10, 17, 12] + Dice[9, 3, 0]

Out[51]= 762413

Basically it picks the coefficient of $x^S$ in $\left ( \sum_{i=1}^{k}x^i \right )^N$

Since I only can use C++, inclusion-exclusion principle can be useful

Just count the ways separating S into N dices and remove the possibilities of partition which contain more than K using inclusion-exclusion principle

Afrizal Fikri - 6 years, 10 months ago

Dice with k-sides

The answer is 413.

1 solution

0 pending reports