Mathematics for Computer Science

15.13. A Magic Trick 489

by the Subset Rule. On the other hand, we have

jYjD 52 
 51 
 50 D132;600

by the Generalized Product Rule. Thus, by the Pigeonhole Principle, the Assistant
must reveal thesamesequence of three cards for at least

270;725
132;600



D 3

differentfour-card hands. This is bad news for the Magician: if he sees that se-
quence of three, then there are at least three possibilities for the fourth card which
he cannot distinguish. So there is no legitimate way for the Assistant to communi-
cate exactly what the fourth card is!

Problems for Section 15.2

Class Problems

Problem 15.1.
A license plate consists of either:

 3 letters followed by 3 digits (standard plate)

 5 letters (vanity plate)

 2 characters—letters or numbers (big shot plate)

LetLbe the set of all possible license plates.

(a)ExpressLin terms of

ADfA;B;C;:::;Zg

DDf0;1;2;:::;9g

using unions ([) and set products ().

(b)ComputejLj, the number of different license plates, using the sum and product
rules.

Problem 15.2. (a)How many of the billion numbers in the range from 1 to 109
contain the digit 1? (Hint:How many don’t?)