Problem Set IX, for Friday, June 5

Mathematics 61

Permutations and Combinations:

• 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 DM6e or page 133 of 2008 copies of DS):

• 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:

• 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.