# How do I think about solving this sort of problem without having to count intersections?

I have asked this sort of question before, and I have a new similar question here. The latter question got me thinking about this specific question.

When throwing 5d20 (rolling five twenty sided polyhedral dice), what is the probability of three or more dice having a result of '5' or less, of the three, two must have a result of '4' or less? (The remaining two dice of the five I don't care about)

(Example: Roll 5d20, with a result of (15,4,7,2,1) on the (1st, 2nd, 3rd, 4th, and 5th) die. This would be considered a success, because the '4' is five or less, and the '2' & '1' are four or less.)

I can do some simple calculations like

• What are all the permutations of 5d20? $20\times 20\times 20\times 20\times 20 = 3.2$ million

• What are the ways of arranging '5','4','4', x , x . (where x is not '4', or '5')

1) 544xx, 54x4x, 54xx4, 5x44x, 5x4x4, 5xx44, (6 ways with '5' in 1st position)

2) 454xx, 45x4x, 45xx4, x544x, x54x4, x5x44, (6 ways with '5' in 2nd position)

3) ... (6 ways with '5' in 3rd position)

For a total of 30 different ways of arranging the 544xx combination. If the x can represent any dice face other than '5' or '4' (to avoid counting duplicates), that gives me $30\times 18\times 18 = 9720$ successes so far. But, there are so many more successes that I haven't counted. I have to worry about the (5,4,4,4,x) throws which I didn't count before because I didn't want to worry about duplication, and the (5,4,4,4,4) throws which is admittedly small (only 5 permutations of the 3.2 million). Then there are all the other permutations I need to count.

1) (5,4,3,x,x) throws, (5,4,2,x,x) throws, (5,4,1,x,x) throws,

2) (5,3,3,x,x) throws, (5,3,2,x,x) throws, (5,3,1,x,x) throws,

3) ...

Each time I have to worry about the intersection of the permutations (i.e. In the above examples, I need to worry about double counting results where the 'x' represents everything except the dice I am counting all the permutations of for a certain the combinations of dice.), and each time I have to worry about missing counting a success. This can be alleviated somewhat by counting the failures, and making sure that the successes+failures adds up to 3.2 million total permutations that I know exist, but this is ripe for mistakes.

• I can brute force it with a simple computer program, (3.2 million permutations is only a few seconds). This is a rather easy solution for me because I am a programmer, and not a mathematician

Note: The brute force solution in pseudo code is

iterate over die_1 from 1 to 20
iterate over die_2 from 1 to 20
iterate over die_3 from 1 to 20
iterate over die_4 from 1 to 20
iterate over die_5 from 1 to 20 {
bubblesort die_1 through die_5 (biggest die is die_5)
if die_3 is 5 or less, and die_2 is 4 or less, success_count increment
else failure_count increment
}


The result of the above is 300,704 successes (one '5' or less, and two additional dice '4' or less), out of 3.2 million.

but, what I really want to know is...

• How should I think about solving this sort of problem so that I can either easily identify intersections between sets, or avoid double counting the intersections?

• Is this even possible, or should I just brute force my solutions?

Note: I just noticed that I could solve this question easier by thinking about it as a tree, and a single d20 being rolled. For each roll, I am either closer to obtaining a success, or not.

1st Roll: 1/20 '5'
4/20 '4' or less
15/20 no successes

2nd Roll: from '5'  :  4/20 '4'or less
from '5'  : 16/20 no additional successes.
from '4'< :  1/20 '5'
from '4'< :  4/20 '4' or less
from '4'< :  1/20 no additional successes.
from 'no success' :  1/20 '5'
from 'no success' :  4/20 '4' or less.
from 'no success' : 15/20 no successes

3rd Roll: keep applying odds at each step.


If complete success (found 3 dice that fit the criteria), multiply result by 20 to the power of X, where X is the number of remaining throws. This tree can also be used to find the failures at each step. (Example: if the 1st & 2nd & 3rd die rolls were all greater than 6, then that part of the tree is a failure. Multiply the number of cases (15*15*15) times the remaining die roll (20*20) to get the number of failures for that part of the tree. All branches of the tree (successes and failures) will total the number of permutations (3.2 million).

-
Note that * is a special character in this site, which triggers italics or boldface; also, you were using * to mean two different things in the same post: multiplication in some places, and a placeholder in others. It is very bad form, and very confusing, to use the same symbol to mean two different things in the same argument. I've edited to replace these problems. Please double-check to make sure I didn't change the meaning by mistake. – Arturo Magidin Jan 30 '12 at 16:53
I'm not clear on your "three dice with 5 or less, two dice with 4 or less". Do you simply mean "at least one five and two fours"? – Arturo Magidin Jan 30 '12 at 16:55
@ArturoMagidin, it must have been a typo. What I meant was at least one die with 5 or less, and at least two other/different dice with 4 or less. This is of course different than at least one '5', and two '4's. At least one '5' & two '4's doesn't count a result of '3', '2', '2', 'X', 'X' which would be a success in my example. – user1873 Jan 31 '12 at 2:44
I guess my confusion comes from the fact that a roll in which at least two dice are 4 or less already guarantees one dice that is five or less. I guess what you really mean is that at least three dice are not 6, and of those three, at most one is equal to 5. Yes? – Arturo Magidin Jan 31 '12 at 3:35
@ArturoMagidin, yes. That isn't how I would word it, but you do have it correct. At least three dice are not "6 or more" (there exists at most two dice that have values of 6 or more), and of the three that are not 6 or more, at most one of them may have a value of 5. Is there some easier way of stating this? Each time I rewrite it, it seems less intuitive. – user1873 Jan 31 '12 at 4:29

## 2 Answers

Let $X$ be the number of rolls of 4 or less, $Y$ the number of rolls of exactly 5. You want the probability that $X+Y \ge 3$ and $X \ge 2$. This is $\sum_{x=2}^5 \sum_{y=\min(3-x,0)}^{5-x} P(X=x, Y=y) = P(X=2,Y=1) + P(X=2,Y=2) + P(X=2,Y=3) + P(X=3,Y=0)+P(X=3,Y=1)+P(X=3,Y=2)+P(X=4,Y=0)+P(X=4,Y=1)+P(X=5,Y=0$ where (since on a single die you have probability $4/20$ of getting 4 or less and $1/20$ of getting 5) $$P(X=x, Y=y) = \frac{5!}{x! y! (5-x-y)!} (4/20)^x (1/20)^y (15/20)^{5-x-y}$$

-
although this is an answer to my example problem (is it correct? do you get 300,704), I was looking at a more general way at looking at this type of problem. When I thought about the question again in the terms of a tree, and how close I was to achieving my objective, it reminded me of a markov chain. My other die question (small straight 6d6) linked above didn't use the same method to achieve the solution. Brute force was the easiest solution for many of the people who provided answers. – user1873 Jan 31 '12 at 4:35

This is rather unimaginative, but you could do it in the straightforward way:

If you want "at least three rolls less than or equal to 5 and at least two less than or equal to 4":

First, split this up into the disjoint events

$\ \ A$: exactly three rolls less than or equal to 5 and at least two less than or equal to 4

$\ \ B$: exactly four rolls less than or equal to 5 and at least two less than or equal to 4

$\ \ C$: exactly five rolls less than or equal to 5 and at least two less than or equal to 4

Then split $A$ into the disjoint events :

$\ \ A_1$: exactly one roll equal to five and exactly two rolls less than 5

$\ \ A_2$: exactly three rolls less than 5

Split $B$ into the disjoint events :

$\ \ B_1$: exactly one roll equal to five and exactly three rolls less than 5

$\ \ B_2$: exactly two rolls equal to five and exactly two rolls less than 5

$\ \ B_3$: exactly four rolls less than 5

I'll leave it to you to split up $C$.

-
I don't think you got my meaning in the question. This might because you don't have a role playing background. I will update the question so that you can better understand it. 5d20 means "roll five 20-sided polyhedral dice". What I was interested was how to think about the problem in a general sense so that I can apply this to other dice questions (instead of brute forcing every example). – user1873 Jan 31 '12 at 2:47