Homework assignment 07
Homework assignments
Homework assignment 10
Document also available in PDF, Postscript, DVI, pure text and LaTeX.
3.2. Counting
Exercise 1 [13 p. 194]
A binary logical connective can be defined by giving its truth
table. How many different binary logical connectives are there?
Proof: [Correction]
We simply have to count the number of truth tables with two symbols.
In such a table, there are 4 cells, and for each of those, there
are two independant choices: true or false. Hence, we have 24=16
possible logical connectives.
Exercise 2 [22 p. 195]
A customer at a fast-food restaurant can order a hamburger with or
without mustard, ketchup, pickle, or onion; a fish sandwich with or
without lettuce, tomato, or tartar sauce; and a choice of three
kinds of soft drinks or two kinds of milk shakes. How many
different orders are possible if a customer can order at most one
hamburger, one fish sandwich, and one beverage but can order less?
Proof: [Correction]
We could use the addition principle to take into account all the
possible cases (hamburger or not, fish sandwich or not, ...).
Another way to deal with this is to consider the option "no
hamburger" as just one extra possible choice for the hamburger. I.e.
to add one to the total number of hamburgers, and likewise for fish
sandwiches and beverages.
Since there are four possible toppings on the hamburger, we have
24=16 possible hamburgers. Likewise, we have 23=8 possible
fish sandwiches.
Conclusion: the choices for hamburger, fish sandwich and beverage
are independant, and thus by the multiplication principle we have
(16+1)(8+1)(5+1)=17=918 possible orders (917 if we
assume that the customer has to order at least one thing).
Exercise 3 [38 p. 196]
How many binary strings of length 8 are palindromes?
Proof: [Correction]
By definition of a palindrome, the 4 last digits in such a string
are mirrors of the first 4 digits. For each of those first 4
digits we have two choices. Thus, there are 24=16 binary strings
of length 8 which are palindroms.
3.3. Principle of Inclusion and Exclusion; Pigeonhole Principle
Exercise 4 [9 p. 204]
At the beginning of this chapter you surveyed the subscribers to
your newsletter in preparation for the release of your new software
product.
The results of your survey reveal that of the 87 subscribers, 68
have a Windows-based system available to them, 34 have a Unix
system available, and 30 have access to a Mac. In addition, 19
have access to both Windows and Unix systems, 11 have access to
both Unix systems and Macs, and 23 can use both Macs and Windows.
Use the Principle of Inclusion and Exclusion to determine how many
subscribers have access to all three types of systems.
Proof: [Correction]
We can think of the number of subscribers having access to all three
systems as the size of the intersection of sets W, U, and M or
|Wintersect U intersect M|. We also know that the total number of
subscribers surveyed is 87: |Wunion U union M|=87. By the
principe of inclusion and inclusion, we have:
|Wunion U union M|=|W|+|U|+|M|-|Wintersect U|-|Uintersect M|-|Wintersect M|+|Wintersect
U intersect M|,
which yields
| |Wintersect U intersect M| |
= |Wunion U union M|-|W|-|U|-|M|+|Wintersect U|+|Uintersect M|+|Wintersect M| |
| |
= 87-68-34-30+19+11+23=8 |
Exercise 5 [18 p. 205]
In a group of 25 people, must there be at least 3 who were born in
the same month?
Proof: [Correction]
Yes! We will prove this by contradiction, following closely the
proof of the usual pigeonhole principle. Assume that no more than
2 people were born in any given month. Since there are only
twelve months, we cannot have more than 12*2=24 persons in the
group, which is obviously impossible.
Homework assignment 07
Homework assignments
Homework assignment 10
Homework assignment 08 /
CSM MACS-358 /
Nicolas M. Thi閞y
Last modified: Tue Dec 2 13:40:29 2003