3 Strong Induction Use strong induction to show that for all natural numbers 11 there exist natural numbers x, y, and z such that 6" = x2 + y2 + zz. 4 Long Courtship (a) Run the traditional (i.e., male optimal) propose-andreject algorithm on the following example: Man Preference List Woman Preference List A>B>C>D 2>3>4>1 1 2 B>C>A>D B 3>4>1>2 3 C>A>B>D C 4>1>2>3 4 A>B>C>D \" 1>2>3>4 State what happens on every day in a table. (b) We know from the notes on the stable marriage algorithm (Lemma 4.1) that the proposeand reject algorithm must terminate after at most 112 days. This is in fact the maximum number of proposals before the algorithm halts since each man has 11 women in his list to propose and there are n men who have such a list. Knowing this, prove a sharper bound showing that the algorithm must terminate after at most n(n 1) + 1 proposals. (0) Is the instance in part (a) a worst-case instance for n=4, in the sense that it requires the maxi- mum possible number of proposals? 1 The Stable Marriage Problem In the previous two notes, we discussed several proof techniques. In this note, we apply some of these techniques to analyze the solution to an important problem known as the Stable Marriage Problem, which we now introduce. The Stable Marriage Problem is one of the highlights of the field of algorithms. Suppose you run a dating agency, and your task is to match up n men and n women. Each man has an ordered preference list of the n women, and each woman has a similar list of the n men. For example, consider the case of n = 3, i.e., three men Alex, Bob, and Charles, and three women Anita, Bridget, and Christine, with the following preference lists (lists are ordered from most favorable to least favorable): Men Women Women Men Alex Anita Bridget Christine Anita Bob Alex Charles Bob Bridget Anita Christine Bridget Alex Bob Charles Charles Anita Bridget Christine Christine Alex Bob Charles What you would like to do as head of the dating agency is to pair up each man with a woman. For example, two possible pairings are { (Alex, Anita), (Bob, Bridget), (Charles, Christine) } and { (Alex, Bridget), (Bob, Christine), (Charles, Anita) }. However, you don't want just any old pairing! In order for your dating firm to be successful, you wish the pairing to make "everyone happy", in that nobody can realistically hope to benefit by switching partners. Can you do this efficiently? It turns out that there is indeed an algorithm to achieve this; moreover, it's remarkably simple, fast, and widely-used. It's called the Stable Marriage algorithm (a.k.a. the Gale-Shapley algorithm), and we present it now