Discrete Mathematics for Computer Science

40 CHAPTER 1 Sets, Proof Templates, and Induction

and

I D 2 n D 3 n D 5 1 = I D301 = 1,000,000

Now, by the Principle of Inclusion-Exclusion for Three Sets,

I D 2 U D 3 U D 5 I = I D21 + I I + I D - I D 2 n D 3 I - I D 2 n D 5 I

-I D 3 n D 5 1 + I D 2 n D 3 n D 5 I

= 22,000,000 U

Often, a problem is posed in terms of finding how many objects do not have one or

more of a set of properties. For example, suppose we were asked to find the number of

integers between 1 and 30,000,000 that are not divisible by any of the integers 2, 3, or 5.

The solution is I D 2 U D 3 U D 5 I where D 2 , D 3 , and D 5 are defined as in Example 8. The

answer is

I D 2 U D 3 U D 5 I= 30,000,000 - I D 2 U D 3 U D 5 I

In Example 8 we have shown that

I D 2 U D 3 U D 5 I = 22,000,000

so

ID 2 U D 3 U D 51 = 8,000,000

Next, we study an example that looks quite different from counting the number of

values having some set of properties.

Example 9. (The Hat Check Problem) Three Victorian gentlemen, called G 1 , G2,

and G 3 , arrive at a restaurant and check their top hats. The cloakroom attendant loses the

numbers on the three hats and doesn't know which hat is whose. Rather than admitting

the error, the attendant gives the three hats back to the three gentlemen at random. Let

hi represent the hat that belongs to gentleman Gi where 1 < i < 3. The notation hihjhk

represents hat hi being given to G 1 by the attendant, hj being given to G 2 by the attendant,

and hk being given to G 3 by the attendant.

How many random assignments of hats result in at least one gentleman receiving his

own hat?

Solution. There are six ways the three hats can be handed back. The first gentleman to

request his hat back may be given any of the three hats. The second gentleman may be

given either of the two remaining hats. The third gentleman must get the last hat. Multiply

3 x 2 x 1 = 6 to get the number of possible ways.

Of those six ways to hand back the hats, obviously only one gets each hat back to

its owner. How many ways get at least one hat back to its owner? This question can be

answered using the Principle of Inclusion-Exclusion.

Let U be the set of all six ways the attendant can give the three top hats back. Let Hi,

for 1 < i < 3, be the set of all the ways where Gi gets his own hat back. Now, I H 1 I = 2,

for if G 1 gets his own hat back, then there are two hats to return to G 2 and G 3 .These

two hats can be returned to these two gentlemen in two different ways. By symmetry,

InlI = InH 21 = I H 31 = 2. If G 1 and G 2 get their own hats returned, then there is one hat