MATH 211 Exam 2 with Solution, Fall 2007

Math 211 — Fall 2007-08 Discrete Structures Quiz 2, November 29 — Duration: 1 hour 15 minutes GRADES (each problem is worth 12 points): 1 2 3 4 [5 6 TOTAL/72 YOUR NAME: Questions and Sh OAS YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation W 4 Recitation W 11 Recitation Th 12:30 Recitation Th 3:30 Professor Makdisi Ms. Karam Ms. Karam Ms. Karam INSTRUCTIONS: 1. 2 NEW! 5. Write your NAME and AUB ID number, and circle your SECTION above. Solve the problems inside the booklet. Explain your reasoning precisely and clearly to ensure full credit. Partial solutions will receive partial credit. Each problem is worth 12 points. You may use the back of each page for scratchwork OR for solutions. There are two extra blank sheets at the end, for extra scratchwork or solutions. If you need to continue a solution on another page, INDICATE CLEARLY WHERE THE GRADER SHOULD CONTINUE READING. Open book and notes. CALCULATORS ARE ALLOWED. Turn OFF and put away any cell phones. You do not need to simplify your answers to counting problems — for example, if the answer is (%)) + (12!)7-6-5, just leave it that way. GOOD LUCK! An overview of the exam problems. Each problem is worth 12 points. Each part of a problem is weighted equally, EXCEPT FOR problems 3 and 4. ‘Take a minute to look at all the questions, BEFORE you start solving. 1 Let X= {nen | (7 <n 77) A (nis a multiple of 3)}. a) Find the cardinality N = |X| of the set X. b) Give a bijection f : {1,2,...,.N} + X. You do not have to prove that f is a bijection. 2. There are 12 passengers on the AUB shuttle bus. Each passenger gets off at one of § stops: A, #, J, M,O (meaning Agriculture, Engineering, Jafet, Marquand, Oval). a) Show that there exists a stop where at least 3 passengers get off. b) How many ways are there for the passengers to get off the bus if the passengers are indistinguishable? c) Same question as (b) except that the passengers are distinguishable? d) Same question as (b) except that the passengers are distinguishable, and 3 pas- sengers get off at each of A, E, J, while 1 passenger gets off at M, and 2 get off at O? 3. a) (8 pts) Show by mathematical induction that Yn € N, (7*) <4, b) (4 pts) Give a different proof of the above by expanding (1 + 1)?" Remark: one can prove by induction the stronger statement that (” Do that at home, after the test. 4, a) (3 pts) Fill in the blanks on page 4 for a function oddprod(n) that computes the product of the odd positive integers i < n. For example, oddprod;, 3 =1-3-5-7-9 and oddprod(11) =1-3-5-7-9-11. v b) (3 pts) We are given a list of lists 1, and we wish to make a new list 12 consisting of the sublists of 1 whose elements are all odd. For example: If 1 ([1,3,8], [4,6,6], (9,11,17], (3,1,1,7], [2]] then 12 = [[1,3,5], [9,11,17}, (3,1,1,71]. Use the Filtered() and ForA11() functions in GAP to do this in one line (see page 4). Reminder: Filtered([1..10], x->Is0dd(x)) = [1,3,5,7,9] ForAll([1..10], x->Is0dd(x)) = false. c) (6 pts) Write a function totallyoddsublists() that solves part b) using nested loops. So you can write 12 := totallyoddsublists(1) to achieve the same result as in part (b). Do not use Filtered(), ForAl1(), or even ForAny() in this part. Hint: the outer loop goes over elements of 1, which are sublists. The inner loop goes through the elements of a sublist and uses a helping variable allodd € {true, false} to keep track of whether the elements that we have examined so far in this sublist are all odd. 5. A problem about the number of permutations P(n, 1). a) Give an algebraic proof that P(n,r) = P(n—1,r) +rP(n—1,r—-1). b) Give a combinatorial proof of the above identity. 6. Consider the function f : {a,0,c} — {1,2,3,4,5,6,7} that is defined by f(a) = 5, f(b) =6, fe) = a) How ay left inverses 9 does f have? [Recall that a left inverse g is a function 9: {1,2,3,4,5,6,7} — {a,b,c} such that go f = idjap.<}-] b) How many left inverses g satisfy [g(1) = a or 9(2) = b or 9(3) = c]? i ii Beart ae Cnet cd read we wee ee is Tate paste. (3)-(2)G5) -C)-)» prere ae om a a ww ~ Cr=(de)..alv “few ssi Ve{Qu eed) V e=|GEND,d IODA] 1 ae wa foot cing ae mes me eget op Lo wey es wy 7 < Su NahU “Satu ety “fonate Lad fs on I TET eed qian ny oe tee oon Poy apes spt nese tu hayed r waged oy iy 8 ™ 20 ¥® Yo 33 z pur ‘wy ve Ho 5709 JoBuassed | arm ‘fq ‘y Jo YR Fe Yo 303 seFuaS -sed ¢ pue ‘aquysmaunsip ae srSuassed |y3 38q) ydooxa (q) se uoNsanb auteg (p ‘Yorwtetsyyen Pde dy sg Sr a ce my X wdonted a . eng, oS shoal a re YO us] = SSG So we ped my & SRN Pee re IL AES Gp Rip 8 thy Gerd sue uy JaqeysNBaysip axe sioSuossed ayy FEI] do0x9 (q) sv uOKSENb oureg (2 CGD 4 be per Gk ( ‘see Ayrton wy pr ny “Gare ) ge Gxrereagh are sp aim tm ss gy ete gt pw PEK K my ay 3 ” i “< on nnn How ew » Ns a Wein wow « wo Ky uw Qype amon § Oe. on we oom ow oe Kaw eanod Pen ain wow wm Ky TA oy Oe WP a pe me tale’ poe mm a4 . daqeysmaay spur are sinfuassed ay 31 snq aq3 Yo 128 07 sioBuaTed ay} LOY a1911) are sXem ABUT MOT (q sabeayed ‘owes, <_frar Weg sapey Se sey ap oem oe oe amy TT . 8 eS it ELE] ees ee ee SPO Byte g Heme ssNoned 2 Mey aie we taped aparently "Bo ye siniuosed ¢ ysua] ye aroqn doys v systx9 ax] IYI MoYg (e “(0eag ‘puvnbreyy ‘yayep ‘SupoomBag ‘emynouay Bupresw) Oy ‘fg ‘y ‘sdow 9 J0 ouo 78 Yo meH reBuaEsEd YOR “eng aIINYs ANY 9y3 uo sixBWessEd ZI aE ary, -z 1 Negus Gy Se aes paw my “ater my wage onl are ay 4g meyplig, aged ns ww sont Fy ft Oa] cme ae ete Tee gs amy Lane aes ont ay “patter erey ale ey my mea yg Gy oe cata <cnhy mom wey ey “SEG ay NE UGE Nea oer Ypres Rep fons dex po Ferre eR y+ Gomme my ere wT Pam eS Ks gales ageu + Trebmwe sul 4A haley gy spedsewen zal amy SSC HES eh ut pally op pe Gre 20g ee aed aaa “SS si'ue 2X tore K— fro vy, Lp eapallq © ane any -woryoofiq, By f qeyy saord 04 any you op nox “ye {Ate 'Z I}: f woreliq ¥ ants (q ig % ew f Sree pens me ae pe ase G pep yep ee wag re men Sse /e3 TQozsaee | Nea oh bp PPE KR MMP vegpallg ode ps amy peed Hay ang ayn] : arte a rue Lywyaeed Covad ARAL ge weyers Uwe og “peedinvin 3 me 6 W4E-S% AY ayseed por ‘mam stl] sas [Ses Sewer ee ee NT pe B48 “Geopelg 2 . Quand Py Nea PLUS ES Lowe Agee “yy HE ge oye XT HIND SSL a U'by eX “X 498 0419 J0 |x] = N Areurpreo omy pury (@ “{(e so ard wu) v2 5S 4) | Nau} = xT +1 ‘ab oe oy wenang 3. a) (8 pts) Show by mathematical induction that Yn € N, (7) <n Le PED be the shhenat (72) 649. * Base a S a . .. oe huh PCS). (+ Gar ie taheed STAT wR) aden | Tadedon ee ae wa. Va C P+ teeg) . (Tat nm ben arbtemy cleme EAL, SA Serine tb (\ 549 hy Coe = an) = (dl . : owt 9 Grote = Raed O00 Gl SOD fare) Cdl PQ nt Cond at, Qendtanny Al set) Qn bow eek moreno * ne n) Sore Magmic tak Qe, oe eh Cm) s wes 4G. geet Meco Mark Ong 4 Lt mee * St The she has ae gg, CRG Pow). Mensa by the bate ace D tndeddy step, we Greacbh dit = Ya Bh) Ny Tmathcoubeat tabvebien, b) (4 pts) Give a different proof of the above by expanding (1 + 1)?". © Gee GYM OVE ae Gr aye Bt e 2) r() ee - Bae. *G). Ba Metin () wa ze h “GE Rye (De ee he Remark: one can prove by induction the stronger statement that (") < 4"/Y2n +1. ox a422 that at home, after the test. 5 Shep: She Mat ned a gh. ile Ame staan Soap a1 *he Sete 5 HD Rsimpt # gt Whe eel Shen ET t a aa * Vim + ere dh Saaartt (ansitamry & Qemnt. 4. a) (3 pts) Fill in the blanks below for a function oddprod(n) that computes the product of the odd positive integers 1 <n. For example, oddprod(’) = 1-3-5-7-9 and oddprod(11) =1-3-5-7-9- 11. * eddprod := function(n) local ansver, 4; QASwes \; H Stert Be probed wits NO Lehre di Yor din Tim) do mati (pee if OMG Se Negyse iS, then oasuer is anger Wty so eanghy probeak™ a D} th; * od; return(ansver) end; Neel We om alin Sut i A by FGad te. NaAT cee ToddGy be ethical 1 Gap rab h TO Lt/i), ) (3 pts) We are given a list of lists 1, and we wish to make a new list 12 consisting of the sublists of 1 whose elements are all odd. For example: If 1 = (01,3,5), (4,5,6), (9,411,171, (3,1,1,7], (21) then 12 = [[1,3,5], (9,11,17], (3,4,1,73]. Use the Filtered() and ForA11() functions in GAP to do this in one line below. Reminder: Filtered([1..10), x->IsOdd(x)) = [1,3,5,7,9) ForAll([1..10}, x->Is0dd(x)) = fal see Nee tahoe, Answer ft . Tr eFitvered (9, 2-7 FecAW(e, 9-7 150 G))) : Nokes we om thie Cote Sitter) 2, KO Feral Go, Teedd Dy. c) (6 pts) Write a function totallyoddsublists() that solves part b) using nested loops. So you can write 12 := totallyoddsublists(1) to achieve the same result as in part (b). Do not use Filtered(), ForAl1(), or even ForAny() in this part. Hint: the outer loop goes over elements of 1, which are sublists. The inner loop goes through the elements of a sublist and uses a helping variable allodd € {trus, false} to keep track of whether the elements that we have examined so far in this sublist are all odd. Answer (will take several lines): Nem is pe “ty Then oe Seent ohea, totallyoddsublists := function(1) Week ersmar, satae, aitell, ah; Sse is £5 fre aettut in @ do Meld sz foe; mreemoers tsk all elles contig ch ee far elt in shu do WE nk TOS] (ell) hen athe! 2= Mee. 0, fe AtTeRNAT a,b eB (AD ther atoll o Ble; &, # ll all ad Qld ol, Utell tha, AUN (secur, sti), Coben, Concer) 5 aetaaTk gems “pang oy mene ‘rua tal phe ER gay Bet Ramah MB” OF CI VGE AON Cr GD dH TAL Mp my lpg ey wee Pray. \rvpe ne Cele an OS | — 4 mee Seem ss ates hy baer BT op my tinny yay ate Seton RA Pe ; “(usey Le he Peyt ees = t Uy] + me [Op ee ete evitivd = [Wavery SN =F 4 “rl wemp oy 42% moe Le (my] . », . sty EE PML aes : 28% | © Pan ae ans wh 2 4 : Wrae OSCR yh wep mo am ag lasts man se Py). tJ ETD te Come tab Corben’ wep) cz = pa Geer “Woy'e39 a6 eat ‘Wb egh mpl EON ty at rena hye gm oe og etch we ah ng oemmeg oe ety] = Foss -s “\eyatyaty) yan omy Be@w Lv ee be ty fareut a rr oo) Yerb Taber yp Cream am bery mye * Muapteseme tb = (£)6 30 9 = (2)6 40 v = (1)6} Ayeryes 6 sosxanur yot Anau Moxy (q mo Ely aye. meyer. LS bey We oy S79 Cay : Ss Yrates tot i “oe Batre Gl mE: Te Riles 7 Yaspat mh oy rah Frm L yt098 wT sem “Gormey aK ye “4 Ae @)AC cen on (EE = F068 yey yons {9'9'0} — {2'9°S EZ 1} 6 woroUTy v s| 6 esreany y>| e 4eq7 [JE>9Y] ZeAeY f Soop 6 soeIAAUT Yo] AowUE MOH (T L=@)f '9= @sF 9 ‘¢ = (2)f 4q pougep st yeyy {2'9's'y't'Z‘T} — {9'¢'D} : f wopouny ayy reprsucc SITES PES a Oh TY shew nea va tral ep A ew Se a ae Pn Y we Ces ewd 1s ME age Tam Oe TY eeay wewses ™h Ts eat Toy yy wr [er9) (ret Badge aoe sep 7D TS ‘then wrevrd onl Byes OE 1 s fro men calm GN map og MO AL te PP ny ye a ope sy Rll ~ (ketone FH poe von FHS) PL sem dna OO a = sow! oso 04) “te ba wh cay yy ONS oe smapeyenadey we ae other Gatyaesr Ged plans @s ome Wary === ‘then Grek 3 Me 34 wo Gem oe an . the Cg . ie Se ap BS Ey fem MYO mv oye 6) Remar mp stems ae “Pad Te snd —_ (Cet aly > SPM ee FE ty om gee on at wale tomes woos) Neto cae tie, Sprang we to my weg Gay” othe Cig a ey eM pe TeSOny = sey per gy penton eo te) om GRD . A OF (em cae yw erp aR ety oe j WI oN women FR ep aly me A UNE “eam Paap any on tog len peep vv: oaPay my ane om Reimer ‘Sure any ey RO yen Cee toby parqeew my es CE “Aygqmapt aaoqe ays jo Jooad feproyeurqutoo w aay) (q Msn 4 enw ‘Ve, Yew yg EPL GQ - eo te. Yew ae, wd ios * Gajed = ar ek EP Gd | jGro- rw) seen © Jory era = aes Cd ey ag . Ven9 qa = Glug aon aheey “(Ua Weta + Gt ~ Ud = (4°) 38N Jooad dperqodye we aaty (e *(4'u)g suopeynuted jo soqumu aq) moge wogoid y “¢