MATH 211 Exam 2 With Solution, Fall 2005
American University of Beirut · Discrete Structures · 3 pages · with solution
More MATH 211 files
Show the text of this exam
MATH 211 EXAM II
Fall 2005
November 9
Name: K E A
Instructions. Please write your name when you first receive this test, write clearly and justify all
your answers. Every question or part of a question is worth two points (a total of 24 points). This test
sheet is to be submitted with your answers.
(1) Prove that nm! is O(n"). Show carefully the witnesses C and & in your proof.
(2) Prove that 154+ 23+.--+ n4 is O(n*). Show carefully the witnesses C and k in your proof.
(3) Find the remainder of 5554781334323.
(a) when divided by 5
(b) when divided by 9
(4) (a) Write the decimal integer 1021 in base 3.
(b) represent the number (4B1AF*);, in decimal. (make sure you provide the final answer.)
(5) Using just 7-cent and 10-cent stamps, any amount of money (or postage) greater than or equal
to k can be made. Find & and prove the statement using mathematical induction.
(6) (a) Use the Euclidean algorithm to find AND represent gcd(18,13) as a linear combination of
18 and 13.
(b) Find an inverse of 13 mod 18
(c) Find an inverse of 18 mod 13
x=7 modl3
r=3 mod 18
(make sure you write down the final answer for the solution(s) x)
(7) Use mathematical induction to show that n? — 7n+ 12 is a nonnegative integer whenever n > 3.
(d) Solve the system of equations
Do one or more of these Bonus Problems. You receive two points for each ‘round’ answer:
Bl Déja Vue. Use induction to show that a set with n elements has exactly 2” subsets.
B2 moderately challenging. Write a pseudo-code for an O(n) function that reports the second largest
value of a list with n integers, (Note: you still get one point if your function is O(n’).)
B3 Mind TeaZer. Use Induction to show that given any subset A with n +1 elements of the
set{1,2,3,--- ,2n}, then there is an integer in A that divides another integer in A.
Bon Chance
Ci) Wiss etn ayer eee eo eT
Niet ae Ler above (in Yas. right hand side) aS a ny,
sin] we pave Vr Lerwms , we gel nl< YE, oervre.
This is true Ser olf ny S6 ni < Con Wun>
Se Ke Coeek»
3 3 4 3 3 4
2) Similoe te 1) 5 1 cn » : p42 terre eM Qravn =n
Ie 3
is Se Caksi
ae 3
“n oA
3 a) s ( because a nah wOu mod Sas Pe Gest digit
b) 2 { & womb ee mod 9 equal He sum of its digits mod ?\
4) Divide nepestely by 3 and “pecerd s the TemarndOs +
a) le2l= 3x 340 +4)
340 = 3x ll34 ®
113 = 3x3% +@ Se write the nemaindor
3% = 3x12 +@ starting with the Yast me
12 = 3x4 +@ dicatrg
be eee Ps oe | (1401241), =Weo2l),
fim 3K Ooo)
b) (4BLAF). = 15 + toxl6+dx1Gny Lx 16 44x"
= 154160 4256 4 45,056 + 262,144 = 30%, 631.
5) Kis BY (note tht 4%, 49,49,50, 51,52 all wank, but not sat
Base case; K= 54: 2 sevens & Y tens.
Ind. Hyp: + Suppese at works Sor Some k > S54,
Ind, Step! we need be show thet it works for Kl:
o Suppor we have 2 tens in te representation of Ki,
then naplace them by thre Seven- cent stow ps, Hence.
in this case (kK+\) Can alse hepresen ted” by Sevens & tens.
e we nud te be abk to ne present (K+) in off Cases, so
Suppose the nrupnesentation of kK dees wok haa 2 ten
bee, ib has ome or less ten—cent stam se .
i) if it has ne tens , Huan it must have at hast Fr sits
Sine gst)
iW) if at Nas One ten, Teme VE + Se ta Damen n Pare :
\S “at Least 44, di Mesut Lens ¥ ik sh\\ vous t hove F
Sevens! (ox more)
in either cose, aeplace F sevens by 5 tens, making (44)
Tt follows by The principle eS mathematical tnduetion thet any
integer amount 2 54 canbe mate Using Sevens & tens,
Now geing \vackwonds :
13 =5x2+4+3 4=23-2«\
(a) 5 = 3xt42 >3-(5-3 =3x2-+5
3 = 2x14@) < ged 243 -5*%2)x2 5
= 1x240 @ VE SKS om IRE ES OD
= 1342 = (13-13) k5
=I3x%2 -18xK5 413 *%5
1 = Sk? a [8x3
Cverify: 13xF-\8x5 = 91-90 =1)
(b) From part @) we see thot 13x4-19?x5 = 4 mod 18
Wence 13x =4 mod 18, hence FZ ds an inverse of 13 medlt
(c) Similarly, (- 5) LS an vee of IP mod 13.
(4) we use the chinese nemainder thecem :
Sin@ (3 & \Z \ave relatively prime we Knew thet
Here és o las te this =
M, mod13 = 5 [part ©}
Mm, = 13 } /\3 a
Me mod 13 = ? [rate]
mz = 13 Mee ay, = 13
i
Se dhe golution us eoxeli ke F a FxI3x3 ~ ~ 357
(rote ! adding a mah ph of ie ives ane tir solulrn ,
24. ~354F 4 2x 13K 1% = et
(7) Bose caves wad! 3. tx tai2 = 6 > os
Ind. Wyp. + rc muyyst ok Sor Some K >3, en FkeAl2 > °
Tnd. step + we wort 46 shew thot (e+) ~ F(k+) +12 Pag 6
(Ka BK) 412 = Ky De t1-FK~F 412 =k 7k 412) 4(2K-6)
But (kK - 7K412) Do by hypothesis ; ¥ 2e>6 sina k>3
se thot (k +t) - 2K +0 412 is We sum of wel nen neg ab ve
teums , hen itis nm- negative ~The result follows by math. ind.