CS70-Homework 2 Solved

State which of the proofs below is correct or incorrect. For the incorrect ones, please explain clearly where the logical error in the proof lies. Simply saying that the claim or the induction hypothesis is false is not a valid explanation of what is wrong with the proof. You do not need to elaborate if you think the proof is correct.

(a)    Claim: For all positive numbers n ∈ R, n2 ≥ n.

Proof. The proof will be by induction on n.

Base Case: 12 ≥ 1. It is true for n = 1.

Inductive Hypothesis: Assume that n2 ≥ n.

Inductive Step: We must prove that (n+1)2 ≥ n+1. Starting from the left hand side,

(n+1)2 = n2 +2n+1 ≥ n+1.

       Therefore, the statement is true.                                                                              

(b)   Claim: For all negative integers n, (−1)+(−3)+···+(2n+1)= −n2.

Proof. The proof will be by induction on n.

Base Case: −1 = −(−1)2. It is true for n = −1.

Inductive Hypothesis: Assume that (−1)+(−3)+···+(2n+1)= −n2.

Inductive Step: We need to prove that the statement is also true for n−1 if it is true for n, that is, (−1)+(−3)+···+(2(n−1)+1)= −(n−1)2. Starting from the left hand side,

(−1)+(−3)+···+(2(n−1)+1)=((−1)+(−3)+···+(2n+1))+(2(n−1)+1)

= −n2 +(2(n−1)+1) (Inductive Hypothesis)

= −n2 +2n−1

= −(n2 −2n+1) = −(n−1)2.

       Therefore, the statement is true.                                                                              

(c) Claim: For all nonnegative integers n, 2n = 0.

Proof. We will prove by strong induction on n.

Base Case: 2×0 = 0. It is true for n = 0.

Inductive Hypothesis: Assume that 2k = 0 for all 0 ≤ k ≤ n.

Inductive Step: We must show that 2(n+1)= 0. Write n+1 = a+b where 0 < a,b ≤ n. From the inductive hypothesis, we know 2a = 0 and 2b = 0, therefore,

2(n+1)= 2(a+b)= 2a+2b = 0+0 = 0.

       The statement is true.                                                                                               

2        A Coin Game
Your "friend" Stanley Ford suggests you play the following game with him. You each start with a single stack of n coins. On each of your turns, you select one of your stacks of coins (that has at least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into a stack of 3 coins and a stack of 2 coins, your score would be 3·2 = 6). You continue taking turns until all your stacks have only one coin in them. Stan then plays the same game with his stack of n coins, and whoever ends up with the largest total score over all their turns wins.

Prove that no matter how you choose to split the stacks, your total score will always be n  .

(This means that you and Stan will end up with the same score no matter what happens, so the game is rather pointless.)

3        Grid Induction
Pacman is walking on an infinite 2D grid. He starts at some location (i, j)∈N2 in the first quadrant, and is constrained to stay in the first quadrant (say, by walls along the x and y axes). Every second he does one of the following (if possible):

(i)      Walk one step down, to (i, j−1).

(ii)    Walk one step left, to (i−1, j).

For example, if he is at (5,0), his only option is to walk left to (4,0); if Pacman is instead at (3,2), he could walk either to (2,2) or (3,1).

Prove by induction that no matter how he walks, he will always reach (0,0) in finite time. (Hint: Try starting Pacman at a few small points like (2,1) and looking all the different paths he could take to reach (0,0). Do you notice a pattern?)

4        Stable Marriage
Consider a set of four men and four women with the following preferences:

men
preferences
women
preferences
A
1234
1
DABC
 
1324
 2
BC
 
1324
3
BC
D
3124
4
ABDC
(a)    Run on this instance the stable matching algorithm presented in class. Show each day of the algorithm, and give the resulting matching, expressed as {(M,W),...}.

(b)   Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might propose and get rejected several times in a single day). Prove that this modification will not change what pairing the algorithm outputs.

5        Optimal Partners
In the notes, we proved that the Stable Marriage Algorithm always outputs the male-optimal pairing. However, we never explicitly showed why it is guaranteed that putting every man with his best choice results in a pairing at all. Prove by contradiction that no two men can have the same optimal partner. (Note: your proof should not rely on the fact that the Stable Marriage Algorithm outputs the male-optimal pairing.)

6        Examples or It’s Impossible
Determine if each of the situations below is possible with the traditional propose-and-reject algorithm. If so, give an example with at least 3 men and 3 women. Otherwise, give a brief proof as to why it’s impossible.

(a)   Every man gets his first choice.

(b)   Every woman gets her first choice, even though her first choice does not prefer her the most. (c) Every woman gets her last choice.

(d)   Every man gets his last choice.

(e)    A man who is second on every woman’s list gets his last choice.