CS 70 Discrete Mathematics for CS

Fall 2004  Rao  HW 2

Due Thu, September 16 at 3:39PM (283 Soda or in-class)

1. (5 pts.) Any questions?

What’s the one thing you’d most like to see explained better in lecture or discussion sections? Are lectures too fast, too slow, or just right? Are discussion sections too fast, too slow, or just right? Any comments about what we could have done better in the past week would be appreciated.

2. (20 pts.) Hamiltonian sequences in tournaments A sequence of players in an all round-robin tournament forms a Hamiltonian sequence if for 1 ≤ i < n, the i-th player beats the (i + 1)-th player. Prove by induction that for any tournament of at least two players, there exists at least one Hamiltonian sequence. (Hint: To prove this by induction, you have to add the new player to the sequence. She can be at the beginning, the end of the sequence, or somewhere in the middle. If she is in the middle, you need to find some position i such that she beats the i-th player and gets beaten by the (i + 1)-th player.)

3. (20 pts.) A Quadratic Recurrence Given a rooted binary tree with n leaves. We define the cost of eachleaf is 0, and the cost at each internal node as the number of leaves in the left subtree times the number of leaves in the right subtree. Prove that the total cost is n(n − 1)/2.

4. (20 pts.) Mmm, mmm, good.

Chocolate often comes in rectangular bars marked off into smaller squares. It is easy to break a larger rectangle into two smaller rectangles along any of the horizontal or vertical lines between the squares. Suppose I have a bar containing k squares and wish to break it down into its individual squares. Prove that no matter which way I break it, it will take exactly k − 1 breaks to do this.

5. (15 pts.) Proofs to Grade Assign a grade of A (correct), C (partially correct) or F (failure) to the following proof. If you give a grade other than A, please explain exactly what is wrong with the structure or the reasoning in the proof. For a partially correct proof, you should correct it. You should justify all your answers (Remember, saying that the claim is false is not a justification).

(a) Claim: For every n ∈ N, n^{2} + n is even. Base Case: The natural number 0 is even. Inductive

Step: Suppose k ∈ N and k^{2}+ k is even. Then,

(k + 1)^{2}+ (k + 1) = k^{2}+ 2k + 1 + k + 1 = (k^{2}+ k) + (2k + 2)

is the sum of two even integers. Therefore, (k + 1)^{2} + (k + 1) is even. By the Principle of Mathematical Induction, the property that n^{2}+ n is even is true for all natural numbers n. ♠

boy preferences girl preferences
a 1>2>3>4  1 d>b>c>a
b 2>1>4>3  2 a>d>b>c
c 1>3>2>4  3 a>b>c>d
d 2>1>3>4  4 d>c>a>b

Figure 1: Preferences for the stable marriage problem. (1 > 2 means that 1 is preferred to 2.)

(b) Claim: Any amounts of postage no less than 3 cents can be formed from 3-cent stamps. Proof: (uses strong induction) Base case: The postage of cost 3 cents can be formed from a single 3-cent stamps. Inductive Step: Assume that any postage of cost i cents, for all i ≤ n, can be formed using 3-cent stamps. We need to show that the postage of cost n+1 cents can be formed. Since 3-cent stamps can form the (n−2)-cent postage, adding one more 3-cent stamp gives the (n+1)-cent postage. Therefore, by the Principle of Strong Induction, any amounts of postage no less than 3 cents can be formed using 3-cent stamps. ♡

6. (20 pts.) Stable marriage Consider a set of four boys (a, b, c, d) and four girls (1, 2, 3, 4) with the preferences shown in Figure 1.

(a) Run on this instance the traditional marriage algorithm. Show each stage of the algorithm, and give the resulting matching, expressed as a set of boy-girl pairs. You can do this by hand, or you can write a simple program to do it for you.

(b) The matching you found above is boy-optimal. Find now a girl-optimal stable matching. (It requires running a modified algorithm.) Compare the two matchings.

(c) We know that there can be no more than n^{2} stages of the algorithm, because at least one girl is deleted from at least one list at each stage. Can you construct an instance with n boys and n girls so that c · n^{2} stages are required for some respectably large constant c? (We are looking for a general pattern here, one that results in c · n^{2} stages for any n.)

(d) Let M,M′denote two stable matchings, and let M ⊔ M′denote the configuration where each girl is married to the better of her two partners in M and M′(according to that girl’s preference list). Suppose that M ⊔ M′is a matching. Is M ⊔ M′guaranteed to be stable if M and M′are? Prove your answer.