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.
Problems:
- 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.
- 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.
- Section 4.1, Problems 20, 32.
- Section 4.2, Problems 20, 28
-
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?
- Section 4.3 Problems 24 (c)(d), 26, 40
(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?
- (Bonus) Section 4.3, Problem 62