Problem Set VIII, for Friday, December 7

Mathematics 61

Basic Principles (for Counting) (page 114 in Discrete Source or page 227 in Discrete Mathematics):

• Exercise 58.   Suggestion: How many arrangements are there in which the art books are together?   Compare Exercise 57, which has an answer in the book.
• Exercise 59.
• Exercise 67.   As the book says, Exercise 65 gives the general rule being applied here.   The problem asks for strings that start with 1 or end with 1 or both.

Permutations and Combinations (page 124 in Discrete Source or page 237 in Discrete Mathematics):

• Exercise 11.
• Exercise 35.
• Exercise 62.   Clarification: The problem asks how many outcomes have at least as many heads as tails.

Generalized Permutations and Combinations (online or page 265 in Discrete Mathematics):

• Exercise 23.   Note that Exercise 22 has an answer in the book.
• Exercise 33.   The three teams are to play simultaneously; therefore they must be non-overlapping.   Moreover, each of the three teams plays a different sport.
• Exercise 42.

The Pigeonhole Principle (page 135 in Discrete Source or page 273 in Discrete Mathematics):

• Exercise 2.   Can eighteen be replaced by a smaller number and still have the conclusion hold?
• Exercise 3.   Clarification: The statement is that every year contains some lucky month (but different years might have different lucky months).   Can we conclude that every year contains two such months?
• Show that in a simple graph with at least two vertices, there must be two vertices with the same degree.   (This is often stated in non-graph terms: At a certain social event, some people shake hands and some don't; show that there must be two people who make exactly the same number of handshakes.)

Click here for answers in .pdf format.