CSE 321 Assignment #5
Autumn 1997

Due: Friday, November 14, 1997.

Reading assignment: Read the text, Discrete Mathematics and Its Applications, Sections 4.1 to 4.5. The following problems are from the Third Edition of the text.

Problems:

1. Section 4.1, page 242, problem 36. (Allow both possibilities at once.)

2. Section 4.1, page 242, problem 42. (A restriction to 8 character variable names is one reason why the names of all those Unix commands are so obscure.)

3. Section 4.2, page 249, Problem 28.

4. Section 4.3, page 258, Problem 16.

5. Section 4.3, page 259, Problem 22.

6. Section 4.3, page 259, Problem 32.

7. In the town of Palukaville there are three elected positions: mayor, sheriff, and dog-catcher, to be chosen from among the 70 people in town. Each person can be elected to at most one of these positions.
   • How many ways are there of filling all three of these positions? That is, how many different election outcomes are possible (assuming no ties)?
   • After a recent scandal involving a terrier, it was decided that H. Bob Clinton, one of the townspeople in Palukaville, was no longer eligible to be chosen as dog-catcher. In how many ways can the three positions be chosen now?
   • During last year's election there were only 65 people in town and someone forgot to prohibit the same person from being elected to more than one position (H. Bob Clinton was not banned from being dog-catcher at the time). How many outcomes were possible then?

8. (Bonus) Section 4.1, page 243, problem 48.

9. (Bonus) The Smithson invitational tennis tournament is a round-robin tournament (each player plays every other player once) in which each player plays at most one match per day. Suppose that there are 2n+1 players in the tournament. How many games are played in total? What is the minimum number of days needed to run the tournament? Justify your answer. What are the corresponding answers if there only 2n players?