CSE 321: Discrete Structures
Assignment #4
January 24, 2001
Due: Wednesday, January 31

Reading Assignment: Rosen, Sections 3.1 - 3.3

Problems:

1.

Section 3.1, exercise 10.

2.

Section 3.1, exercise 24.

3.

Section 3.1, exercise 42.

4.

Section 3.1, exercise 50.

5.

Section 3.1, exercise 68.

6.

Section 3.2, exercise 6.

7.

Prove that any prime number bigger than 3 is congruent to 1 or 5 modulo 6.

8.

John and Sara have a party to which they invite n other married couples. As is normal at parties, handshaking took place. Of course, none shook their own hand or their spouse's hand (and not everyone shook everyone else's hand). After all the handshaking was over, John asked all the other people present including his wife Sara ``how many different people's hands did you shake this evening?'' Interestingly, they each gave a different answer. From the information given, deduce how many different people's hands Sara shook that evening. Prove your answer by induction on n. (Hint: try working through the solution for several small values of n before going to the general case.)