`|= |#1|#1 `@= @#1@#1

Discrete Structures Anna Karlin, 426C Sieg
CSE 321, Spring 1998

Homework #6
Due at the beginning of class, Wednesday, May 20

Reading: Rosen, Sections 4.4 - 4.5, 5.1

Continued Experimental Policy: You are strongly encouraged to work in groups of 2 on this homework and turn in a single homework with both names on it. Both members of the group will receive the same score.

Come visit: If you are having trouble with any of the problems or are not sure of the correctness of your solutions, please come visit Anna or one of the TA's in office hours. We're really, truly happy to help you out.

1. How many functions are there from the integers in the range [1,..,k] to the boolean values ?
2. How many ways can 3 exams be scheduled on a 5-day period such that no two exams are held the same day?
3. How many ways are there to seat 5 children in a row of 12 chairs?
4. How many ways can three distinct numbers be chosen from the set such that their sum is even?
5. How many ways are there of seating n people around a circular table? (Two seatings are considered the same if one is simply a circular shift of the other.)
6. Rosen, Section 4.2, problem 4.
7. How many ways are there to arrange the letters in the word MISSISSIPPI?
8. A palindrome is a word that reads the same forwards and backwards (e.g., ``Anna''). How many six-letter palindromes can be made from the English alphabet?
9. How many 5 card hands (from a 52 card deck) have the same number of Spades and Hearts?
10. What is the coefficient of in ?
11. What is the coefficient of in ?
12. Extra Credit, but you must do this SOLO: If you did not get a perfect score on these problems on the midterm, feel free to redo them for extra credit. Please turn just these in on a separate page from the rest of your homework with your name on it.
    • Prove by contradiction: If x is a rational number different from 0 and y is an irrational number, then is irrational. (You may use the following fact: if a and b are nonzero rational numbers, then a/b is also rational.)
    • Prove by induction that

      

      whenever n is a positive integer.

13. Extra Credit: Imagine a town with East-West streets numbered 1 through n, and North-South avenues numbered 1 through m. A taxi cab picks up a passenger at the corner of 1st street and 1st avenue. The passenger wishes to be delivered to n-th street and m-th avenue. It is quite clear that the passenger will be angry if the cab chooses a route longer than (n-1)+(m-1) blocks, so we won't allow the cabby to take a route longer than this. In other words, the cabby must always be increasing his street number or his avenue number. Suppose that there is an accident at i-th street and j-th avenue. How many routes can the cabby take that avoid the intersection with the accident?
14. Extra Credit: 23 people come to a dinner party. They are to be seated at a circular table. Suppose that there is a nametag at each place at the table and suppose that nobody sits down in their correct place. Show that it is possible to rotate the table so that at least two people are sitting in the correct place. (Hint: the pigeonhole principle.)

• About this document ...