How to find the probability that when throwing N dice, the sum of points will be in this range?
Given the number of hexagon cubes - N. In the next row, there are 2 numbers - the range (left,right). How to find the probability that when throwing N dice, the sum of points will be in the range (left,right)?
Limitations:
N = 100
left, right <= 600
Examples :)
1
1 3
2
11 12
Answers:
0.5
0.083
Explanation: 1) The possible numbers that will fall out are 1, 2, 3, and all (6**N = 6).
Total: probability - 3 / (6**N = 6) = 0.5.
2) Possible numbers that will fall out - (5 + 6), (6 + 5), (6 + 6).
Total: probability - 3 / (6**N = 36) = 3 / 36 = 0,083.
I tried to solve the problem algorithmically, find all permutations of length N in the array (1,2,3,4,5,6), and then check that the sum is in the range (left,right).
Code:
from itertools import product
n = int(input())
a,b = map(int,input().split())
arr = ["1","2","3","4","5","6"]
res = ["".join(i) for i in product(arr, repeat = n)]
k = 0
for i in range(0,len(res)):
string = res[i]
s = 0
for j in range(0,n):
s+=int(string[j])
if s>=a and s<=b:
k+=1
print(k / (6**n))
2 answers
Too long for a comment-explanation of the thick hint @pavel
Create a table Nx6N and fill it in row by row.
What's in cell A[K][P]? number of options to score the sum of P when throwing K cubes.
The amount of P when using K dice can be obtained by dropping one point on the K th cube and the sum of P-1 on K-1 cubes.
The same amount can be obtained when two points are dropped on the K th cube and the sum of P-2 on the K-1 cubes.
Etc. up to 6 points.
1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 1 1 1 0 0 0 0 0 0
2 0 1 2 3 4 5 6 5 4 3 2 1
Simple implementation in Delphi:
function SumProb(n, a, b: Integer): Double;
var
Table: array of array of Int64;
i, j, k: integer;
begin
SetLength(Table, n + 1, 6 * n + 1);
for i := 1 to 6 do
Table[1, i] := 1;
for i := 2 to n do
for j := i to 6 * i do
for k := Min(6, j) downto 1 do
if j - k > 0 then
Table[i, j] := Table[i, j] + Table[i - 1, j - k];
Result := 0;
for i := a to b do
Result := Result + Table[n, i];
for i := 1 to n do
Result := Result / 6;
end;
The probability of falling into the range is equal to the sum of the probabilities of each discrete value falling out of the range.
The probability of each discrete value of the sum S falling out is equal to the ratio of the number of ways to score such a sum to the number of possible outcomes. The latter is 6N.
And the number of ways to get the sum S is
Sum for i from 0 up to [(S-N)/6] summands of the form (-1)i CiN CN-1S-6i-1
You can also calculate this value "manually": by the inclusion-exclusion method (as I described in detail here) or through generating functions. The above is a ready-made formula.
For example, for the problem 2 11 12, we find the number of ways to throw out the sums 11 and 12, which, according to the above formula, 2 and 1, respectively. Then the probability is (1 + 2) / 36 = 0.08(3).