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

Homework #4
Due at the beginning of class, Wednesday, April 29

Reading: Rosen, Sections 3.3, 4.1 - 4.2

Problems:

1. Rosen, Section 3.2, problem 12
2. Rosen, Section 3.2, problem 20
3. Rosen, Section 3.2, problem 32
4. A binary tree is either empty, or consists of a root node and a ``left subtree'' and ``right subtree'', which are themselves binary trees. (See Figure 8 in Section 8.1, page 537, for an example.) Any node in a binary tree both of whose subtrees are empty is called a leaf. For example, the tree in Figure 8(a) of Section 8.1 has 6 leaves: f, g, e, j, k, m. The height of a binary tree is the distance from the root to the farthest leaf. The tree in Figure 8(a) of Section 8.1 has height 4, m being the farthest leaf from the root. (Note that the distance from the root to m is considered to be 4 rather than 5.) By induction, prove that for any positive integer n, any binary tree with n leaves has height at least . Be careful of the case when the root has one empty subtree.
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, no one shook their own hand or the hand of their spouse (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 all gave a different answer. From the given information, determine 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.)
6. Consider the following variant of the stable pairing problem, which we'll call the "general stable pairing problem" (this is the bisexual version): We are given 2n people, each with a complete ranking of the remaining 2n-1 people (no ties). A "pairing" of the 2n people is a partition of the 2n people into n couples. A pairing is "unstable" if there are two people (not a couple) that both prefer each other to the people with whom they are coupled. A pairing is "stable" if it it not unstable. (See page 4 of the notes I handed out for an example of the preference lists.) Prove or disprove: for any set of preference lists given as input to the general stable pairing problem, there is at least one stable pairing.

• About this document ...