Poker Digest Vol. 2, No. 14, July 2 - 15, 1999
Bib Ladder took a sip of coffee, gently lowered his cup to the table and fixed me with a stare before commencing, ``Tell me, professor, how do you determine the chances of no one having a pocket pair in a 10-handed hold'em game? I've thought about this problem trying to use some of the material you've taught me, but I can't seem to get anywhere.''
``Bib, that problem requires a technique I have never shown you. If you are interested, I can start the lesson now, but we must progress slowly.''
``Yeah, I'm interested and I have some time now.''
``The technique is something called the Principle of Inclusion-Exclusion. It is useful for certain kinds of counting problems. I'll try to make clear the scenarios for which it is useful. It is a favorite technique of mine, and I always enjoy problems in which inclusion-exclusion comes into play.
The main idea is best conveyed via example, so let me give you two examples and then extract the ingredients of these examples. Bib, do you know what it means for two positive integers to be relatively prime?''
``I know what a prime number is, but I don't know what relatively prime means.''
``We say that two integers m and n are relatively prime if their only common positive divisor is 1. Thus, 12 and 35 are relatively prime because their only common divisor is 1, while 12 and 21 are not relatively prime because both are divisible by 3. Does this make sense?''
``Yeah, that's a simple concept.''
``Here is a question: How many integers between 1 and 1,000, inclusive, are relatively prime to 6? Note that a number is not relatively prime to 6 if it is divisible by 2 or 3. So let's remove the integers between 1 and 1,000 which are not relatively prime to 6. First, there are precisely 500 integers between 1 and 1,000 which are divisible by 2. Second, there are 333 integers between 1 and 1,000 which are divisible by 3. Let's remove them from the 1,000 integers giving us 1,000 - 500 - 333 = 167. Is this the correct answer, Bib?''
After thinking only a moment or two, Bib responded, ``No, any integer which is divisible by 6 has been removed twice.''
``Very good! So let's add them back in. There are 166 integers between 1 and 1,000 which are divisible by 6. This gives us the quantity 1,000 - 500 - 333 + 166. Let's see what that is counting. Any integer which is relatively prime to 6 is counted in the 1,000 term and nowhere else. Any integer which is divisible by 2 and not 3 is counted once in the 1,000 term and once in the -500 term thereby contributing zero. Any number which is divisible by 3 and not 2 is counted once in the 1,000 term and once in the -333 term thereby contributing zero. Finally, any integer divisible by both 2 and 3 is counted once in each of the four terms again contributing zero. So the correct answer is 1,000 - 500 - 333 + 166 = 333.
Now let's do the same for integers between 1 and 1,000, inclusive, which are relatively prime to 30. The prime divisors of 30 are 2, 3 and 5. The number of integers between 1 and 1,000 divisible by 2 is 500, divisible by 3 is 333 and divisible by 5 is 200. The number divisible by 6 is 166, divisible by 10 is 100 and divisible by 15 is 66. Finally, the number divisible by 30 is 33. What kind of addition and subtraction must we do to ensure that any number which is relatively prime to 30 contributes one and all other numbers contribute zero?
The first term is 1,000 so that every integer contributes one here. Any
integer between 1 and 1,000 which is divisible by exactly one of 2, 3 or
5 and no others needs to be subtracted precisely once so it is then making
no contribution. The expression
1,000 - 500 - 333 - 200 takes care of such
integers. However, any integer which is divisible by two or more of 2, 3
and 5 is being removed too many times so we have to put them back in.
Consider the expression
1,000 - 500 - 333 - 200 + 166 + 100 + 66. Any integer which
is divisible by exactly two of the primes 2, 3 and 5 is counted twice
with a - sign and twice with a + sign so it contributes zero. Finally,
any integer divisible by 30 is counted in each term so it currently is
contributing one to the expression. Thus, we remove such integers
giving the expression
Let's take a look at characteristics of the preceding examples. Both problems can be modelled by thinking of a collection of objects where each object is endowed with some properties from a list of possible properties. In our case the properties were `divisible by 2', `divisible by 3' and `divisible by 5' (only for the second example). Given a subset of properties -- for example, `divisible by both 2 and 5' -- it is easy to compute the number of objects having the subset of properties and possibly additional properties as well, but not easy to count the number of objects having exactly the subset of properties and no others. For example, we divide 1,000 by 10 to obtain 100 objects with the properties `divisible by 2 and 5' but some of them also are divisible by 3 while others are not. We want to count the number of objects having none of the properties (in our examples that makes them relatively prime to the respective number).
The Principle of Inclusion-Exclusion provides us with a tidy formula for
doing so. Let A(i) denote the number of objects having i or more
properties. We compute A(i) by taking each subset of i properties
and making the easy computation of the number of objects having that subset
of properties (and possibly more) and summing all these numbers. The
Principle of Inclusion-Exclusion then states that the number of objects
having none of the properties is given by
If you look back at the above examples, you will see this is exactly how the answers were determined. In the next issue we shall apply it to a card situation.