CSE 321 Assignment #5
Spring 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.


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

  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