U.C. Berkeley – CS70: Discrete Mathematics and Probability Problem Set 4Lecturers: Umesh Vazirani & Christos H. Papadimitriou Due September 22, 2006 at 4:00pmProblem Set 41. Fibonacci Fun: Prove the nth Fibonacci number is equal toφn−(1−φ)n√5, where φ =1+√52is theGolden Ratio, and satisfies the identity φ2= φ + 1. Be sure to state what style of proof you are using.2. Hard examples for sta ble mar riage algorithm.In the last homework, you ran the traditional propose and reject a lgorithm on the following instance:Men’s pr e ference list:1 A B C D2 B C A D3 C A B D4 A B C DWomen’s preference list:A 2 3 4 1B 3 4 1 2C 4 1 2 3D 1 2 3 4(a) In class we showed that the propose and reject algo rithm must terminate after at mos t n2propos-als. Prove a sharper bound showing that the algorithm must terminate after at most n(n − 1) + 1proposals. Conclude that the above example is a worst case instance for n = 4. How many daysdoes the algorithm take on this instance?(b) Extra credit: generalize the above example to arbitraty n and prove rigorously that the algorithmmakes n(n − 1) + 1 proposals on your example. How many days doe s the a lgorithm ta ke?3. Man-optimal, Woman-optimal In an par ticula r instance of the stable marriage problem with nmen and n women, it turns out that there are exactly three distinct stable matchings, M1, M2, M3.Also, each woman W has a different partner in the three matchings. Therefore each woman ha s a clearpreference ordering of the three matchings (according to the ranking of her partners in her preferencelist). Now, suppose for woman W1, this order is M1> M2> M3. True or false: every woman hasthe same preference o rdering M1> M2> M3. Justify your answer.4. Stable Grouping.(a) In a particula r class, there are n students attending from each of 3 different majors (3n totalstudents). The students ar e asked to split into groups of 3 such that one person from each major isin each group. Each student has a ranking of pre ference for the students from the other 2 majors. Astudent, s ay Anita, as signed to a group, X, will naturally prefer a different group, Y, if Anita ranks theother two members of Y higher than the other two members of X not in her major. The grouping willbe unstable if also Y’s member in Anita’s major, say Rishi, rank s the o ther two member s of X higherthan he ranks his two cur rent compatriots. Prove that there always exis ts a stable grouping of all ofthe students.Hint: try to solve this by applying what you know from the stable marria ge problem. Is there somethinguseful you can say by restricting your attention to only two of the majors. Now can you include thethird major?1(b) What if ther e are m different majors (mn total students)? Using induction, prove that there alwaysexists a stable grouping o f all of the students.(c) For (b), how long would the professor have to wait for the students to asso rt into groups? In otherwords, how many propose / rejects would it take to achieve a stable grouping?5. Modular Equations Solve the following equations for x and y or show that no solution exists. Showyour work (in particular, what division must you carry out to solve each case).(a) 5x + 23 ≡ 6 (mod 499)(b) 9x + 80 ≡ 2 (mod 81)(c) The system of simultaneous equations30x + 3y ≡ 0 (mod 37) and y ≡ 4 + 13x (mod 37)6. Modular Sum of Squares Prove that if n = 3 mod 4, then n ca nnot be the sum of the squares of2 integers.7. Goldbach’s Infinitude of Primes.The Fermat numbers ar e generally described as: Fn= 22n+ 1 . In the 1700’s, Goldbach realize d thatFermat number s held a fasc inating se c ret.(a) P rove that Fn= F0× F1× · · · × Fn−1+ 2.(b) Use (a) to s how that any two Fermat numbers must be r e latively prime with one another.(c) Use (b) to argue that there must be an infinitely many number of
View Full Document
Unlocking...