Lesson 2, Problem 4 ~ Challenge

How many ways can you get at least one 3 after three dice rolled?

2 methods:

1. Counting the wrong thing

There are 5 ways to NOT get a 3 on the first die. There are 5 ways to NOT get a 3 on the second die. There are 5 ways to NOT get a 3 on the third die. There are 125 ways to roll all the dice with no 3. There are 216 total ways to roll the dice. Subtracting, we find 91 ways to roll the dice WITH a 3.

2. Principle of Inclusion-Exclusion

Of the 216 dice rolls:

36 have a 3 for the first die
36 have a 3 for the second die
36 have a 3 for the third die
6 have a 3 for the first and second dice
6 have a 3 for the second and third dice
6 have a 3 for the first and third dice
1 has a 3 for all three dice

and using the Principle of Inclusion-Exclusion, we add 36+36+36-6-6-6+1. That's 91!

An explanation of PIE:

Let's say we want to count thenumber of people of who go to Aops or this website.

What happens if just add up the number of people of who go to Aops and the number of people who go to this webiste.

Then we would be overcunting. But what do we overcount? People who only go to Aops are counted once. People who only go here are counted once. But what about people who go to both?

They are counted twice! So we need to substract the number of people who go to both so that they are counted once.

Now: How many people here are good at algebra, couting, or geometry?

If we add the number that are good at algebra, and the number that we are ggod at counting and the number othat are good at geo, we get an over count!
How many times have we counted people who are good at algebra, good at geo, but not good at counting? 2 times: once for the number that are good at algebra, oncce for the number of people who are good at counting. So let's substract them. We do the same for the other people who are good at exactly two subjects.

Now, what about the people who are good at all 3? They get counted 3 times originally, but then we subtracted 3 times. So we need to ADD this number.

Hmm... Is there a pattern? Try it for greater n and you will find a pattern!