# CSE 321 Assignment #5Spring 2001

### Due: Friday, May 4, 2001 at the beginning of class.

Reading assignment: Read the text, Discrete Mathematics and Its Applications, sections 4.1-4.4 and begin reading section 4.5. The midterm exam is scheduled for Monday, May 7 in class.

The following problems are from the Fourth Edition of the text.

Problems:

1. Suppose that a function T is defined by T(1)=1 and for n greater than or equal to 1, T(n+1) is equal to T(n) if n+1 is not divisible by 4 and is equal to T((n+1)/4) + T((n+1)/2) + n if n+1 is divisible by 4. Prove that for all n greater than or equal to 1, T(n) is less than or equal to 4n.

2. Define a set S of strings by

• Basis: The empty string is in S.

• Constructor: If x and y are in S then 0x11x0 and xy are also in S.

• Nothing is in S other than the strings that can be derived by starting with the basis and applying the constructor.
Prove that every string in S has an equal number of 1's and 0's.

3. Section 4.1, Problems 20, 32.

4. Section 4.2, Problems 20, 28

5. 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 George W. Gore, 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 (George W. Gore was not banned from being dog-catcher at the time). How many outcomes were possible then?

6. Section 4.3 Problems 24 (c)(d), 26, 40
7. (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?

8. (Bonus) Section 4.3, Problem 62