CSE 321: Discrete Structures
January 24, 2001
Due: Wednesday, January 31
Reading Assignment: Rosen, Sections 3.1 - 3.3
- Section 3.1, exercise 10.
- Section 3.1, exercise 24.
- Section 3.1, exercise 42.
- Section 3.1, exercise 50.
- Section 3.1, exercise 68.
- Section 3.2, exercise 6.
- Prove that any prime number bigger than 3 is congruent to 1 or 5
- 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.)