### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DISCRETE MATH MATH 055

GPA 3.93

### View Full Document

## 6

## 0

## Popular in Course

## Popular in Mathematics (M)

This 84 page Class Notes was uploaded by Kavon Feest on Thursday October 22, 2015. The Class Notes belongs to MATH 055 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/226599/math-055-university-of-california-berkeley in Mathematics (M) at University of California - Berkeley.

## Reviews for DISCRETE MATH

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

Math 55 Some Inequalities May 9 1999 154 pm The Exercises after Ch 32 in our textbook Discrete Mathematics and Its Applications 4th ed by K Rosen 1999 provide students good opportunities to prove things by Mathematical Induction Some of these things are inequalities about which one might ask How did someone think up that inequality After all if A gt B is true so is A gt BB for all suf ciently tiny B gt 0 ofthese in nitely many inequalities how did the one actually proved get chosen In some instances the choice seems arti cial as if the proof had been devised rst and then the result presented as a puzzle Find the proof In some instances the arti ciality becomes obvious when an inequality In gt 0 proved for positive integers n turns out to be true also for positive nonintegers n In what follows which is not for everybody some of the inequalities whose proofs by induction seem arti cial or laborious will be proved quickly andor improved by using the Calculus Harmonic Numbers The kLh Harmonic Number is Hk1112 13 1k711k for integers k gt 0 see text p 193 and p 201 5152 Many estimates of Hk are best obtained from estimates of t 1 the integral I x dt In x 1 7 In x for x gt 0 For instance 1x gt1tgt1x1 X inside the integral so 1x gt lnx1 7 lnx gt 1x1 and then lnk1 lt Hk lt 1 lnk follows by summing appropriate inequalities In particular when k 2H for n 2 0 we nd that Hk lt 1nln2 lt 1n since ln2 06931 cf p 201 51 Better estimates come from the observation that the graph of y lt is convex curved like L because d2ydt2 2t3 gt 0 and thus lies below its secants but above its tangents Consequently areas under the curve satisfy 1x1x12 gt 1nx11nx gt 1x12 Summing appropriate inequalities can you see which now establishes for k 2 m gt 0 that lnk 1271nm 12 2 Hk 7 HIn 2 lnk 12k71nm 7 12m When m 2 these two inequalities bracket Hk within 1 for all k 2 2 In particular when k 2n 2 2 we nd that Hk 2 H2 714 n71ln2 2 17n 21 n2 as claimed on p 193 though the last inequality here is unobvious This illustrates a nasty aspect of inequalities If you are asked to prove that A gt B but not told how you can end up proving an inequality A gt B that is stronger better because B 2 B and yet remain unaware of your achievement so long as you cannot prove B 2 B For proving inequalities there are tricks but no routine procedures analogous to simpli cation procedures that so often prove the equality of algebraically equivalent expressions This is why computerized algebra systems like Mathematica and Maple still handle inequalities ineptly Many people not just students nd inequalities too troublesome and avoid them leaving rewarding careers open to students willing to rise to the challenge Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm AT Anlmr A n A Math 55 Some Inequalities May 9 1999 154 pm Bemoulli s Inequality Ifreal xgt7l andifreal p30 or p21 then 1 pxSl xp This ancient inequality dates from the early years of the Calculus though the text solicits a proof without Calculus and restricted to nonnegative integers p on p 200 ll Geometrically this inequality says that the graph of 1 x is convex U shaped and therefore lies above its every tangent particularly the tangent drawn through the point on the curve where x 0 Our proof will start from the derivative d 1 xp dx p1 9011 Consequently the integral 1 Pltlt1xgtP 171gtdxlt1XgtP717pX For all x between 0 and X the integrand p1xIF1 7 1 has the same sign as X because if Xgt0 and pgt 1 then p1x1171gt0 if Xgt0 and plt0 then p1x1171gt 0 if 71 ltXlt0 and pgt 1 then plxIH 71lt0 if 71 ltXlt 0 and p lt 0 then p1xlH 71lt 0 Therefore the integral is nonnegative which con rms Bernoulli s Inequality This inequality gets reversed if 0 Sp S l can you see why DRAW GRAPHS I Sums of Reciprocal Squares For any integer k gt 0 we seek close estimates for Sk ll l4 19 ll6 lk2 Two good ways to nd estimates both start from known formulas One way uses the formula lmm1 lmlm2 lk7lk lm 7 lk obtained from the text s p 200 6 or by Telescoping as in p 79 20 This way provides Sk71lt 112 l23 l34 lk7lk l7 lk for kgt l which is what the text asks you to prove on p 200 18 A second way to estimate Sk uses the Xt 1 72 1 1 mtegral I t dt 7 for x gt 0 Smce the graph of lt2 1s convex 1t11es below 1ts x x x l secants but above its tangents see Harmonic Numbers above consequently lx2 lxl22 gt lx 7 lxl gt lx 122 These two inequalities can be proved by algebraic means alone with no appeal to Calculus can you see how Summing appropriate inequalities now establishes for k gt m gt 0 that lm 7 l2m2 7 1k 1218 lt sk 7 sn lt lm 12 7 1k 12 When m 2 these two inequalities bracket Sk well within 2 for all k 2 2 In particular SkS 16571k12 lt 271k for k22 Sums of Reciprocals of Square Roots For any integer k gt 0 we seek close estimates for Rk lWl lW2 lV3 lWk Two good ways to nd estimates both start from known formulas One way uses a formula lVm Vnt1 1Vnt1 Vnt2 1Vk71 Wk 7 Vk 7 m obtained by telescoping This way provides Prof W Kahan Page 2 Math 55 Some Inequalities May 9 1999 154 pm Rk gt 2V1 V2 2V2 V3 2V3 V4 2Vk yam 2Vk1 7 2 as reqested in the text on p 201 53 A second way to estimate Rk uses the integral 1 J t 1Halt 2xl 7 ZVx for x gt 0 Since the graph of lWt is convex it lies below its X secants but above its tangents see above consequently lWx 1xx12 gt 2Vxl 7 2Vx gt 1xx 12 These two inequalities can be proved by algebraic means alone with no appeal to Calculus can you see how Summing appropriate inequalities now establishes for k gt m gt 0 that Wk 12Vk 7 mm 7 lZWm lt Rk 7 Rm lt 2Vk 12 7 2Vm 12 When m 2 these two inequalities bracket Rk well within 1 for all k 2 2 In particular Rk 2 Wk 12Vk 17 7N8 gt 2Vk1 7 2 though the last inequality is unobvious A pattern is emerging for these sums of series To see how far this pattern can go look up the Euler Maclauriri Sum Formula in Advanced Calculus texts or old Numerical Analysis texts In these texts repose several centuries lore about rapid approximate computations of functions whose exact computation would be intolerably onerous One more example follows Stirling s Approximation to n Example 10 on p 195 of our textbook proves an estimate n gt 2H for n 2 4 by induction This is too crude an estimate for the needs of this class What follows proves an old published in 1730 formula James Stirling s Approximation n rs nen whose relative not absolute error approaches zero as n approaches 00 For example Table 1 Stirling s Approximation n n v2nnne Rel error 10 3628800 360106 08 20 24331018 24231018 04 40 81591047 81421047 02 80 715710118 714910118 01 160 471510284 471210284 005 A much better approximation can be obtained from the nonconvergent Asymptotic Series n z Vmnenexp 112n 7 1360 113 11260n5 7 11680n7 for large n but it lies far beyond the scope of this course Instead the integral l lnxdx xlnx 7 x will be exploited to estimate upper and lower bounds for the nite series lnn 2101 lnk ln2 ln3 ln4 lnnil lnn for n gt 1 as was done before except that the graph of lnx is concave curved like now because lnxquot ilx2 lt 0 so the graph lies above its secants but below its tangents Consequently Prof W Kahan Page 3 Math 55 Some Inequalities May 9 1999 154 pm lnx lnxl2 lt If 1 In t dt 7 x 1 7 In x 1 7 1 7x7 In x lt lnx 12 As before summing appropriate inequalities implies nl2lnnl2 7 n 7 32ln32 l lt lnn lt nl2lnn 7 n 2 7 32ln2 The upper bound exceeds the lower by l 7 32ln43 7 nl2lnnl2n l2lnl7zz 0568477 lt 00685 where z l2nl and lnl7zz 7l 7 22 7 223 7 234 7 245 7 Consequently 089 lt 0962 7 00685 lt Cn lnn 7 nl2lnn n lt 2 7 32ln2 0962 This Cn is a decreasing function of 11 because after some algebra Cnl 7 Cn 7 1 l2lnl7zlzz 7 7223 7 245 7 267 7 lt 0 Therefore as 11 increases towards in nity Cn decreases towards alimit C gt 089 Although Stirling did not know it at rst this constant C turns out to be lnW 0919 as shall be proved in a moment For now we conclude for some constant C between 0962 and 089 that lnn 7 nl2lnn n 7 Q approaches zero or equivalently that n eCVnnefl approaches 1 descending as 11 increases towards in nity To determine C we obtain an estimate for 7 found rst by John Wallis who died in 1730 but derived nowadays more rigorously by using Integration by Parts as follows For m 2 2 set Jm J s2 sinx mdx 7132 sinx m Tldcosx 32 cosx alsinxm71 using I by P 72 7 2 m 7 1 f5 cosx 2 sinxm dx 7 M 71m 17 sinx2 sinxm dx from which follows that Jm m7lJm2 7 Jm l 7 lmJm2 provided we also set J1 Ig2 sinx1dx l and J0 IFS2 sinx de TE2 Now induction on k 0 l 2 3 in turn provides con rmation for the formulas J2k1 7 2kk22k1 and J2k 7 2k7c22kk2 Moreover because 0 lt sin x lt 1 inside the range of integration 0 lt Jm lt Jmil Consequently I gt JmJHH l 7 lmJm2Jm1 gt 1 7 lm gt 1 and therefore JmJm4 gt 1 as m gt 00 and so does TE2J2k1J2k 2kk42kl 2k gt TE2 as k gt 00 That quotient of factorials etc is Wallis estimate for TE2 Replace each factorial in that quotient by its Stirling approximation n 7 eCWnnen and let k gt 00 We nd that Stirling s approximation to 2kk42kl 2k simpli es after a lot of algebra to e2C1 392 21 l2llt 2k 32 gt eZC4 as k gt 00 since 1 l2k2k gt e This implies that eZC4 TE2 whence eC W completing the vindication of Stirling s Approximation n 7 nen Prof W Kahan Page 4 Math 55 Some Inequalities May 9 1999 154 pm Arithmetic vs Geometric Means Given collections of positive variables x and positive weights wj where we restrict subscript j to some nite set solely to avoid the technicalities associated with convergence if j were allowed to range over an in nite set let W w EJWJ A 21 wjxjw and G Hjxj 1 Here A is the Weighted Arithmean Mean Average of the numbers x and G is their Weighted Geometric Mean To some extent these de nitions are redundant because lnG is the weighted arithmetic mean of the numbers lnxj but this is no time to quibble about terms that lw have been in use for millennia Our objective is to prove that A 2 G with equality just when all the x s have the same positive value This inequality is the same as on the text s p 201 55 except that the text considers only the special case when all weights wj l and supplies a long unobvious proof by induction of which only Gauss could be proud and was Our proof will be very short First we simplify the notation by de ning fractional weights wjw gt 0 so that f 7 7 7 f 2171 A727 and G71jxj Next observe for any x gt 0 that 0 S 7 jdt lnG 7 lnx 7 l xG because so long X as the integrand s t lies strictly between x and G the signs of G7x and of lt 7 lG must be the same Ofcourse 0 S becomes 0 just when x G Now replace x by x multiply by and sum over j to deduce that 0 S 0 7 l AG as was claimed Prof W Kahan Page 5 Mathematics 55 Spring 2005 Lecture 14 Wednesday 2232005 More on Proof By Induction Please read 34 for this Friday7 and 35 for next Monday I plan to devote 4 more lectures7 including today7s7 to Chapter 3 Example Prove by induction that every positive integer 2 2 can be represented as a product of powers of prime numbers Clari cation A factorization with a single factor is allowed Thus 2 2 is considered to be a prime factorization of 2 Attempted Proof The rst small point is that were only supposed to prove something about all n 2 27 rather than all integers n 2 1 Let Qn be the statement that n can be represented as a product of positive integer powers of prime numbers Let Pn be the statement 2 2 a If we prove Pn for all n 2 1 then we will have proved Qn for all n 2 2 Basis step If n 1 then n 2 2 is False7 so P1 is True First attempt at inductive step Let n be a positive integer We want to prove Pn 1 There are two cases If n 1 is prime then the desired factorization is simply to write n 1 as itself this is one of those factorizations having only one factors ii If n 1 is not prime7 then by de nition of a prime number7 there must exist at least one integer factor q gt 1 that divides n 1 Choose one such factor q7 and write n 1 qr where r is another positive integer Now both q7 r are lt n 1 the inductive hypothesis applied to both q7 r then we could express each as a product of powers of primes Multiplying together their two factorizations would yield a factorization of n 1 as a product of powers of primes7 completing the inductive step D Thus we see that it could be useful to have a different kind of inductive hypothesis7 of the form W The principle of strong induction says that this is a valid method of inference More precisely7 the principle of strong induction says that 131 VnPk for all k g n a Pn 1 a VnPn where the UofD is N Epample Prove that the greedy algorithm for the lecture scheduling problem always produces an optimal solution De nitions of terms The scheduling problem UC Mudville opens7 and each aca demic department submits a nonnegotiable list of lectures it wants to hold Lecture j begins at time oh and ends at time e j ranges from 1 to n These times are arbitrary a lecture might begin at 917 and end at 9327 while another might begin at 921 and end at 1005 Alas7 due to construction delays7 there7s only one lecture hall The scheduling of ce wants to t in as many lectures as possible7 but of course no two at the same time How to choose which ones Two lectures are not considered to overlap if one begins at exactly the moment when the other ends The greedy algorithm Choose whichever lecture ends earliest In case of a tie7 choose any one ii Discard all lectures that overlap with the chosen one Then go back to step i7 choosing only from among those lectures not discarded Repeat until no lectures remain Here7s a series of pictures illustrating a sample set of lectures and the application of the greedy algorithm Time runs horizontally7 from left to right the time axis is not shown Each line segment denotes a lecture the left endpoint indicates its beginning time7 and the right endpoint its ending time Figure 1 All proposed lectures above Figure 2 The lecture ending earliest has been selected7 and all other lectures that overlap with it have been discarded Figure 3 Among remaining lectures not including the one selected above the one ending earliest has been chosen and all lectures overlapping with it have been dis carded Figure 4 Final outcome of the greedy algorithm Question Why is this called a greedy algorithm See below for answer Theorem The greedy algorithm always produces an optimal solution To formulate this more precisely given a set of lectures L de ne greedyL to be the number of nonoverlapping lectures one gets by applying the greedy algorithm to L The theorem says that for any nonoverlapping subset S C L 5 S greedyLl lt doesn7t say that some alternative selection might not give just as many nonover lapping lectures only that none can give more It doesnt require that an alternative selection be made in any systematic way it compares the greedy algorithm to any other selection whatsoever Proof Let Pn be the statement that for any set L of 71 lectures l greedyLl 2 8 for any nonoverlapping subset of L Our goal is to prove VnPn where of course the UofD is N The basis step is trivial lf there7s only one lecture then there7s only one possible choice the greedy algorithm gives that only possible choice Strong inductive step Let n E N and assume k S n a Let a set L of n 1 lectures be given In order to simplify notation we identity lecture 239 with the number 239 thus A 1 2 n 1 Suppose that lecture J ends earliest that is a S e for all 239 Let A be the set of all lectures that do not overlap with lecture J Then A consists of n or fewer lectures Applying the greedy algorithm to L gives the same result as selecting lecture J and 3 then applying the greedy algorithm to A That is greedyL 1 greedyA Consider any set S of nonoverlapping lectures Let K E S be a lecture that ends earliest Express S as S TU where K T Then eK S b S e for any 239 E T Since e S eK this means that no lecture in T overlaps with lecture J Thus By the induction hypothesis lTl S greedyA Thus lSl 1 lTl 31 greedyA greedyL D Here7s some material that wasn7t included in the lecture due to time constraints Comment There are many many greedy algorithms We saw another earlier in the semester dealing with making change Greedy algorithms arise in problems where one makes a sequences of choices among alternatives in attempting to optimize or maximize something Choosing one alternative narrows the eld of possibilities for the next choice and so on In a greedy algorithm roughly speaking one makes whichever choice appears to yield the greatest immediate progress towards the goal without considering what will happen down the line In chess this means thinking only of the present move rather than thinking ahead In making change it means using the largest denomination of coin available so that the remaining change to be made is minimized In the scheduling problem it means choosing whichever lecture ends earliest so that the greatest amount of time remains for the scheduling of additional lectures We7ve already learned text and problem set discussions of making change with various denominations of coins that sometimes greedy algorithms produce optimal solutions but sometimes they do not Greedy algorithms are generally easy to implement 7 just as chess would be easy if one never had to think ahead Thus it7s often useful to prove that a greedy algo rithm is optimal for one then has a simple and optimal solution There are lots of other examples of proofs by induction in our text I recommend studying them There are two theoretical points you might be wondering about 1 What justi es the principle of induction That is why is it a valid rule of inference 2 What justi es the principle of strong induction The well ordering property of N or of N 012 N U 0 Every nonempty subset of N contains a unique smallest element That is if S C N is nonempty then there exists n E S such that k E S a n S In this course7 we accept the well ordering property as an axiom about N7 that is7 as a fundamental assumption that is not proved In mathematics one must begin with some axioms one can7t prove something from nothing at all In more advanced treatments one starts with the theory of sets and with a small list of axioms about sets7 and one proves the well ordering property from those axioms To do that would take us much of a semester7 and although fascinating7 would probably not signi cantly advance our understanding of the subject matter of this course So I hope that you7re willing to take the well ordering property for granted Proof that induction is a valid method of inference Suppose given some predicate Suppose that P1 is True7 and that V71 6 NPn a Pn 1 is True We must prove that Pn is True for all n E N Let S be the set of all n E N for which Pn is False we want to prove that S is empty If not7 then by the well ordering property7 S has some smallest element7 k Let n k 7 1 Then 71 S7 since k is smallest Therefore Pn is True Then both Pn and Pn a Pn 1 are True7 so Pn 1 is True by modus ponens Thus Pk is True7 so k S7 a contradiction Thus S must be empty D Math 55 CONIPLEXITY vs COST August 24 1999 422 pm Introduction Does Complexity of an Algorithm make sense or is it an abuse of language The cost of an algorithm makes sense cost can be measured in time consumed memory occupancy arithmetic operations performed memory movements The complexity of a task makes sense it is the minimum among all algorithms that perform the task of these algorithms costs This use of complexity appeared in the 1960s in the works of Richard Karp and of Shmuel Winograd and spread rapidly to other computer scientists In the 1970s a few mathematicians misapplied complexity to their determinations of the least costly algorithms in families of algorithms without establishing whether some families other than the ones they studied might perform the same tasks at lower costs By the late 1980s complexity had become a synonym for cost in some circles Kenneth Rosen the author of the course s text Discrete Mathematics and its Applications 4th ed 1998 uses complexity this way in his Chapter 2 When this kind of abuse of language gains currency it obscures distinctions that really do make a difference Lest these distinctions be lost altogether examples will be presented here of tasks and algorithms whose complexities and costs are interesting enough to persuade the student and other readers I hope that cost deserves to be distinguished from complexity The rst example is the factorization of an integer for which task simple algorithms cost far more than complicated ones The second example is the evaluation of a quartic polynomial a task whose complexity is slightly less than the costs of the most widely used algorithms The third example is Collatz s 3x 1 puzzle whose cost is small and complexity unknown The fourth example is Floyd s algorithm for nding the ultimate period of an iteration cost and complexity are about the same The fth example is M Brown s recurrence whose complexity is about nine times its cost The sixth example is a modi cation of Brown s recurrence that costs only slightly more but behaves with chaotic complexity Factoring Integers Finding the large prime factors of a very big integer 71 presented as a string of perhaps several hundred digits is a task that codebreakers would like to solve very quickly for reasons discussed in the text at the end of Ch 25 The simplest algorithm known forms successive quotients 712 713 715 717 719 7111 7113 7115 71 consecutive odd integers until one ofthese trial divisions goes without remainder whereupon the smallest prime divisor of 71 has been found Can you see why it must be prime Because a nonprime 71 must have at least one prime divisor no bigger than 71 the number of trial divisions need never exceed roughly V712 and if 71 pq for nearly equal primes p and q the number of trial divisions will not fall far short of V712 so this is a rough but fair estimate of this simple algorithm s cost in worst cases An almostsimplest algorithm forms successive quotients 712 713 715 717 7111 7113 7117 7119 7123 7129 71 consecutive odd integers not divisible by 3 5 nor 7 until one ofthese trial divisions goes without remainder whereupon n s smallest prime divisor has been found Roughly how much faster than the simplest algorithm is this one Can you program it to run ef ciently In case the smallest prime factor of n is not much smaller than n the foregoing algorithm can be sped up by interleaving it with Fermat s factorization algorithm For k 1 2 in turn test whether m k2 7 n is an integer in which case n kimkm Why does this algorithm always terminate Prof W Kahan Page 1 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm In any event these simple algorithms cost QOn operations in worst cases which is intolerable when the integer n is over a hundred decimal digits long However there are horrendously complicated algorithms that run far faster with worstcase costs conjectured to be as small as Oexp 2lnn13 lnlnn23 some of them are accessible through automated algebra systems like Macsyma Maple Mathematica How does ln compare with exp 2lnn13 lnlnn23 when n m 1010 7 10100 7 101000 7 The assignment of greater complexity to the simplest algorithms because they run so much slower than than the horrendously complicated algorithms is an assignment that affronts common and other senses But the complexity of integer factorization is a concept that makes sense even if as seems likely no single factorization algorithm minimizes the worstcase cost for all integers n Conceivably an in nite collection of factorization algorithms may exist each algorithm faster than all others for a relatively widely scattered set of integers n but none faster than all others for all integers n In this case if there is a function fn such that for every tiny u gt 0 an algorithm exists whose cost is Ofnn but none exists whose cost is Ofn this fn can reasonably be regarded as the complexity of integer factorization But no such f is known yet Suppose you discovered an algorithm that factorizes huge integers faster by orders of magnitude than anyone had thought possible before thereby undermining the security of widely used encryptions Which of the following actions would you pursue7 1 Publish your algorithm in a mathematics or computer science journal for all the world to see and use 2 Embed your algorithm in a computer program and patent that and collect royalties from licenced users 3 Keep your algorithm secret and sell it to the Ma a for a billion dollars Action 2 is not so different from 1 unless you can afford to hire lots of lawyers and expert witnesses to defend your patent against infringers Action 3 may place your life in jeopardy Quicker Quartic Polynomials Given real numerical coefficients a b c d e of a quartic polynomial qx ax4 bx3 cx2 dx e with a i 0 we seek a formula by which qx may be computed for a huge number N of different real numerical arguments x with as few multiplications as possible Can such a formula run faster than the usual procedure Homer s Recurrence qx ax bx cx dx e which costs four multiplications per argument x 7 What is the complexity minimum cost measured in multiplications per argument x of quartic polynomial evaluation These questions seemed important back in the days when multiplication took appreciably longer than addition recording and recalling Nowadays this is the case only for multiplication of multiword operands which is what we shall assume And we shall lump subtractions in with additions We shall assume also that rounding errors are negligible although in practice they can vitiate much of what we shall do Prof W Kahan Page 2 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm The answers to our questions depend upon technicalities For instance multiplications by small integers are free if they are replaced by additions 4Z ZZZZ takes two additions Consequently quartics like k4x 7 cl4 k2x 7 c12 92 in which k4 and k2 are small integers and cl and 92 are real constants cost only the two multiplications per argument x required to compute x 7 cl2 and x 7 cl4 But there are other quartics that cost more than two multiplications per argument x unless these are evenly spaced In the special case that every argument xJ x0 jB for j 0 l 2 N71 and real constants x0 and B i 0 the cost of computing all N values qxj can be reduced to a few multiplications and a few more than 4N additions as if the complexity measured in multiplications per argument of polynomial evaluation were practically zero To see how to handle this special case look up Finite Differences in a Numerical Analysis text We shall exclude this special case despite its importance for fast graphic displays of curves A family of formulas that cost three multiplications per argument x will be exhibited This family is complicated though less so than some other published families still the formulas presented below are complicated enough to challenge reader who wonder if they are correct First a slight simplification We shall construct first a formula to calculate a monic quartic FBCDE z 7 Z4 1323 022 Dz E with only two multiplications per argument 2 Monic means that the leading coefficient is l Then we can calculate any given nonmonic quartic qx with three multiplications per argument x in either of two ways qx aFba ca da ea x or qx signaFbh3 ch2 dh e xh where h jail4 There are many formulas that compute F with two multiplications a family of candidates is provided by GijmUVW z 7 22 iz Uz2 jz V k22 mz w 7 ijmVUW 2 which produces a monic quartic polynomial in z with just two multiplications provided i j k m are all small integers drawn perhaps from the set 1 0 l For almost every choice of those integers we get a formula to compute F with two multiplications after the constants U V W and some others have been assigned appropriate values as follows Choose small integers i j k m with i7 j T I Beiej4 s 7 D72CT8T3ijT27m R 7 C73T2Tij7ij 7k U 7 iR7Sij V ReU W 7 E7GiJkmUV0 T and then FBCDE z GilkmUVW zT The reader perhaps aided by a computerized algebra system is urged to confirm the correctness of these formulas Finally in one of the two ways mentioned above F generates a formula for qx that costs only three multiplications per argument x not the four that Homer s recurrence costs To attribute greater complexity to Homer s four multiplications than to the three needed by the formula generated by F and G above seems perverse Prof W Kahan Page 3 Math 55 CONIPLEXTTY vs COST August 24 1999 422 pm What is the complexity of quartic polynomial evaluation The formulas generated by F and G bring the cost down to three multiplications per argument but do not prove this cost to be minimal though it is minimal Real quartics that cannot be evaluated in so few as two multiplications do exist but the proof of their existence is subtle it goes roughly like this All the polynomials that can be evaluated in two multiplications and arbitrarily many additions of expressions made up from real constants and the indeterminate x can be shown to constitute a countable set of curves and surfaces of dimensions less than five in the fivedimensional space of real quartics like qx ax4 bx3 cx2 dx e Therefore the complexity of quartic polynomial evaluation is with rare exceptions three multiplications per argument Collatz s 3x 1 Puzzle Let Cxo be the least integer n for which anl when for k 0 l 2 3 in turn Xk1 xk2 whenever xk is even 3xk 1 whenever xk is odd starting from any positive integer x0 There is a puzzle here nobody knows for sure why such an n exists for every positive integer x0 nor has anybody found an x0 for which Cxo must be deemed in nite Among the rst 29 values of Cxo the size of C27 is a surprise xo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Cx0 0 1 7 2 5 8 16 3 19 6 14 9 9 17 17 4 12 20 20 7 7 15 15 10 23 10 111 18 18 This puzzle has been traced back to the 1920s when it was described by the late Prof Lothar Collatz of Hamburg The puzzle has also been attributed to the late Dr Stanislaw Ulam of the Lawrence Los Alamos National Laboratory among others The cost of computing Cxo the obvious way is proportional to Cxo but other ways exist to compute it at a cost usually small compared with Cxo when it is big see program collatz in the NUMTHEORY section of the SHARE library of Maple V Since nobody knows for sure whether G is always nite nobody knows its complexity though the obvious algorithm exhibited above is extremely simple Ultimately Periodic Sequences Given a function f that maps a set X into or onto itself and a member x0 of X a sequence x0 x1 x2 xn is generated by the recurrence xn fxn for n 0 l 2 in turn The sequence is Ultimately Periodic when xn xnp for some fixed p gt 0 and all sufficiently large n and then p is an Ultimate Period of the sequence For example all sequences generated so far for Collatz s puzzle have ultimate period p 3 because they have always turned into x0 x1 l 4 2 l 4 2 l Every positive integer multiple of an ultimate period p is another ultimate period the smallest ultimate period the greatest common divisor of all ultimate periods is called The Ultimate Period of the sequence Given f and x0 is there an algorithm that will detect the ultimate period p if one exists If no period exists the algorithm may run forever or until stopped by Prof W Kahan Page 4 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm an external agency A naive algorithm stores all of x0 x1 x2 xn fxn1 and compares each xn with every previous member of the sequence until a match with xnp occurs This naive algorithm costs N memory and Nz time for comparisons where N is the least n for which xn xnp There is a less costly way An algorithm attributed to Prof Robert Floyd of Stanford computes simultaneously xn fxn1 and x2n ffx2n2 for n 1 2 3 in turn and compares them until xm x2m at which point m must be a multiple of the ultimate period p then Xm1 Xm2 xmp are recomputed and compared with xm to determine p This algorithm costs a xed amount of memory and N time can you see why Re nements of this algorithm exploit available memory to reduce the time spent when N or p is not too big but as N 7gt co every algorithm that detects the ultimate period must cost QN time can you see why Therefore the complexity of detecting the ultimate period is N for each f and x0 M Brown s Recurrence Prof Morton Brown of the Univ of Michigan presented this problem in 1983 and its solution in A periodic homeomorphism of the plane on pp 8387 of Continuum Theory and Dynamical Systems Lect Notes in Pure amp Appl Math 149 1993 Dekker NY Prove that the sequence x0 x1 x2 X3 de ned by the recurrence Xn1 lxnl 7x114 for n 1 2 3 intum started from any real x0 and x1 not both zero is periodic with period 9 Experiments corroborate but cannot prove the claim For example X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 X0 X10 X1 71 0 1 1 0 71 1 2 1 71 0 3 5 2 73 1 4 3 71 72 3 5 7c 1 17139 772 2773 771 277 71 771 7 1 That so simple a recurrence has a period so big as 9 is surprising More surprising is the period s persistence in the face of roundoff when executed in oatingpoint arithmetic every subtraction is rounded off the sequence is still ultimately periodic with ultimate period 9 Evidently roundoff is not so nearly random as some people think Even more surprising is the length of the proof that the recurrence behaves as it does To keep that length within bounds we shall assume all real arithmetic to be exact no roundoff To prove the claim we identify consecutive pairs xn x1171 in the sequence with points in the Cartesian x y plane and abbreviate x y z and xn xn zn Then the given recurrence takes the form of an iteration that starts from an arbitrary zo and continues zn Hznil for n 1 2 3 in which Hz Hx y is defined by HX Y i ley a X Prof W Kahan Page 5 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm An example corresponding to the first instance in the table above is zo 071 151gt 1 zl 10 162 l 121 l Z7l2 Z3 0 l 18 71 l Z4 710 1907lzo Our task is to prove that H9z HHHHHHHHHz z for every point z Our task appears to be simply a matter of repeated substitution and simpli cation but actually it is complicated enough that no automated algebra system has been able to perform it without human assistance BERNE has required by far the least help The following proof is designed for human consumption Set the origin 0 0 0 For any u 2 0 and any z X y let uz uX My Provided z 0 as u runs through all nonnegative values uz traces a my a semiinfinite straight line segment emanating from 0 and passing through and beyond z Since Huz uHz if H9z z is true at any one point z 0 on a ray it is true at every point uz on that ray The one point we shall choose is the ray s intersection with a 9sided polygon H contrived to enclose 0 in its interior The vertices of H in order are the ten points zo Z5 zl z6 z2 Z7 Z3 Z8 Z4 z9 zo listed above zo was chosen because it and Z3 lie on the two vertical rays emanating from 0 these rays are the singularities of H where its derivative does not exist V Figure l ll 17 z z Z8 3 2 Z6 H z 4 gt X z1 zo z9 z5 This polygon H turns out to be invarian in the sense that HH H each application of H maps one edge of H to another and nine applications rotate H twice counterclockwise Since no edge crosses the vertical rays the action of H upon each edge takes one of the forms HX y X 7 y X on an edge throughout which X 2 0 HX y 7X 7 y X on an edge throughout which X S 0 Prof W Kahan Page 6 Math 55 CONIPLEXTTY vs COST August 24 1999 422 pm both free of the operator This reduces our task to simple algebra On each edge zizj where j i5 mod 9 we label its points with a parametric formula Zit Xit Yit whose parameter t runs from 0 to l as Zit runs along the edge from zi to zJ Of course each ZiH t HZit The formulas are tabulated below and show Z9t Z0t thus proving that Morton Brown s recurrence has period 9 1 11 signX1t X10 YiO Zj 0 071 t 71 z5 1 10 tl t z6 2 1 1 1 tl z7 3 0 1 7 7t 1 z8 4 710 7 H 7t z0 5 1 71 1 H 21 6 2 1 27t 1 z2 7 12 H 27t z3 8 71 1 7 71 H z4 9 071 t 71 z5 Let s construe his recurrence Xn1 l xnl 7 x1171 as an algorithm what are its cost and if different its complexity Both appear now to be modest even if the proof of period 9 is deemed lengthy However changing Brown s recurrence in a way that increases its cost very little can increase enormously its complexity by any reasonable measure as we shall see next Another Recurrence Somewhat Like Brown s Set constant K 1 or else set K fl For any real initial values x0 and x1 let xn1 lxnKl7lKlxn1 for n 123 There is good reason to believe that the infinite sequence x0 x1 x2 x3 is bounded this means that some function FK x0 x1 gt lxnl for all n Although a proof of boundedness has not yet been published we shall take it for granted in what follows When the recurrence is implemented in oatingpoint arithmetic with roundoff the sequence turns out always to be ultimately periodic albeit sometimes with a gargantuan ultimate period Henceforth we shall assume arithmetic is exact no roundoff in which case the sequence must be either aperiodic or because the recurrence is reversible periodic the sequence cannot be merely ultimately periodic If x0 and x1 are rational the sequence must be rational and if bounded periodic but the sequence can be irrational and periodic If the period exists it must depend upon K x0 and x1 How The dependence appears to be extremely complicated As before we identify consecutive pairs xn x1171 in the sequence with points in the Cartesian x y plane and abbreviate x y z and Xn1 xn zn Then the given recurrence takes the form of an iteration that starts from an arbitrary zo and continues Prof W Kahan Page 7 Math 55 CONIPLEXTTY vs COST August 24 1999 422 pm zn HKzn1 for n 1 2 3 in which HKz HKx y is de ned by HKX Y i lXKHKly X The map z 7gt HKz is an Area Preserving map but this fact has not yet borne much fruit The fixedpoints z HKz are the points ofperiod l The only fixedpoint of HK is z 0 Other starting points zo yield different periods or none The existence has been proved of starting points zo from which the sequence zo zl z2 Z3 is aperiodic but no such starting point is known yet perhaps zo V2 V3 is one for both K i1 There are closed polygonal domains in the zplane from which when started there the iteration provably produces periodic sequences For instance When K 1 If ever lxnl S l and Xn1 S l and lxn i nl S l these inequalities persist and the period is 6 except if zo 0 the period is l If 73 S x0 S 71 3 S x1 S l and 75 S x0x1 S 73 the period is 30 except when x0 x1 72 the period is 5 In particular if zo i V2 7V3 or if zo 7V2 V3 the period is 30 But if zo V2 V3 the period is huge ifthere is a period see Figure 2 If lXOJll S l2 lx174l S U2 and lxoixll S l2 the period is 114 except if zo 4 4 the period is 19 if 5 5 33 if 6 6 14 When K 71 If ever xn S 71 and Xn1 S l and 71 S anern these inequalities persist and the period is 3 except if zo 0 the period is l If 77 S x0 S l l S x1 S 7 and 77 S x0x1 S 71 the period is 24 except when x0 78 and x1 4 the period is 4 If lx0x1 7 20 S 73 l2x07x1 710 S 73 and lx072x1 10 S 73 the period is 102 except when x0 x1 10 the period is 17 If zo V2 V3 the period is huge ifthere is a period see Figure 3 If zo 4 4 the period is 4 if 5 5 54 if 6 6 25 All claimed periods were confirmed with the aid of the computerized algebra system DERIVE Is there for every integer p gt 2 at least one K i1 and at least one starting point from which the period is p Given an aperiodic sequence generated by our recurrence is there a different recurrence that generates the same sequence Evidently our recurrence costs little to run but behaves in a complicated way that raises innumerable questions If our recurrence is construed as an algorithm to which of its cost or behavior should the algorithm s complexity refer In Figures 2 and 3 below pairs x y are plotted in the complex plane as x yl Prof W Kahan Page 8 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm Figure 2 XYi gt X11YXi start 1732114142i a Period Figure 3 15 x x x x x x 15 10 5 0 5 10 15 20 Prof W Kahan Page 9 Math 55 CONIPLEXITY vs COST August 24 1999 422 pm Conclusion The cost of applying an algorithm deserves to be distinguished from its complexity The word complexity may pertain better to the algorithm s description or to its correctness proof or to its behavior than to its cost Advances in the mathematical sciences I was taught are esteemed to the extent that they allow us to understand more while obliging us to memorize less As scientists advance however they sometimes substitute foursyllable words like complexity for fourletter words like cost and work of humbler French and AngloSaxon origin Such substitutions do not strike me as advances in Science Prof W Kahan Page 10 Math 55 The Halting Problem March 13 1999 526 pm On pp 1812 of our textbook Discrete Mathematics etc 4th ed by Kenneth Rosen the treatment of the Halting Problem is not so clear as I would like The following treatment may be easier to understand Some strings of characters will be processed as potential programs much as compilers do it when a string P is presented to a compiler it produces a compiled program that the computer can run or else an errormessage t0 the effect that string P is not valid source program text Other strings will be treated as inputs to programs when a running compiled program reads such a string I it produces an output or error message after running for a nite time or else runs forever or until stopped by some external agency Can a program HP I be written to accept any two strings and then in a nite time tell whether the program compiled from string P ultimately halts perhaps with an errormessage or runs forever after reading input string I Alan Turing showed why no such program H can exist This conclusion saddens us because we often wish to know whether a program PI will ever halt and we can t be satis ed by just running it until it halts or until we lose patience and stop it perhaps prematurely What we desire is some kind of computation by way of proof that assures us in advance that P will not run forever after reading I in But Turing showed why unless P is designed with such a proof in mind no routine way exists to decide whether PI halts Suppose for the sake of argument that such a program HP I did exist we shall try to infer a contradiction that will prove no such H exists The text of H would look something like this string function H string P string I begin Text of a program that reads string P and checks its validity as a program then reads string I and computes whether PI would halt If P is a validprogram and PI would never halt re turn Program text runs forever with Input text else return Program is invalid or Input text lets it hal end program H From H a program KP could be constructed by copying the italicized text from H after the substitution of P for I and adding a few other changes The text of K would look like this string function K string P begin Text of a program that reads string P and checks its validity as a program then reads string P and computes whether PP would halt If P is a valid program and PP would never halt return Program KK halts else while true do run forever end program K Let s run KK submitting the text of K as input to K What would happen If HK K would have put out Program is invalid or Input text lets it halt then KK would run forever but if HK K would have put out Program text runs forever with Input text then KK would return Program KK halts Either way program HK K would have put out the wrong message so no such HP I can predict correctly for every program P whether it halts Prof W Kahan Page 1 Math 55 The Halting Problem March 13 1999 526 pm Why is our textbook s treatment of the Halting Problem not so clear as I would like Our textbook does not distinguish clearly between a program HP I that can examine the sourcetext of P and another program hP I that can invoke call P but cannot examine its text For example hP I could look like this string function hstring P string I begin programpointer CompiledCodeP reset StopWatch to zero and restart it If programpointer NULL programpointer I runs program PI If StopWatch Infinity return Program text runs forever with Input text return Program is invalid or Input text lets it hal end program h Of course hP I is a silly program because it fails to halt whenever PI fails to halt but we have to wait forever to nd out A similar cloud darkens our textbook s version of program KP on p 182 For all we know its sourcetext could look like this string function kstring P begin If HPP Programtextruns forever with Inputtext return Program kk halts else while true do run forever end program k What would happen when kk ran with the text of k as input If Hk k put out Program is invalid or Input text lets it hal then kk would never halt but if Hk k put out Program text runs forever with Input text then kk would return Program kk halts Either way if Hk k halted the message it put out would disagree with what kk actually did thus undermining our con dence in the correctness of H But this may be an unfair test of H When the text of k is read by Hk k it sees that k invokes Hk k but does not see the text of H Unable to see that text H cannot be expected to gure out what Hk k does and therefore cannot be expected to deduce correctly what kk does It is unfair to condemn H for failing to do what we desired but wouldn t let it do Can this unfair test can be put right by granting HP I a license to read its own sourcetext How to do so is not clear Trying to embed the sourcetext of H within H as a compiletime constant runs the risk of in nite regression like the picture FIGURE 1 on our textbook s p 203 that contains within itself a picture of itself Putting into H s sourcetext a statement that reads the le containing H s sourcetext runs the risk of reading that le in nitely often when H is run Whatever is done to avoid these in nitudes amounts to a constraint upon the way HP I may be written Then all that running kk can prove is that burdened by such a constraint H cannot do what we desire correctly This is far feebler than Turing s insight He saw why no conceivable program HP I that always halts can reveal always correctly whether PI halts Prof W Kahan Page 2 H 90515335 50 Math 557 Section 0017 Summer 2009 Propositional Logic 1 Which of the following sentences are propositions a Berkeley is the capital of California b What time is it c z l 3 d 2 2 3 Find the negation of the propositions a Today is Friday b At least two students in this class like apples c There is a student in this class Who likes apples d John has a cat Who eats bananas Let p 417 T be the propositions p Grizzly bears have been seen in the area 4 Hiking is safe on the trail T Berries are ripe along the trail Write these propositions using p 417 and T and logical connectives Berries are ripe along the trail7 but grizzly bears have not been seen in the area Grizzly bears have not been seen in the area and hiking on the trail is safe7 but berries are ripe along the trail lf berries are ripe along the trail7 hiking is safe if and only if grizzly bears have not been seen in the area It is not safe to hike on the trail7 but grizlly bears have not been seen in the area and the berries along the trail are ripe Hiking is not safe on the trail Whenever grizzly bears have been seen in the area and berries are ripe along the trail Construct a truth table for each of the compound propositions a PVQ A 10694 0 10694 A PM 0 FM 69 PM 61 0 H 4 69 d H 4 Show that p V q E p g and p q E p V q Show that pV qT E qu pVT andpA qVT E pAqV pAT Show that p A q and p V q are logically equivalent Show that each of these conditional statements is a tautology by using truth tables 6 Ha A 0 V 4l A 4 b lPH4AqHTl HCUHT 0 A 0 A 4l A q lPV4APHTA4HTl Art Show that each conditional statement from the previous exercise is a tautology Without using truth tables Show that p A q A T and q A 17 V T are logically equivalent H H H H to Math 557 Section 0017 Summer 2009 9 53quot H 5 533 7 00 50 Quanti ers l Let 131 denote the statement 771 gt 3 What are the truth values of 134 and 132 Let denote the statement 771 y 3 What are the truth values of the propositions Ql7 2 and Q30 Let 131 be the statement 771 1 gt I What is the truth value of the quanti cation VIPI Where the domain consists of all real numbers l Let be the statement 771 lt 2 What is the truth value of the quanti cation Where the domain consists of all real nuimbers Let 131 be the statement I 12 If the domain consists of the integers7 What are the truth values a 130 b 131 C 132 d 3951395 e WWI Suppose the domain of the propositional function Qzyz consists of triples z y and y Where I is 07 17 or 2 y is 07 or 17 and 2 0 or 1 Write out these r r using quot 39 39 and 39 39 a VyQ07y70 b HIQWJJ C 3ZdQ07072 Which of the following statements are logically equivalent a VIPI A QI and VIPIl A VIQIl 0 31031 A QI and 31PM A 31Q1l A A l Let Pz7 y be the statement 77 student I has taken class y Where the domain for 1 consists of all students in your class and for y consists of all computer science courses at your school Express each of these quanti cations in English a 3a w b 3IVyPIy CV13yPI7y d EWIHLy e Vy rpmy f VIVyPWy Translate each of these nested quanti cations into an English statement that expresses a mathematical fact The domain in each case consists of all real numbers a HIVWW y b VIVMW lt 0 A y lt 0 A W gt O C 39639962 gt y A I lt y d WWMI y Z l Rewrite each of these statements so that negations appear only Within predicates that is7 so that no negation is outside a quanti er or an expression involving logical connectives a dVIVyPW y b dVIHyPW y VyVMPW y V QL 9 de y PmyD A 0 1wa 9 VI 3yV2Pz y 2 32VyPz y AAA 39D SLO VVV l Determine the truth value of each of these statements if the domain for all variables consists of all integers a Vn3mn2 lt m b Hann lt m2 Vn3mn m 0 Hannm m 3n3mn2 7212 5 3n3mn2 7212 6 3n3mnm4AnAm l 3n3mnm4Anm2 vnvmapo m ngt2gt AA AAA rm C m Cu 0 VVVVVV A i l Determine the truth value of each of these statements if the domain consists of all real numbers a V5 gt 036 gt 0Vz5 gt 0 A 6 gt 0 A 12 lt 6 A z lt a b vzayvzm gt o A lt22 lt y A lt22 lt 12H c vzayvzm gt o A lt2 lt y A lt22 lt 12H Math 557 Section 0017 Summer 2009 Rules of Inference 1 For each of these arguments determine whether the argument is correct or incorrect and explain why E0 a All students in this class understand logic Xavier is a student in this class Therefore Xavier understands logic b Every computer science major takes discrete mathematics Natasha is taking discrete mathematics Therefore Natasha is a computer science major c All parrots like fruit My pet bird is not a parrot Therefore my pet bird does not like fruit d Everyone who eats granola every day is healthy Linda is not healthy Therefore Linda does not eat granola every Determine whether each of these arguements is valid If an argument is correct what rule of inference is being used If it is not what logical error occurs a If n is a real number such that n gt 1 then n2 gt 1 Suppose that n2 gt 1 Then n gt 1 b If n is a real number with n gt 3 then n2 gt 9 Suppose that n2 S 9 Then n S 3 c If n is a real number with n gt 2 then n2 gt 4 Suppose that n S 2 Then n2 S 4 Introduction to Proofs 1 Give a direct proof of the theorem 77If n is an odd integer then n2 is odd77 2 Prove that if n is an integer and 3n 2 is odd then n is odd 3 Prove that if n ab where a and b are positive integers then a S or b S 4 Show that at least four of any 22 days must fall on the same day of the week 5 Prove that 2 is irrational by giving a proof by contradiction 6i Prove that if n is a positive integer then n is odd if and only if 5n 6 is odd 7 What is wrong with this 77proof Theorem If n2 is positive then n is positive Proof Suppose that n2 is positive Because the conditional statement 77If n is positive then n2 is positive77 is true we can conclude that n is positive 8 What is wrong with this 77proof Theorem If n is not positive then n2 is not positive Proof Suppose that n is not positive Because the conditional statement 77If n is positive then n2 is positive77 is true we can conclude that n2 is not positive 9 ls the following argument correct It shows that n is an even integer whenever n2 is an even integer Proof Suppose n2 is even Then n2 21 for some integer kl Let n 21 for some integer Z This shows that n is even 10 If one corner square is removed from the 8 X 8 chessboard prove that the rest of the board canlt be tiled by 2 X l dominoes 11 If two opposite corner squares are removed from the 8 X 8 chessboard can the rest of the board be covered by 2 X l dominoes 12 If there are 367 students in a school prove that at least two of them celebrate their birthday on the same day Math 557 Section 0017 Summer 2009 P FP DEOquot 533 7 9 50 H 0 HHHH ewwe More on Proofs l Do there exist irrational numbers I and y such that my is rational Is it possible to tile 6 X 6 board by l X 4 rectangles Is it possible to tile 10 X 10 board by l X 4 rectangles A corner square is removed from the 8 X 8 chessboard Can the rest be tiled by l X 3 rectangles Let a aha l l l 7amn1 be a sequence of real numbers mJL 2 l are integers Prove that the sequence a has a nondecreasing subsequence of length n l or nonincreasing subsequence of length m l A frog is jumping on a 8 X 8 chessboard At each step the frog jumps from one unit square to one of the squares that is adjacent to the previous position of the frog squares are adjacent if they share an edge Is it possible for the frog to start from the lowerleft corner of the chessboard7 visit each unit square exactly once7 and finish its trip at the upperright corner of the chessboard Justify your answer A cube 3 X 3 X 3 is made of cheese and consists of 27 small cubical cheese pieces arranged in the 3 X 3 X 3 pattern A mouse is eating the cheese in such a way that it starts at one of the corners and eats smaller pieces one by one After he finishes one piece7 he moves to the adjacent piece pieces are adjacent if they share a face Is it possible that the last piece mouse has eaten is the central one Remark Pieces donlt fall down if a piece underneath is eaten first A chocolate has a rectangular shape of the form m X n The lefttop corner is poisoned Two players are playing the following game Players alternate the moves and in each turn a player choses one piece of the chocolate which is not previously eaten and eat that piece together with all pieces that are down and right to the chosen piece A player who eats the poisonous piece loses the game Which player has a winning strategy Determine the greates number of figures congruent to CE that can be placed in a grid 7 X 7 without overlaping such that each figure covers exactly 4 unit squares If a 5 X n rectangle can be tiled with n pieces congruent to E1 prove that n is even r If a and b are real numbers prove that a2 b2 2 Zabl r If a7 27 c are real numbers prove that a2 b2 c2 2 2ab be ca lf a7 27 c are positive real numbers prove that a3 b3 03 2 Babe lf a7 12 2 0 prove that 2a3 b3 2 3a2bl Math 557 Section 0017 Summer 2009 Sets and Set Operations 1 List the members of these sets a I l I is a real number such that 12 1 b I l I is a positive integer less than 12 c I l I is the square of an integer and z lt 100 d I l I is an integer such that 12 2 E0 Use set builder notation to give a description of each of these sets 3 0737679712 b 37 27170717273 0 77177170710 9 For each of the following sets determine whether 2 is an element of that set a z E R l I is an integer greater than 1 b I E R l I is the square of an integer C 27 2 d 12 2 e 12 1 2 f 2 Find the power set of each of these sets where a and b are distinct elements a a 3 a7 5 C 07 0 1 How many elements does each of these sets have where a and b are distinct elements a Pa757 ayb b may ah a 0 13030 Translate each of these quanti cations into English and determine its truth value a VI 6 Rz2 71 b Hz 6 Z12 2 c VI 6 Z12 gt 0 d 31 E R12 1 HA 123 andB 3a ndA X A B X A andA X B iProvethat AUAA A AA AUAU ANA0 F 01 53gt 590 I Draw the Venn diagrams for each of these combinations of the sets A B and C a A m B C b A B UA C c A B UA C39 1 Suppose that A 69 C B 69 Cl Must it be the case A B Hm HO iProvethat a A BUCAUC BUC b AnltBCgtgtltAnBgtC C ABUCUBCAUB0A H H H Math 557 Section 0017 Summer 2009 Functions 1 Determine Whether f is a function from Z to R if a f n in wxwWW 0 f n 521 i Which of the functions from m 127 c d to itself are onto a 0057 fba7 f067 1 d b 0057 fb177 f0 d7 fd0 C fad7 f0 57 f067 fdd Determine Whether the function f Z X Z A Z is oneto one or onto or both to 9 8 fm7n mn 3 771771 m2 n2 0 f mm m d fm7n W e min Determine Whether each of these functions is a bijection from R to R a 21 1 3 f1121 0 f I 13 wwm2 1 Is the functin f R4r A R oneto one 1 122 5 a 1 i l b f1I 5 Give an explicit formula for a function from the set of integers to the set of positive integers that is a oneto one7 but not ontoi b onto7 but not oneto onei c oneto one and onto d neither oneto one nor onto 7 Give an example of bijection f 01 A R 8 Let f be the function from R to R de ned by 14 Find f 1l7 f 1z l 0 lt z lt 17 and f 1zlz gt16 9 If f and f o g are oneto one7 does it follow that g is oneto one Justify your answer 0 Let f z N A N be a function such that 1 and for every integer n 2 2 Evaluate f2009i 1 Find all functions f R A R such that f1 fy y ffI7 for all my 6 R 2 Let a gt 0 be a real number and f R A R a function satisfying fza fz 7 for all z E R Prove that the function f is periodic ie there exists I gt 0 such that for all z b f z Math 557 Section 0017 Summer 2009 Relations H 1 Consider the set R 123 and the following relation N on R N 12 13 31 Which of the following statements are true a12ltbgt21ltcgt1sltdgt32 e For all p E R there exists 4 E R such that p N L f For all p E R there exists 4 E R such that 04V4P E0 Draw the graph of relation N from the problem 1 9 Draw the graph of the following relations on the set A 1 2 a b c and determine which of them are symmetric a p 0171 17a727b7572 b 9 A X A 0171 17a75727275 C T A X A 00707 17007 1776 4 Let A 123 4 5 Draw the graph of the relation p de ned as a For a b E A up if a b is divisible by 3 b For ab E A apb ifa S b c For a b E A up if a 2b is divisible by 3 d For a b E A up if a 7 b is divisible by 3 5 Which of the relations in the previous problem are a symmetric b antisymmetric c re exive d transitive e equivalence relations on i Represent the relations from the problem 4 using matrices N 1 Draw some random graph with vertices labeled by 1 2 3 45 This graph represents a relation Ask the members of your group to write down the relation represented by the graph Write down the relations represented by the graphs drawn by your groupmates 00 1 How many binary relations exist on a set with 5 elements 50 Let R be a symmetric relation on set C with n elements De ne the following function f on the set C f G A Z as fg card 1 91 6 R Prove that Egec is even Math 557 Section 0017 Summer 2009 Graphs 1 What is the difference between an undirected graph and the graph of a symmetric relation E0 QP FP 50 a Draw all undirected graphs with 4 vertices b If you have erased some of the graphs in the previous problem7 repeat the step a c Near each of the vertices write down the degree of the vertex with respect to the corresponding graph d For each of the graphs add up the degrees of all the vertices e Prove that the sum of the degrees of all the vertices is equal to the number of edges Does there exist a graph with 25 vertices each of degree 3 Does there exist a graph with 10 vertices each of degree 4 Which of the graphs from the previous problem are connected Which of them are trees Which of them are bipartite i How many edges are there in a tree with n vertices Let n gt 3 be an integer n teams participated in a basketball tournament Each team played one game with every other team There were no ties Prove that there exists a team A such that For every team B that won a game against A7 there exists a team C such that A won the game against C7 and C won the game against B Let A be a set of n points in space From the family of all segments with endpoints in A7 4 segments have been selected and colored yellow Suppose that all yellow segments are of different length Prove that there exists a polygonal line composed of m yellow segments7 where m 2 1 arranged in order of increasing length n Each of three schools contain n students Each student has at least n1 friends among students of the other two schools Prove that there are three students7 all from different schools who are friends to each other Friendship is symmetric If A is a friend to B7 then B is a friend to A Math 557 Section 0017 Summer 2009 P FW Algorithms i Describe an algorithm for nding the maximum largest value in a nite sequence of integers Describe an algorithm that takes as input a list of n integers in nondecreasing order and produces the list of all values that occur more than once Use the bubble sort to put 324 15 into increasing order Use the insertion sort to put the elements of the list 3 2 41 5 in increasing order Use the de nition of 77161 is Ogz77 to show that I4 913 4x 7 is 014 Give a bigO estimate for each of these functions For the function g in your function g of the smallest order a nlogn2 l n2 logn b nlogn 12 logn 1n2 1 c n2 nngi The conventional algorithm for evaluating a polynomial anz an71zn 1 pseudocode by procedure polynomialc a0 a1 i i an real numbers powerl yia0 for i1 to n begin powerp0werc yry a pawer end y ancn an1cn 1 alc a0 estimate that is Ogz use a simple mm a0 at z c can be expressed in a Evaluate 312 z l at z 2 by working through each step of the algorithm showing the values assigned at each assignment step b Exactly how many multiplications and additions are used to evaluate a polynomial of degree n at z c Math 557 Section 0017 Summer 2009 Number Theory 1 1 Evaluate the following expressions a 239 mod 29 b 495 mod 17 2 711111101112 d 1000 mod 47 e 1111 mod 1111 W W 1000 8 2 Prove that a E 12 mod n lt gt nl a E b 3 Solve the equations a 31 E 1 mod 5 b 51 E 1 mod 3 C 31 E 2 mod 5 Cl 41 E 2 mod 8 e 51 E 1 mod 4 4 Determine Whether each of these statements is True or False a lfaEb mod n andCEd mod n7 then aCEbd mod b If a E 12 mod n and c E d mod n7 then ac E 12d mod C If 01a 51b and a E 12 mod n for c E Z 07 then E mod 5 Prove the following statements a 12m0d3 6 01 b 12m0d4 6 01 6 Find all solutions to the equation 12 y2 322 w27 Where w7 Ly 2 E Z HHHHHH H 0 Math 557 Section 0017 Summer 2009 Number Theory 2 Find one solution to each of the systems of equations 1 E 3 mod 5 a z E 2 mod 7 213E2 mod b 31l E2 fnod 11 H If p gt 3 is a prime number prove that p mod 6 6 15 If I is an integer prove that 12 mod 3 6 01 F90 Let m be a natural number If a q E b 4 mod m q prove that a E 12 mod 5 Does a q E b 4 mod n imply a E 12 mod n on i If mln prove that for any two integers p and q gm 7 Find all pairs zy of positive integers such that 12 y2 7 9 Find all prime numbers p such that 710 l is a perfect square to Find all prime numbers p such that 2p l and 4103 l are prime as well 0 Find all solutions of the equation 12 y2 Sryz Where I y and 2 are positive integers 1 Find all solutions of the equation 13 y3 712y 4 Where I and y are positive integers 2i Prove that there are in nitely many prime numbers p for Which p E 3 mod 4 3i Prove that there is no integer m such that 10m 3 is a perfect square 4 Find all prime numbers p such that p5 51 is prime as well 5 Given n numbers zlzgulzn each of Which is equal to l or El suppose that 1112 1213 znzl 0i Prove that n is divisible by 4 i If a and b are relatively prime positive integers and c any integer prove that each of the equations az E 1 mod 12 and am E 5 mod 12 have integer solutions 7 If n is natural number such that 2n l and 3n l are perfect squares prove that 5n 3 can t be a prime number H 8 Find the set of all positive integers z y such that 12y z y is divisible by If y 7 HH 9 Among rst 2008 integers 1004 n n E Z integers are colored in green Prove that there are 2n green integers Whose sum is divisible by 2009 Math 557 Section 0017 Summer 2009 Induction 1 Let Pn be the statement 1 12ni 1 a What is the statement 131 b Prove by induction that 1 holds for every integer mi 2 Let Pn be the statement 2 i n2 37L 2 a What is the statement 131 b Prove by induction that 1 holds for every integer mi 3 If n 2 l7 prove that LLL L 24 46 68 2n2n2 4n4 g i Prove that 3 gt n2 4 5 One cell is removed from 2 X 2 board Prove that the remainder of the board can be tiled using the pieces congruent to Math 557 Section 0017 Summer 2009 Induction and Recursion 2 1i Prove that a 2373 3274 L 13 27 for n 21 b 1iil1i l39dl 7n22 ltcgt 17lt17gt1722 7732771211 2 The harmonic numbers H j 1 2 i i i are de ned by Hj 1 Use mathematical induction to prove that Hgn 21 Si Prove the identities a 21k12n whirl b 2271 k2 12 22 I I I n2 7101442527144 n 3 3 3 3 nn1 2 cEk1k 1 2 n i 4 If n is a positive integer prove the inequalities a 2 gt n2 n 2 5 quot l b in lt E27927 n 2 2 c Bernoulli If a gt 71 then 1 a 2 1 na 5 Prove that for each positive integer n the number 2 1 32n 1 is divisible by 7 6i Prove that for each positive integer n the number n 4n1 7 n D4 1 is divisible by 9 7i 1ffz Ilfr E and f fof0ofprovethat IlfmwnENi n 8 Find the general term of the sequence a an 731 n20 me a mix b zn1 zn8n n E N 11 1 C In1 In2n27 71207 10 2 d In1 Inan17 n 6 N7 11 17 a 1 e In 31771 2n 1 n 2 2 11 1 f In 31771 3n 1 n 2 2 11 1 g In 317171 n3n 17 n 2 27 11 1 h an2 2an1 3am n 2 07 a0 37 a1 1 9 EvaluatethesumSn gnENi 10 Prove that the elements of the Fibonacci sequence f1 f2 1 fn2 fn1 fn for n 2 1 satisfy 1 1 1 7 V3 fn7 7 7 7 forn21i 2 2 11 Prove that fofi f1f2 39 39 39 f2n71f2n 1622 12 Prove that fn1fn71 7 71 i 13 Determine the number of different ways in which 2 X n board can be disected into dominoes 14 Determine the number of different ways in which 2 X n board can be disected into dominoes 15 Does there exist a function f z N 7gt N such that n 1 N 121 1 i 16 Find all functions f Z 7gt Z such that y 1 z 1 for every two integers z and y H Math 557 Section 0017 Summer 2009 Counting 1 Determine the number of ways in which we can arrange four red and 6 green marbles in a row so that all green marbles stand next to each other Bart has 3 and 7 dollar bills only In how many different ways can he give 40 to Lisa using just his money In how many different ways we can assign of ces to two employees if the total number of of ces in the company is 100 gt590 1 How many different bit strings of length 20 are there 5 How many oneto one functions are there from a set with m elements to one with n elements 533 Determine the number of positive integers whose decimal expansion contains exactly 4 digits doesn7t contain equal digits and doesnlt contain the digit 3 N 1 How many bit strings of length eight either start with 1 or end with the two bits 00 9 How many integers between 1 and 1000 have all their digits different and donlt contain the digit 5 in their decimal expansion 50 Let S be a subset of the set 1 2 3 i i i 2n Assume that the equation I y 2n 1 doesnlt have solutions in 5 ie if z y E S then I y 2n 1 What is the largest number of elements that S can have Let n 2 1 be a positive integer 1f a1 1 i an are positive integers prove that it is possible to paint some of these numbers in green in such a way that the sum of green numbers is divisible by n Math 557 Section 0017 Summer 2009 H to CA3 F 5 1553 00 to H 53 H H H to H 9 H F H 01 H on Permutations and Combinations List all permutations of the set l234 List all 2permutations of the given set List all threeelement subsets of the set 1 2 3 4 5 How many bit strings of length 10 contain exactly four 1s it Let n and k be positive integers such that n 2 k 2 l Prove that n k If n gt k are positive integers prove that Let n be a positive integer Prove that f Prove that for every positive integer n and every two real numbers I and y the following equality holds 1y Z quot 10 j Prove that for every positive integer n the following equality holds ltzgtlt2gtltgt2v Prove that for every positive integer n the following equality holds ltzgtlt2gtlt1gtnltgto Give a formula for the coefficient of 1k in the expansion of a 21 i 39 b I 100 c lt 2 a100 Determine the total number of triples of nonnegative integers a b c that satisfy abc30 ln how many different ways can we give 10 identical apples to 3 different students In how many different ways can we give 5 identical apples to 20 different students so that no student gets all 5 apples All apples are supposed to be given to students In how many different ways can we distribute 15 identical apples to 4 different students so that the rst student gets less than 10 apples and the second student gets some number of apples divisible by 7 ln how many different ways can we distribute 15 identical apples to 4 different students if not all of the apples have to be distributed How many subsets of the set 1234 30 have the property that the sum of the elements of the subset is greater than 232 HHH Math 557 Section 0017 Summer 2009 Generating Functions 1 Find the coefficient near 13 in the power series of the function I 210 centered at 0 2 Find the coefficient of 15 in the power series of l 12 I4 15 3 centered at 0 3 Find the generating function for the nite sequence 0 21 5 4 5i 4 Find the sequence whose generating function is 1713f 5 Find the sequence whose generating function is 132 6 Find the generating function of the sequence an 37K 7 Find the generating function of the sequence given by an 3n ilen 0 1f 2 l n 8 Find the coefficient near I4 in the power series a 1z123 b 1 1 12 13 9 Find the function whose power series is 1 31k 321 331316 341416 0 ln how many different ways we can distribute 10 identical apples to 3 students 1 Let 5 be the number of triples a b c of nonnegative integers such that a 212 Sc n Calculate 220 2 Use generating functions to nd the number of ways to choose 10 bagels from three varieties 7 egg salty and plain 7 if at least two bagels of each kind but no more than three salty bagels are chosen HHH to H CA3 Math 557 Section 0017 Summer 2009 H E0 9 g 5 9051533 50 Combinatorics 7 Miscellaneous Problems Four friends One Two Five and Ten are located on one side of the dark tunnel and have only one flashlight It takes one minute for person One to walk through the tunnel two minutes for Two ve for Five and ten for Ten The tunnel is narrow and at most two people can walk at the same time with the ashlight Whenever two people walk together they walk at the speed of the slower one Show that all four friends can go from one side of the tunnel to the other one in 17 minutes A magical tree contains 2007 green and 2008 red apples Every time a child climbs the tree he she eats 2 apples After that a miracle happens when the child takes 2 apples of the same color one red apple grows on the tree when the child takes 2 apples of different colors one green apple grows on the tree What will be the color of the last apple Why A group of pirates found a pile with 2008 gold coins The rst pirate takes one coin from the pile and splits the remaining coins into two smaller nonempty piles The pirates continue coming Each pirate selects one pile that has at least three coins takes one coin from it and splits the remainder of the selected pile into two smaller nonempty piles ls it possible that at the end each of the remaining piles has 3 coins There are 298 students at the university Prove that 100 of these students can be painted in green such that the difference of the ID numbers of every two green students is divisible by 3 Prove that among any 100 numbers one can select 15 numbers such that the difference between any two selected numbers is divisible by 7 Does there exist a positive integer n such that the decimal representation of 3 ends in 7700001 Does there exist an integer n such that 3 has 2008 consecutive zeroes in its decimal representation Initially number 1 is 2008 times written on the blackboard A student is playing the following game at each step he replaces two of the numbers from the blackboard by the quarter of their sum After 2007 steps only one number will remain at the blackboard Prove that this last number must be greater than or equal to 12008 Each of three schools contain n students Each student has at least n1 friends among students of the other two schools Prove that there are three students all from different schools who are friends to each other Friendship is symmetric If A is a friend to B then B is a friend to A In how many different ways can we give 3 apples to 10 students ln how many different ways can we give 6 apples to 12 students Prove that 220 A Prove that 221 3 1 513 I Math 557 Section 0017 Summer 2009 Introduction to Probability H i Two different numbers are randomly chosen from the set 12 3 45 Let A be the event that the sum of the two chosen numbers is greater than 6 a Determine the set S of all possible outcomes b Determine the set A c Determine the probability PA of the event A E0 A fair die is rolled 2 times Your goal is to calculate the probability that the rst number is greater than the second a What is the set S of elementary outcomes b What is the set E that represents the event described in the problem c What is the probability of the event E 3 A kid is playing with an unfair coin When the coin is tossed it has 13 chance of getting tails and 23 chance of getting head The kid tosses a coin 3 times a What is the set S of elementary outcomes b What is the event E that the number of heads is odd c What is the probability of the event E F A fair die is rolled twice What is the probability that the outcome is an odd number each time the die was rolled 5 A player is tossing a fair coin 100 times For each of the tosses if it resulted in H the player gets a dollar otherwise he 49 loses a dollar Prove that the probability that the player didnlt lose money in this game is equal to g 21 0 5 on i A box contains one red and m blue balls m is a positive integer Bart and Lisa alternatively take the balls from the box without looking Bart starts the game and in his rst move he takes one ball at random from the box If he picks the red one 7 he is the winner Otherwise Lisa takes a ball at random from the box notice that now the box contains one red and m 7 1 blue balls If she picks the red ball 7 she is the winner If she takes the blue one then it is Bart s turn again and the game continues until someone takes the red ball For each value of m determine who has a bigger chance for winning Bart or Lisa Math 557 Section 0017 Summer 2009 Independence Conditional Probability 1 A fair die is rolled four times Denote by Ai 1 2 34 the event that the i th number is even Let C 123 be the event that the sum of the i th and i 1st numbers is even Which pairs of the stated events are independent E0 A fair coin is tossed twice Let A HHHT B HHTH C HT TH Prove that each two of A B C are independent but PA N B N O PA PB PC 3 A box contains the numbers 12 3 n One number is drawn at random from a box Denote by A the event that this number is divisible by 2 Denote by B the event that this number is divisible by 3 Determine all values of n for which A and B are independent 4 Three dice are given The rst one has sides labeled by the numbers 2 2 2 2 6 6 The second die has all sides labeled by 3 and the third die has its sides labeled by 11555 5 Two players A and B are playing the following game Player A chooses the die and then from the two remaining dice the player B chooses one Then each of the player rolls hisher die The winner is one who rolls the bigger number Who has a bigger chance for winning A or B 5 There are two boxes The rst box contains the numbers 12345 and the second box contains the numbers 3 4 5 6 7 8 A player rst tosses a fair coin 1f the outcome is H the player will pick a random number from the rst box if the outcome is T shelll pick a random number from the second box What is the probability that the chosen number is greater than 4 In each of the boxes all the numbers have the same probability to be chosen 533 Assume that A and B are the events for which PA gt 0 and PB gt 0 Prove that PAlB PBlA 7 Assume that A and B are two events such that PB gt 0 Prove that PA PAlB PB PAlB PB 9 Assume that A and B are the events for which PA gt 0 and PB gt 0 Prove that PBlA PA PltAlBgt 50 Suppose that one person in 100000 has a particular rare disease for which there is a fairly accurate diagnostic test This test is correct 99 of the time when given to someone with the disease it si correct 99 of the time when given to someone who does not have the disease a Find the probability that someone who tests positive for the disease has the disease b Find the probability that someone who tests negative for the disease does not have the disease H H Math 557 Section 0017 Summer 2009 H E0 CA3 F 5 533 5 90 Random Variables i A fair die is rolled 4 times a Determine the random variable that represents the sum of the obtained numbers in these rolls b What is the expected value for the sum of the obtained numbers Let X be a random variable Whose codomain is the set of positive integers Prove that nor i PX gt n i A fair coin is tossed until the total number of heads or the total number of tails reaches 3 What is the expected number of tosses a A fair coin is tossed until the rst tail appears What is the expected number of tosses b What is the expected number of tosses of a coin until the rst sequence HT appears Apu is selling donuts Each of them costs 2 dollars but some of them have a dollar bill insider Homer can t see if any particular donut has a dollar bill but once he buys it and breaks in pieces he can easily take the money out Homer has 6 dollars and he entered the Apu s store With the idea to eat as many donuts as he can afford If each donut has a dollar bill With a probability of 12 What is the expected number of donuts that Homer Will eat a A fair coin is tossed n times Denote by T the total number of tails Calculate E2T 1 b Find the closed form for the sum 220 2k l c Find the closed form for the sum 220 2k l 2k A cat a mouse and m different frogs are put randomly in a row all permutations are equally likely Let X be the number of frogs between the cat and the mouse Find EX in the closed form If X is a random variable prove that EX2 2 EX Markovls inequality If X is a positive random variable and a gt 0 prove that 1300 a lP Xgta S If X and Y are random variables prove that EltltX e W 2 W e W i If X is a random variable prove that for every real number a the following inequality holds PX 2 a g Mex ea H Math 557 Section 0017 Summer 2009 below 91 on 00 50 Probability 7 Miscellaneous Problems r If X and Y are random variables nd a constant a such that EX aY Y 0 r If X and Y are random variables then EXY2 S EX2 EY2i A random permutation is chosen from the set of all permutations of 1 2 i i i Let X be the number of xed elements in the chosen permutation for example the permutation 35241 of 123 4 5 has exactly one xed element 7 that is 4 Determine the expected value and the variance of Xi i Prove that 2123 n 2n 1i Two players A and B play the following game They are tossing a fair coin if it results a tail A gets a point if it results in H B gets a point The rst player who wins 5 points is a winner in t e game and will get a prize of 80 applesi However after 4 games 3 or which are won by A and the remaining one by B a thief comes and takes the coin How should players A and B divide the apples among themselves in a fair way i A box contains 100 red and 100 green coinsi Next to the box there is a huge pile with 10000 green coinsi A player is playing the following game She takes two coins simultaneously from the box and if both coins are of the same color she puts one green coin from the pile to the box if coins are of different colors she will take away the green coin and return the red coin in the box The player continue playing this game until only one coin is left in the box What is the probability that the last coin will be red A fair die is rolled until we get an odd number of heads followed by a taili Let X be the random variable representing the number of die rolls before this event happenedi Determine i 6 different numbers from the set 123456789101112 are chosen at random all outcomes have the same probabilities These numbers are painted in green and arranged in the increasing order 91 lt 92 lt 93 lt 94 lt 95 lt 95 The remaining 6 numbers are painted in red and arranged in the decreasing order 7 1 gt 7 2 gt 7 3 gt 7 4 gt 7 5 gt 7 51 Let X be a random variable de ned as X 251 1n 7 gill Calculate 100 different numbers from the set 121 1 1199 are painted in green each number has equal chance to be painted What is the probability that the sum of no two green numbers is equal to 199 or 200 ie what is the probability that none of the equations 1 y 199 and z y 200 have completely green solutions a Let X1 X2 H i Xn be independent copies of the same random variable Prove that for every number k PltX1X2mXn 2kgt1 3e1 n e b The coin is tossed 100 times Let 1 denote the probability that there are more than 90 heads in this experiment Prove that a S d m Math 55 Rational Approximations of lrrationals April 8 1999 738 pm Problem 17 on p 249 of our textbook Discrete Mathematics etc 4th ed by Kenneth Rosen is an application of the Pigeonhole Principle to an important problem How well can any given irrational number x be approximated by rational numbers mj whose denominators j are not very big These rational numbers are distributed rather unevenly For example for a given positive integer n the rational numbers mj with arbitrary integers m in their numerators and positive integer denominators j S n are some as close together as ln7l 7 ln ln7ln and others are as far from their neighbors as ln 7 On ln When n is big the gaps between adjacent rational numbers mj with denominators bounded by n can be very different All irrational numbers x that fall into a relatively narrow gap are far better approximated by some rational mj than are the irrational numbers x near the middle of a relatively wide gap For a given denominator j the best approximation mj to x has as its numerator the integer m nearest jx Given instead a bound n upon the denominator j we wish to choose it so that jx will differ as little as possible from its nearest integer m How small can we make that difference This note offers a proof simpler than the text s of a stronger statement than problem 17 s Given irrational x and positive integer n there exists at least one positive integer j S n for which jx and the integer m nearest jx differ in magnitude by less than lnl Here is its proof Let f0 x jx 7 this is the fractional part of jx and it can be rational for no integer j gt 0 lest x fox turn out to be rational In particular fox 0 therefore 0 lt fox lt l Moreover fox fkx if integers j and k are di erent because otherwise x 7 xik7j would turn out to be rational Therefore the set 0 x fax fox fn71x ux 1 consists of n2 distinct numbers y all lying between 0 and l inclusive We shall break this interval 0 S y S 1 into n1 disjoint subintervals to serve as pigeonholes for that set These pigeonholes are i7lnl S y lt inl for i l 2 3 n and nnl S y S 1 In a picture y l i O l 2 3 n l n n1 The last pigeonhole includes both its endpoints other pigeonholes include only their lefthand endpoints Each pigeonhole s width is lnl Since the set has more numbers than there are pigeonholes to hold them at least one pigeonhole contains at least two numbers from the set Therefore four integers jl jz m1 m2 must exist satisfying both 0 S jl lt jz Sn and l zx 7m2 7 01x 7m1 l lt lnl Let 0 ltj j2 7j1 S n so that jx 7 mz7m1l lt lnl End of proof The bound lnl cannot be reduced because when x is an irrational number extremely close to l n1 either lx or nx differs from its nearest integer by barely less than lnl Thus for every positive integer n there is at least one positive integer j S n for which the integer m closest to jx satis es lx 7mjl lt lnlj which can be rather smaller than l2n but maybe not if x lies near the middle of a relatively wide gap as mentioned above How strictly do we wish to bound the denominators j If we let j get slightly bigger than n can x be approximated perhaps much more closely This question motivates what follows Prof W Kahan Page 1 Math 55 Rational Approximations of Irrationals April 8 1999 738 pm We have just deduced that among positive integers j S n at least one satis es 1jx 7 m1 lt 1n1 for m ltltjx gtgt the integer nearestjx Consequently 1jx 7 ltltjx gtgt1 lt 1Q1 for such an integer j How many positive integers j can satisfy this last inequality For every irrational number x there are in nitely many integers j that satisfy 1jx 7 ltltjx gtgt1 lt 1j1 Proof by contradiction Suppose there were only nitely many such integers j Then integer N could be chosen so big that 1N1 lt 1jx 7 ltltjx gtgt 1 for all those integers j But we deduced above that there exists at least one positive integer J S N satisfying 1Jx 7 ltltJxgtgt1 lt 1N1 This is paradoxical On the one hand 1Jx 7 ltltJxgtgt1 lt 1N1 lt 1jx 7 ltltjx gtgt 1 for all those nitely many integers j so J could not be one ofthem and yet 1Jx 7 ltltJxgtgt1 lt 1N1 S 1J1 which is what characterized them Therefore there cannot be only nitely many of them End of proof Another way to state what has just been proved is For every irrational number x there are in nitely many pairs mj ofintegers that satisfy 1 x 7mj 1 lt 1j1j In each such pair m j x These rational approximations m j so unusually close to x can all be constructed from truncations of its nonterminating continued fraction For example 7 3 17 115 111292 11111112 1113 11114 314159 26535 89793 23846 Now 3 17 227 31428 differs from T by 000126 lt 156 Abetter approximation 3 17 115 333106 3141509 differs from TE by 0000083 lt1107106 barely And 3 17 115 11 355113 31415929 differs from TE by 0000000266 which is far tinier than 1114113 00000776 But 7 di ers from the next truncated fraction 3 17 115 11129210399333102 314159265301 by 581010 which is not much smaller than 13310333102 911010 Can you see why some ofthese fractions mj are much better than the bound 1j1j and others not much better In 1891 A Hurwitz proved that for each irrational x in nitely many pairs m j of integers satisfy 1 x 7 mj 1 lt 102 5 but there are some irrational numbers y for which at most nitely many pairs satisfy 1 y 7 mj 1 lt 1jz35u no matter how small the positive increments B and u may be an example of such a is y 1 W52 1 11 11 11 11 11 In 1955 HE Roth provedthatifan irrational 2 satis es 1 z 7mj 1 lt 1jp for any xed exponent p gt 2 and for in nitely many integers m and j gt 0 then 2 must be a Transcendental number this means that 2 cannot be the root of a polynomial equation with all coef cients integers To learn more about this subject see books like I Niven s DiophantineApproximations 1963 Wiley or JWS Cassel s Intro to DiophantineApproximation 1957 Cambridge UP or books on Continued Fractions like AYa Khinchin s 1964 Univ of Chicago Prof W Kahan Page 2 Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am The combinatorial coef cient nCk nlk nik ka It can be generated in Pascal s triangle by setting 0C0 1CO 1C1 l and then obtaining n1 Ck nCk nC191 recursively 110 1 1 1 1 quotck1 nck 2 1 2 1 n1ck 3 1 3 3 1 4 1 4 6 4 1 Pascal s Triangle 5 1 5 1o 10 5 1 6 1 6 15 2o 15 6 1 7 1 7 21 35 35 21 7 1 The following three problems are HARD they are not for everybody I Prove that if n gt k gt 0 and GCDn k l then an is divisible by n HW Lenstra lst Proof Let m nik gt 0 Since 1 GCDn k GCDmk k so is GCDm k l this means that integers i and j not both positive must exist satisfying jm ik l Then an 1mka m ikmkck jm 111ka ikmfkck kmkil Cmi1 i1nkmkilcki1 Ira11 1ch inrlckJ is evidently divisible by n This is HW Lenstra s proof 2nd Proof nCk is the number of nbit strings with k bits set to l and nik bits 0 Put these strings into boxes equivalence classes as follows Into each box put just those strings each obtainable from any other in the box by fewer than n onebit circular shifts For example if n 5 and k 3 one box will hold the strings 10101 01011 10110 01101 and 11010 In general each box must hold n strings because no two circularly shifted versions of the same string can match otherwise the number of onebit circular shifts required to turn this string into a copy of itself would have to divide both n and k and this is ruled out by GCDn k l Therefore the number an of strings is the product of n by the number of boxes This is Charles Holton s proof 3rd Proof an nnilenik is an integer GCDn nik GCDn k l so nTlenik must be an integer too so n must divide an This proof makes Problem 1 look too easy Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm an Anlmr A n A Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am 4th Proof To show that nCkn n7ln72 n7klk is an integer we must show for every prime p and integer exponent K gt 0 that whenever pK divides the denominator k it divides the numerator too The exponent K of this prime p in the prime factorization of denominator k is K lkpllkp2llkp3l lkpKllkpKHl because each term lkpml in the series is the number of integers among 1 2 3 k that is divisible by pm This series contains only nitely many positive terms beyond the last of which all terms vanish The numerator n7ln72n7kl is aproduct of k7l consecutive integer factors among which the number divisible by pm is at least k7lpml because the rst and last factors can both be divisible by pm therefore the exponent of p in the numerator s prime factorization is at least L 7 lk7lpl k7lp2l lk7lp3l Lk7lle Lk71th1J Now we must consider two cases according as prime p divides k or doesn t If p does not divide k then every k7lpml lkpml and therefore L K which implies that the largest pK that divides the denominator k divides the numerator too as claimed If p divides k then p cannot divide n since GCDn k l Now the largest pK that divides the denominator k divides the numerator n7ln72 n7kl too because nCk nn7ln72 n7klk is an integer Therefore nCkn n7ln72 n7klk is an integer as claimed End of proof 2 i For k l 2 3 4 prove that 217le is an odd integerjust when k 2K is apower of 2 Proof The simplest proof is a pictorial proof due to Prof Raimund Seidel based upon Pascal s recurrence Il Ck nCk Clel in arithmetic mod 2 which means 00 ll 0 and l0 0l l The picture is shown on the next page In this picture the odd values of an are plotted as l s or I s when n 2KJr1 7 l and k 2K 7 l or 2K and the even values as s or 0 s when k n2 or nil2 The idea behind the picture is that it is composed recursively of triangles within triangles within triangles If A is a triangle whose sides and bottom row are made up entirely of l s and if its top vertex corresponds to n k 0 while its bottom corresponds to n 2K 7 l then three such triangles can be assembled into the next larger triangle of twice the height thus Between the lower two triangles all plotted values are even So ends the proofbypicture An algebraic proof will be presented after the picture and a third proof will come about because this problem 2 is a special case ofthe next problem 3 Prof W Kahan Page 2 Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am k0123456789 110 1 1 II Ck1 Ck 2 l o l n Ck mod 2 3 lIIl lt 4 1001 5 110011 o00 11 6 1010101 7 lllIIlll lt 8 10000001 9 1100000011 10 10100000101 11 111100001111 12 1000100010001 13 11001100110011 l4 101010101010101 15 lllllllIIlllllll lt 16 10000000000000001 17 110000000000000011 18 1010000000000000101 l9 1111000000000001111 20 100010000000000010001 21 lloolloooooooooollooll 22 10101010000000001010101 23 llllllllOOOOOOOOllllllll 24 1000000010000000100000001 25 11000000110000001100000011 26 10100000lolooooololooooolol 27 11110000111100001111000Ollll 28 10001000100010001000100010001 29 llOOllOOllOOllOOllOOllO0110011 30 1010101010101010101010101010101 31 lllllllllllllllIIlllllllllllllll lt Second proof for problem 2 Every positive integer m has a binary representation for which are de ned Um the number of l s in the binary representation of m and Tm the number of trailing 0 s in the binary representation of m the exponent of 2 in the prime factorization of m Now we shall prove that TZkile Uk 7 l Suppose k Xloooooo in binary whence kil X0111111 Consequently Tk Uk l Ukil for all k gt 0 Moreover kZk lck 2k711k712 221lt712k 3ck1 so Tk T21H Ck 1 TZHCH Next eliminate Tk by subtraction to deduce that Tlt21H Ck 7 Uk TZHCH 7 Ukil TZk SCkiz 7Uk72 after replacing k by kil repeatedly diminish k by l T2 1C17U1 071 asclaimed Only when k 2K is a power of 2 is Uk l and then TZkile 0 which means that 217le is odd otherwise it s even End of second proof Prof W Kahan Page 3 Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am 3 Prove that nCk is an odd integer just when the binary representation of n is the logical OR of the binary representations of k and nik Proof To better exploit symmetry in this problem let m nik and let Hm k 1ka mkm k Intkcm Hk m so our task is now to prove that Hm k is odd just when the binary representation of mk is the logical OR of the binary representations of k and m To this end let us de ne for all nonnegative integers m and k the nonnegative integers mik k Ijm logical OR of the binary representations of m and k and mk k m logical AND of the binary representations of m and k For example take m 12 001100 and k 10 001010 in binary then mk 22 olollo but mik 14 001110 and mk 8 oolooo Note that mk mik mk this is true in general because the nonzero bits of mk are the carries generated when m and k are added Consequently mk mik just when mk 0 in other words what we have to prove is that Hm k is odd just when mk 0 This has been done with two rather di erent proofs The rst proof is by induction on mk using Pascal s recurrence in the symmetrical form Hm k Hmil k Hm kil Verify this yourself To start Hm 0 l is odd and m 0 0 so the desired result T is con rmed along the edges of Pascal s triangle and in the rst two rows corresponding to n 0 and n 1 above In the middle ofthe third row n 2 we nd Hl l 2 is even and l l l i 0 con rming the desired result in the third row too Let our induction hypothesis be that the desired result T is true for Hm kil and Hmil k at some m gt 0 and k gt 0 from which we shall infer that the desired result holds also for Hm k Hmil k Hm kil as follows Let M Tm and K Tk be the numbers of trailing zeros in the binary representations of m and k respectively If M K then m k 0 and mil km kil For example try M K 3 in which case In 1ooo and k 1ooo so mk 1ooo 7 0 but mil cgt111 and kil 0111 so mil k cgtcgtcgtcgt mkil Consequently when M K the induction hypothesis implies that Hmil k and Hm kil have the same parity even or odd so their sum Hm k must be even which con rms the desired result T Therefore we need consider only the case M i K henceforth and by symmetry we can suppose M gt K When M gt K we nd mil k 0 and mkil m k For example when M gt K 3 we nd m cgtcgtcgtcgt k lcgtcgtcgt mil k 2 ollll39olooo 01000 i 0 and m kil cgtcgtcgtcgt m k Consequently when M gt K the induction hypothesis implies that Hmil k is even so that Hm kil has the same parity as has Hm kil Hmil k Hm k which agrees with mkil mk and thus propagates the induction hypothesis to Hm k End of rst proof The second proof uses the two functions 00rx the greatest integer in x and fx x 7 x the fractional part of x For example 378 3 and f378 078 We shall apply these functions only to nonnegative arguments It is not hard to see why Lxyl 7 Lxl 7 lyl L fx fyl either 0 or 1 for all nonnegative x and y since 0 S fx lt l and 0 Sfy lt l Moreover W fyJ 0 just when fX fy lt 1 Prof W Kahan Page 4 Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am Now recall TN the exponent of 2 in the prime factorization of integer N For example Tl2 2 Apparently for any positive integer N TNl lN2llN4llN8llN16l lN2Kl because lN2Kl is the count of the number of positive integers divisible by 2K and no bigger than N The series contains only nitely many positive terms because lN2Kl 0 for all suf ciently big integers K Now for all positive integers m and k THm k Tmk 7 Tm 7 Tk Lmz ml 7 anl 7 Lml Lm4 1V4l7lm4l7l1d4l lm8 ml 7 lm8l 7 stl lml6 1d16J7Lm16J7L1d16J L fm2 f1d2l L fm4 f1d4l L fm8 f1d8l lfm16 f1d16l Therefore THm k 0 just when every lfm2K fk2Kl 0 for every K l 2 3 and only then is Hm k odd Thus our proof requires that we determine for which pairs m k are all the expressions lfm2K fk2Kl 0 instead of some being 1 For this purpose we shall extend the logical AND operation to de ne x y also for nonintegers x and y whose binary representations have at most nitely many binary l s after the binary point De ne xy 21ltgtlt2Ky2K whenever an integer K exists for which both 2Kx and 2Ky are nonnegative integers The restriction to nitely many binary l s after the binary point is a technicality that precludes the possibility that numerically equal but di erent binary representations X X0111111 and X X1000000 might prevent the numerical values of x and y from de ning x y uniquely Note that the binary representation of fm2K is obtained from that of m by shifting its bits K places right past the binary point and discarding bits still standing left of the point For example fl923 010011 01000 010011 0011 38 Also recall that lfx fyl 0 just when fx fy lt l Now lfm2 fld2l 0 just when fm2 fld2 0 and ifthis is true then lfm4 fld4l 0 just when fm4 fld4 0 and ifthose are both true then lfm8 fld8l 0 just when fm8 fld8 0 and if all three ofthose are true then lfml6 fldl6l 0 just when fml6 fldl6 0 and so on In short all of lfm2K fk2Kl 0 just when mk 0 and therefore that is when Hm k is odd End of second proof The solution to problem 3 also solves problem 2 as follows For positive integers k 217le Hk k7l is odd just when k k7l 0 which occurs just when k 2K is apower of Prof W Kahan Page 5 Math 55 Three Problems about Combinatorial Coefficients April 26 1999 657 am Epilog Each of the proofs presented above has been found by at least one UC Berkeley undergraduate taking lower division Math courses including Math H90 But in a class like Math 55 only a tiny percentage of the students can be expected to nd even one of the proofs much less three even though they require no knowledge beyond what has already been taken up in Math 55 If these problems are so hard why put them before students almost all of whom will be frustrated Part of a Math professor s job is to identify students with extraordinary mathematical capacities and to cultivate their talents These are the people upon whom all of us will depend to decrypt an enemy s secret messages to reveal the molecular structure of antibiotics and help synthesize them to help design crashworthy cars and aircraft to enhance the reliability and capacity of communication networks to help reconcile stability with liveliness in economic systems and to advance our understanding of persistent mathematical problems These are the students who can solve problems like the three above or reproduce their solutions after a casual reading Whether they work on Computer Science or on most of the best of modern mathematics they will use what they learn in Math 55 every day Part of a Math professor s job is to help students learn as much mathematics as they will need to perform competently jobs that require a little of it occasionally Some of these students will become the helpers or the employers of those mentioned in the previous paragraph some will take responsibility for the planning and management of pure water distribution and safe sewage disposal for the control of electric power grids that survive the loss of a power station without blacking out a whole state for helping design safe and economical housing and commercial structures These students should be able to follow every step of the proofs above and then perhaps appreciate the strategy that motivated the steps even if it is not a strategy that would have come to the student s mind unaided A few students will wish devoutly to avoid reading these proofs or despite diligent attempts to read them will be unable to follow the proofs steps nding too many that jump too far or get forgotten somewhere between their description and their application They re not for everybody Part of a Math professor s job is to help students discover before too late whether their talents include mathematics or lie elsewhere Many students whose mathematical capabilities are limited either by nature or by earlier exposure to an unfortunate education it is hard at times to tell which of these has played the greater role will none the less get jobs involving computers so these students should learn what they can and need to learn about computers But where A student s time at UC Berkeley is precious use it to learn well ideas that will serve you well throughout your life ideas each of which was earned by a great mind s lifetime of effort Most people who use computers have to know very little about them and that little is accidental and ephemeral better learned from a manual or book or community college or state university than from a crowded UCB Computer Science class full of very competitive hotshots Each student has to discover where his talents lie and what this world needs done that he can do well regardless of whether he likes it We in the older generations have an obligation so to order affairs that people who do well what needs doing well are rewarded for doing that We will never get it quite right but neither have we gotten it entirely wrong and some of us are able to change Prof W Kahan Page 6 Math 55 Coins and Stamps May 1 1999 659 pm Instances of a problem treated in general below were used to illustrate Mathematical Induction on pp 1989 p 200 Ex 19 3133 and p 227 Ex 9 in our text DiscreteMathematics andIts Applications 4th ed by K Rosen 1999 McGrawHill Every student is expected to be able to follow the proofs in this note but perhaps not to create them nor to reproduce them all Given two kinds of coins one worth M and the other worth N what sums of money can be made up using various numbers of these coins and no others Given two kinds of stamps one worth M and the other worth N what postage can be made up using various numbers of these stamps and no others In short what set 35 is generated by the expression xM yN as x and y run through all nonnegative integers This set 35 consists of certain nonnegative multiples of d E GCDM N In fact every multiple of d bigger than L E LCMM N 7 M 7 N turns out to lie in though this fact is not obvious to prove it is the purpose of this note The proof comes via Charles Holton from Yossi Fendel who didn t remember where he got it Dividing d into L and into every member of 35 including M and N simpli es the problem It becomes trivial if either of M or N is l so we assume henceforth that Mgt1 Ngt1 and GCDMNE1 Set 35 is still generated by the expression xM yN as x and y run through all nonnegative integers Our task is to prove that the largest integer L not in is L E MN 7 M 7N E M7lN7l 7 1 First some terminology For any nonnegative integer z we write 2 mod MN for the residue remainder left when 2 is divided by MN Aset of MN integers z is called a complete nonredundant set of residues just when every remainder 0 l 2 MN7l turns up just once among the residues 2 mod MN In particular every set of MN consecutive nonnegative integers is a complete nonredundant set of residues an example is the interval T of MN integers t that satisfy L lt t S LMN This T will gure in the proof Consider now the subset S of generated by the expression xM yN as x and y run through all integers that satisfy 0 S x lt N and 0 S y lt M The integers in S are not all consecutive 0 and M and N belong to S but 1 does not Still S is a complete nonredundant set of residues as we shall demonstrate now Every member s of S determines its x and y uniquely because if s E xM yN E xM yN then x7xM E y7yN but GCDM N E l and therefore lx7xl E 0 mod N and ly7yl E 0 mod M now the constraints 0 S x lt N and 0 S E lt N imply x E x and similarly y E y Therefore the MN pairs x y generate MN distinct members s E xM yN of S No two members of S have the same residue mod MN because if xM yN E xM yN mod MN then x7xM y7yN E 0 mod MN whence follows lx7xl E 0 mod N and ly7yl E 0 mod M and then x E x and y E y as before Therefore the MN elements of S provide all MN distinct residues which means that S is a complete nonredundant set of residues as is T Forexample if ME2 and NE3 then LE 1 TE 2 34 5 67 and SE 0 2 3 4 5 7 If ME2 and NE5 then LE3 TE45 6 7 89101112l3 and SE02 4 5 67 891113If ME3 and NE 5 then L E 7 T E 8 9 10 20 21 22 and SE 0 3 5 6 8 9101112l3l4 161719 22 The sets S and T overlap their largest elements are the same N7lM M7lN but the smallest element Ll E M7lN7l in T is rather bigger than the smallest element 0 in S Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm AI Anlmr A n A Math 55 Coins and Stamps May 1 1999 659 pm However whenever s lies in S but not in T which implies s SL then t s MN must lie in T because L lt MN S t S LMN but not in S since no residue mod MN occurs more than once in S In short TiS Q SiT MN Here the 7 is the setdifference operator and the adds MN to every element of SiT Since like S and T the sets SiT and TiS have equally many elements actually TiS SiT MN This set s every element t s MN xM yN MN xNM yN lies in and so since 35 gt S too 35 gt S U TiS S U T gt T Now that we know 35 gt T we can prove that every integer bigger than L lies in by induction as follows Partition the integers bigger than L into consecutive subsets T jMN for j 0 l 2 3 and let our induction hypothesis be that 5 gt T j MN for some integer j 2 0 We know this hypothesis to be true for j 0 For each integer t in T 01MN we nd that s t 7 MN belongs to T jMN which is contained in according to the induction hypothesis whence follows that s xM yN for some integers x 2 0 and y 2 0 Then t xNM yN must lie in 35 too and therefore 35 gt T QlMN too By induction 3 T jMN for every integer j 2 0 This part ofthe proof is the only part presented in our text So every integer bigger than L lies in 35 Now where does L lie L cannot lie in the subset S because its largest element is NilM MilN L MN E L mod MN and no residue mod MN can occur in S more than once L cannot lie in the subset 7SxMyN x20 and yZM or x2N and y20 because its least element is MN gt L Therefore L cannot lie in which therefore consists of every integer greater than L together with a scattering of integers less than L End of proof A challenging exercise Prove that exactly half the integers between 0 and L inclusive lie in Note why Ll MinNil is even GCDM N 1 so M71 and N71 cannot both be odd Now let J be the interval of Ll integers j that satisfy 0 S j S L To prove that exactly half these integers lie in 35 we shall show that whenever an integer s lies in J then Lis lies in J7 so there must be exactly Ll2 such pairs s Lis in J Jm7S 0 is empty because as was explained above the least element of 7S is MN gt L therefore J JmS U 7S JmS Since every integer s in J lies in S too every such s xM yN for some integers satisfying 0 S x lt N and 0 S y lt M Then MN Lis NilM MilN xM 7 yN NilixM MiliyN lies in S in which each ofthe MN residues mod MN occursjust once Since MN Lis E Lis mod MN we conclude that S cannot contain Lis which however does lie in J Therefore Lis lies in JiS which since J JmS implies Lis lies in J7 as claimed End of proof Prof W Kahan Page 2 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am Here are solutions to all 27 problems at the end of the notes on Probability theory by HW Lenstra Jr 1988 His combinatorial coe icient is here rendered Ck E nlklnEk PAndrew 0 1212 13 13 1 PBeatrix E 0 0 12 13 E 16 PCharles 1 12 0 13 12 2 Without a Joker the independent pairs are A B and A C but not B C With a Joker in the deck no pair is independent 3 Let M E PA and B E PB so that PA39 E 1E and PB39E1EB Since A and B are independent PAmB E 3915 Then M E PA E PAmB PAmB39 E 015 PAmB39 whence follows PAmB39 E M391EB Similarly PA39mB E kmB and PA39mB39 E km145 Thus A39 and B39 are independent because PA39mB39 E PA39PB39 Likewise for A and B39 But A and A39 cannot be independent since PAmA39 E PQ E 0 unless M E 0 or M E 1 4 Yes independent because Pdivisible by 3Pdivisible by 5 E 13l5 E 115 E E Pdivisible by 3 and by 5 Then PGCDnumber 15 E l E 1 E 13 E 15 l15 E 815 5 5000 700 310010000 E 060 6 For any number n the probability that n balls of any particular color will be drawn is the same for every color because of the situation s symmetry permuting the color s names does not change their probabilities Therefore the Expected number of balls drawn is the same for every color Since all three colors Expected numbers sum to 12 each Expected number is 4 7 a fx E x mod 3 and gx E x mod 4 so x E 4fx 9gx mod 12 by the Chinese Remainder Theorem Since 900 E 0 mod 12 as s ranges over the set S E 1 2 900 with uniform probability 1900 per element Pfs E m E 13 for each m in 0 l 2 and Pgs E n E 14 for each n in 0 1 2 3 and then Pfs Em and gs E n E Ps E 4m 9n mod 12 E l12 because 4m 9n mod 12 runs through all 12 members of 0 l 2 11 as m n runs through all 12 pairs Therefore f and g are independent 7 b Efg E Ef Eg E 1 32 E 52 Efg E EfEg E 132 E 32 and Variance Vfg E Vf Vg E 23 54 E 2312 because f and g are independent 8 Eemales E 93 E 3 Vemales E 929 E 2 assuming independence of sex of each birth 9 The number of ways of choosing 5 volumes out of 10 is 10C5 E 252 The number ofways to get no complete novel is 25 E 32 The number of ways to get one complete novel is 5C14C323 E 160 The number ofways to get two complete novels is 5C23C121 E 60 As a check we observe that 60l6032 E 252 Assuming each way as likely as every other PiE0 E 32252 E 863 PiE1E 160252 E 4063 PiE2 E 60252 E 1563 E 7063 E 109 Variancei E 200567 Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm AJ Anlmr A n A Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am 10 This solution takes advantage of three identities obtained by differentiating the rst twice 117q Emoq 117q22gtonq 1 217q3 2gtonn71q 2 Vf I 2ngt0 qn 1 39p39n 7 1p2 Engto q 1 39p 112 7 22ngto qn 1 3911 2ngt0 qn lp p39q392ngto n39n139q 2 p72392ngt0 n39qn 1 2120 qmp recall liq p 2pqp3 p72p2 lp2 2q p72 lp2 qp2 11 Any positive integer n and nonnegative fraction p S 1 determine a Binomial Random Variable f it is the count of the successes in n independent Bernoulli trials each with probability p of success Pf k Ckpkl7pn k Now Pf is even Eogjgh j nC2jp2jl7pn 2j and Pf is odd l 7 Pf is even In the special case that p l2 these expressions simplify to Pf is even Pf is odd l2 as is obvious if n is odd because then each term Ca392 n included in the sum 2 can be paired with an equal term CnizjTn excluded from that sum if n is even the simpli cation of the sum is not obvious However the 2H equally likely outcomes of n trials can be put into pairs that diiTer only in their rst trials since the members of each pair have opposite evenodd parity the odd counts f must be as numerous as the even counts and equally likely 12 The same reasoning as worked in Example 7 implies that 2 is the expected number of children whose rst name starts with the letter that they get The variance cannot be determined because it is positive unless all children s names begin with the same letter in which case the variance is zero 13 There are 2100 rs 1267651030 subsets ofa set with 100 elements The subsets with cardinalities between 41 and 59 inclusive number 24131659 mock 100C50 t 23921st loocsdk 119554391030 Their ratio is ll9554l26765 rs 09431 This ratio is the same as the probability that a binomial random variable counting the successes in n 100 independent Bernoulli trials with p l2 will depart from the mean np 50 by less than 105 2 times the standard deviation Vnpl7p 5 Chebyshev s Inequality says this probability is at least 1 l22 075 The Central Limit Theorem uses a Normal random variable see the class notes titled Law of Large Numbers distributed continuously with the same mean and standard deviation to estimate that a departure from the mean smaller than M times the standard deviation has probability near M 7 DELL but what value of M should be used for the given discrete distribution If M 105 2 then M 7 DELL rs 0955 overestimates the probability If M 95 18 then M 7 DELL rs 0928 underestimates the probability If M 955 19 then M 7 DELL rs 0943 gets it about right Prof W Kahan Page 2 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am 14 Random variable f has mean f Ef and variance 0392 Ef7f2 and random variable g lfifl has mean 17 Eg The variance of g is v Eg7 c2 Eg2 2 217Eg 12 Ef2f2 212 12 lt52 2 12 Since all three of V 039 and 17 are nonnegative 039 2 17 as claimed with equality just when V 0 which occurs just when g is constant 17 instead of random which occurs just when f takes at most two values each with probability 12 15 Let random variable f have mean f Ef and variance 0392 Ef7f2 Chebyshev s Inequality says Plfifl 2 r S 0392r2 meaningfully only if r 2 039 because 62 21142521362 2 02521362 2H2 PWP64 2 2H2 02521362 2 ENE 91364 rzPof 2 r with equality just when E ti q tiffP64 0 and E ti x r2Pf 0 The rst equation here implies PO lt lfifl lt r 0 and the second implies Plfifl gt r 0 so random variable f can take on at most three values fir f and fr Apparently Pf fir Pf fr to ensure that Ef f and to ensure that Ef7f2 0392 we nd Pf fir Pf fr 52 2 r2 Then Pf f l 7 0392r2 and Chebyshev s Inequality becomes an equality barely 16 Random variable f takes the value 1 with probability p PA 0 with probability lip PA39 Then mean f Ef pl lip0 p and the variance of f is P391p2 17p3907p2 plip as claimed 17 For each ordering in which the list s ith item is marked we obtain iil equally likely orderings in which that ith item is unmarked by swapping the ith item with one of its iil lesser predecessors and all orderings are enumerated once apiece this way Thus the probability that the ith item is marked is li Therefore the expected number of marked items is H20 1l2 13 120 2359774 Had the number of items been a number N rather bigger than 20 the Harmonic Number HN would have been better approximated as described in the class notes on Some Inequalities 18 See the class notes about Derangements or our text for the facts about the number Dn of derangements of a set of n elements this is the number of permutations that leave no member of the set unmoved There we nd that Do 1 D1 0 D2 l and for n l 2 3 in turn Dn nDnil 21n 18a Pno one gets his hat back D1010 10D9 llO gt 10D910 Pjust one man gets his hat back If the number of men were N instead of 10 the inequality would go the same way for all even N gt 1 the opposite way for all odd N gt 0 Prof W Kahan Page 3 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am 18b PJust nine out of ten men get their hats back 0 it can t happen 18c For any i chosen in advance from the set 1 2 10 Example 7 explained why ProbabilityMan i gets his hat back l 10 For any two different i and j chosen in advance from that set ProbabilityMen i and j get their hats back 107210 l90 This differs from 1 100 which is what this probability would be if the events Man i gets his hat back and Man j gets his hat back were independent These events are correlated when one occurs it enhances the other s likelihood 18d Let fi l ifman i gets his hat back 0 otherwise and let f Eifi We already know from Example 7 that Probabilityfi l llO so that Efi llO and therefore f s expected value Ef l and there is a formula for f s variance V Ef2 772 To compute this we need to know that Efi2 Efi llO and from 18c that EfifJ l90 if i7 j Then Ef2E2ifi2 2iEfi22i2j iEfifj 1010 9090 2 whence variance V2il l 19 Let fk Pf k and ak Pf 2 k 2ka for every integer k 2 0 in particular a0 1 because we are told that f takes only nonnegative integer values Then we nd that EkZI ak 2121 2ka 2321 2116ij after the order of summation is reversed jzij39fj EU 20 This problem is essentially the same as the Monty Hall Three Door Puzzle Example 10 on p 265 of our text Discrete Mathematics anal its Applications 4th ed by KH Rosen 1999 McGrawHill In terms of coin and cups I have two choices only one of which is random The random choice answers the question To which of three cups will I point rst The nonrandom choice selects in advance one of two strategies Strategy 1 Uncover the cup to which I rst pointed Its probability of covering my coin is l3 which is not changed by the performer s knowledge which I do not share of which of the other two cups does not cover my coin When he lifts that cup he does not change what I shall receive Strategy 2 Uncover not the cup to which I rst pointed but the other cup still unlifted The probability that the cup to which I rst point does not cover my coin is 23 This probability is not changed by the performer s revelation of the other cup not covering my coin when he lifts it so 23 is also the probability that my coin will lie under the third cup the cup I will uncover Evidently strategy 2 is twice as likely as strategy 1 to recover my coin The sum of their probabilities l 3 23 l corresponds to a third strategy of the kind favored by historical gures like Alexander the Great at Gordium knock over both unlifted cups Prof W Kahan Page 4 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am 21 This hard exercise challenges the student to construct an accurate mathematical model for a complicated game It is complicated partly because it can terminate in two ways either in step i or in step ii and each way requires its own peculiar proof The rst proof treats values of the debt X that compell the game to terminate either in step ii or in step i after at most a predetermined nite number k of coin ips The second proof will treat debts X that prevent the game from terminating in step i allowing it to continue for arbitrarily many coin ips though with ever diminishing probability until it terminates in step ii If the holder of the coin initially Klaas owe a debt X to the nonholder initially Karel let 26X be the nonholder s eXpectation so 1726X is the coinholder s eXpectation Evidently ze0 0 and zel l both determined by step i of the game without any coin ip When 0 lt X S l2 the coinholder can eXpect to win the coin in step ii with probability 12 and end the game leaving nothing for the nonholder or else with probability 1 2 the debt will double and the game continue with the same coinholder consequently if 0 S X S 12 then 26X 02 262X2 262X2 is the nonholder s eXpectation and the coinholder s eXpectation is l2 2X2 On the other hand when 12 lt X lt 1 step i reverses the roles of coinholder and nonholder and replaces the debt X by 17X consequently if 12 lt X S 1 then 26X l 7 262lX2 T is the former nonholder s eXpectation The two equations T and T are functional equations from which we shall deduce by mathematical induction that 26X X whenever 0 S X S l but our process of deduction will work on only those values X for which the game can t run forever The game can terminate in step i only if X is an integer multiple of a power of 12 which case will be considered now Consider X m2k for nonnegative integers k and m S 2k since 0 S X S l Every coin ip that shows tails will replace X by either 2X or 217X both replacements will decrement k by l so at most k coin ips can occur after which the game must terminate in step i For just such values X m2k we shall use induction on k to prove the formula zem2k m2k We have already noted its validity when k 0 and m 0 and m l 20 Let our induction hypothesis be that the formula is valid for some k K 2 0 while 0 S m S 2K To verify the formula for k Kl we need eXamine just two cases If 0 S m S 2K then 0 S mZKJr1 S 12 and equation T plus the induction hypothesis implies zem2KH zem2K 2 mZKJr1 as claimed If 2K lt m S ZKH then 12 lt mZKJr1 S l and equation T instead of T implies zem2KH 17 ae2KLm2K2 mZKH because 0 s 2KLm lt 2K Therefore 26X X whenever X is an integer multiple of a power of 12 between 0 and l We could infer that Karel s eXpectation 26X X for all real values X between 0 and 1 if we proved that 26X is a monotone increasing function of X Such a proof is feasible but would suit students of Real Analysis Math 104 better than students of Discrete Math 55 besides it would reproduce a large fraction of the neXt proof which runs along lines that Lenstra seems to have intended judging by his hint However the neXt proof works for only those debts X that let the game run forever albeit with probability 0 Prof W Kahan Page 5 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am First let us model cointosses as a samplespace of in nitely many mutually exclusive outcomes H TH TTH TkilH in which TkilH stands for k coin ips of which the rst kil show tails and the last shows the head of Queen Beatrix The probability of TkilH is l2k because the coin is fair Note that all these probabilities add up to 2kgt0 l2k l leaving zero for the probability that the game will run forever because the Queen s head never shows up A Dutch guilder with no head is unfair and illegal so Klaas can t possibly have one To determine who will hold the coin for the k th ip let us represent the debt x as a twos complement binary fraction x 7x0 Ellgt0 xJ2J in which each bit xJ is either 0 or 1 but we disallow the possibility that all but nitely many of those bits are the same In other words we allow no binary representation to end with an in nite string of ones nor with an in nite string of zeros thus excluding values x that are integer multiple of a power of l2 this exclusion is tolerable because such values have already been handled by the previous proof Except for such values every other number x in the range 71 lt x lt 1 has a nontrivially nonterminating twos complement binary representation as the reader should be able to verify although the initial debt x lies in the narrower range 0 lt x lt l For example 13 0 01010101 in binary and 713 1 10101010 71 23 More generally x gt 0 when x0 0 and x lt 0 when x0 l in other words Signx 172x0 i1 as expected SignO won t occur Because x cannot be an integer multiple of a power of l 2 the same is true for its replacements 2x and 2lix in the course of the game Therefore the game cannot terminate in step i only the appearance of the Queen s head in step ii can end the game and then the coinholder who ipped the coin will retain it Our next task is to gure out how the bits of x determine who that coinholder will be To that end set X0 x so 0 lt X0 lt l and for k l 2 3 in turn de ne Xk thus If leGll lt l2 then set Xk 2Xk1 otherwise since Xk1 il2 when l2 ltle71lltl set Xk 2Xk717 SignXk71 Either way mathematical induction con rms that 71 lt Xk ixk Ejgtk xJ2j k lt l for all k gt 0 as follows The tested condition leill lt l2 is tantamount to xkil xk and if true ensures that lel lt l and SignXk 172xk Signinl Over ow could spoil these last equations only if x were an odd integer multiple of l2k but this possibility has been ruled out If the alternative condition le71l gt l2 tantamount to xk1 xk is true it ensures that 0 lt lel lt l and SignXk isignXk1 Over ow could spoil this last equation only if x were an odd integer multiple of l2k Apparently x le2l is the debt owed by the coin holder to the nonholder immediately before the kth ip and SignXk reverses just when the coin changes hands in step i Immediately after the kth coin ip if it shows tails Xk is the signed debt Klaas owes Karel positive if Klaas owes lel to Karel negative if Karel owes lel to Klaas Here is a summary of how the signed debt Xk correlates with the game 0 Initially Klaas who holds the coin owes Karel a debt of x Xo where 0 lt x lt l Prof W Kahan Page 6 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am i After k7l coin ips the debt stands at X leill if inl gt 0 Klaas owes it to Karel and holds the coin but if inl lt 0 then Karel owes X to Klaas and holds the coin If now X lt 12 set Xk 2Xk1 so that X lelZ Otherwise when l2 lt X lt l the coin must change hands and the debt change from X to 17X lelZ in the opposite direction where now SignXk 7SignXk1 The signed debt Xk 2 must still be nonzero because it is never an integer multiple of a power of 12 ii The coinholder is now Klaas if Xk 0 Karel if Xk l The coinholder who owes the nonholder lelZ ips the coin If the queen s head shows after this k th ip the coinholder retains the coin and ends the game Otherwise the debt is doubled k is incremented by l and the game continues from step i above If the kth coin ip ends the game an outcome TkilH with probability 12k the game ends with Klaas holding the coin if Xk0 Karel if Xk 1 Therefore Karel s eXpectation is 26X 2kgt0 Xk2k X as claimed 22 The probability generating function of the random variable f is gX 2120 fk39Xk wherein fk Pf k 2 0 Since f takes only nonnegative integer values gl EkZO fk l The assumption that the radius of convergence of g is larger than 1 is essential because otherwise for instance if fk lklk2 the eXpected value Ef g39l could be 00 Thus we can assume that the eXpected value 7 Ef EkZO kfk g39l is nite The variance V0 EH2 1302 7 72 zkzo kz39fk 7 gm2 zkzo k39k 139fk t zkzo k39fk g3912 gquot1 t 90 g3912 23 When Lenstra wrote maps the nth variable to n Ithink he meant maps the nth element of h mh mmh mmmh to n Thus Pf n q 1 p The probability generating function of f is gX Eng qn 1 39p39Xn pXl 7 qX The eXpected value 7 Ef g39l pl7q pq1412 lp because l7q p The variance of f is V gquot1 g391g3912 2pq17q2 2pc1217q3 1p 71132 qpz 24 Lenstra s notation for this problem has too many subscripts so let s simplify it Let f g and h f g be random variables that take eXclusively nonnegative integer values and let their respective probability generating functions be FX EkZO fk39Xk GX EkZO gkXk and HX Ekzo hk39Xk Provided f and g are independent Prof W Kahan Page 7 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am hk 1 h1lt Pfgk EosjskPfj amp gkj EOSJSk Pf jPg kij because f and g are independent zosjgk fj 39gkj39 which is the same as the coe icient of xk in FX39GX Emzo fm39Xm 21120 gn39Xn ZmZO 21120 fm39gn39Xm11 Ekzo Xk39zosjsk fj 39gkij Therefore Hx FxGx though to believe this you may have to take for granted in nite series manipulations whose validity is established in advanced Calculus courses 25 As in Exercise 17 the sample space S is the set of all lists formed by permuting a given set of N distinct numbers N 20 Each such list is as likely as any other to be chosen at random The rst element in each list is marked and so is its every element that exceeds all its predecessors in the list but no other elements are marked For any positive integer i S N let A denote the subset of lists whose ith element is among the marked elements Exercise 17 s solution explained why PAi AiS li Note that every AimAJ is nonempty 25a For every positive integer K S N and for every subset of K integers i j k drawn from the set 1 2 3 N we wish to show that PAimAJm mAk PAiPAJ PAk The formula is trivially true for K l and the formula is true for K N because only one list lies in AlmAzmmAN so its probability PAlmA2rmAN lN PA1PA2PAN thanks to Exercise 17 Let s prove the formula for every K between 1 and N by induction Suppose the formula is true for some K between 1 and N71 inclusive What about Kl Let the subset of Kl integers be i j k m there is no loss of generality in assuming them so ordered that i ltj lt lt k lt m since doing so changes neither AimAJm mAkmAm nor PAiPAJ PAkPAm The lists in Aim mAkmAm can now be partitioned into two subsets the lists in AimAJm mAkmAm and the rest in Aim mAkmAm iAi From each list in AimAJm mAkmAm we may generate iil lists in Aim mAkmAm iAi by swapping the marked ith item in the former list with one of its iil lesser predecessors doing so generates every list in AimmAkmAm just once so AjmmAkmAm iAimAjmmAkmAm This implies PAimAJm mAkmAm PAJm mAkmAmyi PAiPAjm mAkmAm since all the lists are equally likely Finally invoke the induction hypothesis upon the K integers j k m to infer PAimAJm mAkmAm PAiPAJ PAkPAm as claimed 25b The number of marked elements in a list is a random variable f f1 f2 fN where fi 1 just when the randomly selected list s ith element exceeds all its predecessors in the list otherwise 0 In other words 1 just for the lists that lie in A so Pfi l li Moreover we have just seen in 25a that the random variables are independent Therefore variance Vf Vf1 Vf2 VfN Now fi2 0 or 1 Efi Pfi l li and Vfi Eu 7 13092 M 7 M2 so Vf 1 12 13 1N7 1 14 19 1N2 2 2001576 when N 20 Prof W Kahan Page 8 Math 55 Solutions to Problems in HW Lenstra s Notes July 9 1999 738 am 25c Exercise 24 showed that the probability generating function of a sum of independent nonnegative integervalued random variables is the product of their individual probability generating functions The probability generating function for is lili zi so the probability generating function for their sum f must be zlz2z NilzN as claimed 26a This problem resembles Lenstra s Example 8 After buying one box the probability that any subsequent purchase will contain a letter different from the rst s is p 56 analogous to the probability of hitting a target The expected number of additional purchased boxes like the expected number of shots until the rst hit is lp 65 Therefore the total number of purchased boxes expected before two different letters are acquired is l 65 26b Let pJ be the probability that any purchased box will contain a letter di erent from j previously chosen letters Evidently pJ l ij6 Let random variable nJ be the number of boxes purchased to get a letter di erent from j previously chosen letters As before we nd Enj lpJ 667j No claim is made yet that these random variables nJ are independent Still the number of boxes purchased to get at least one instance of every letter is a random variable n Slog 5 nJ because whatever the order in which letters appear the sequence of purchases can be broken into batches each a batch of purchases of which the last acquired a letter not seen before The problem s solution is En Slog 5 Enj Slog 5 667j 14710 26c As in Exercise 23 when 0 S j S 5 we nd the probability generating function for nJ to be NJx EkZI pJlipJk 1xk lij6xl ijx6 Moreover each nj is independent ofthe others because rst it is unchanged by changes among the prior set of j letters in boxes already purchased and second because nj does not depend upon which new letter turns up so long as it is different from the prior set of j Thanks to Exercise 24 the probability generating function for FEOSJgnj is Nx139losj 5 NJx 5165x6ngj351 ijx6 27 See the class notes on Derangements to nd out about Dn the number of derangements of n objects permutations that leave no object unmoved and about the number Fuk IleDmk of permutations of n objects that leave exactly k unspeci ed objects unmoved Those notes explain why Dn nDIH fln nlEOSJSn flyj 27a Pfn k Fukn lkEOSJltJlk flyj for 0 S k S n 271 gnz 2120 zkkuxogJgni flyj zogkgnzogjgni zkkuenij set m jk EongHEnggmzkkxyelwrkmik ZOSmSnaiummx so 14 39En 2 0 gnZ39tn 21120 20Smlt41tn tn139zilmml 2mzo 212m tn th39Z1mml Emzotmzilfnm because 212m tnitn telescopes exptzil as claimed Prof W Kahan Page 9 Mathematics 55 Spring 2005 Lecture 10 Wednesday 292005 Euclidean Algorithm and Congruence Announcement Midterm exam in class next Wednesday 1 supply paper Review next Tuesday in discussion section Today Congruences7 congruence equations7 Chinese Remainder Theorem State ment of Fermat7s little Theorem Problem Given a7 b7 how to solve the congruence equation ax E b mod m This should remind us of 9th grade algebra to solve ax b7 we divide through by a to get z ba ba l Whats the analogue here If we had a number a such that aa E 1 mod m then x ab would be a solution7 for ax aab7 and aa E 1 mod m implies by one of our theorems that aab E b mod m Such a number a is called a multiplicative inverse ofa modulo in Of course7 there are other solutions if z is a solution then so is z 1 km for any integer k that is7 if z E y mod m then y is also a solution Reversing the reasoning7 we see that ifax E b mod m then x E ab mod m Thus any two solutions must be congruent modulo m the solution is unique modulo in But when does it exist We know that there exist integers 57 t such that gcda7 m satm lf a7 m are relatively prime7 that is7 if gcda7 m 17 then we get 1 satm This says that sa E 1 mod m7 so a s is the desired multiplicative inverse of a On the other hand7 if gcdam c is 31 1 then c divides both am7 so c1ax and c1771 so c must divide b in order for the equation to be solvable Upshot lf a7 m are relatively prime then i a has a multiplicative inverse modulo m7 ii for any b7 there is an integer solution x ofthe congruence equation ax E b mod m7 and iii Any two solutions Ly are congruent modulo m Chinese Remainder Problem Given nitely many positive integers 77117712 7mN7 and given integers b17 7bN7 nd an integer z satisfying z E bj mod 771 for all j E 17 27 7N simultaneously Eccample Find z congruent to 1 modulo 27 congruent to 2 modulo 37 and congruent to 4 modulo 7 We check that z 11 works I didnt explain how z could be found Eccample Find z congruent to 1 modulo 8 and to 2 modulo 12 This is impossible the rst congruence requires z to be odd7 while the second requires it to be even Chinese Remainder Theorem Let N 2 27 and let m1 7mN E N be given If the numbers in are pairwise relatively prime then for any numbers b i a solution x exists7 ii any two solutions are congruent modulo M where M is the product M 77117712 39 39 39 mN iii if z is a solution7 and ify E z mod M7 then y is also a solution 1 Here pairwise relatively prime means that no two have any positive common divisors except of course 1 The main new element here is that we have N equations for a single unkown x Conclusion iii is obvious Proof of ii Suppose that my are solutions and let 2 ziy Then 2 E 0 mod m for all j 6 12 N that is each m divides 2 Because the m are pairwise relatively prime this implies that their product M also divides z A detailed proof was given in class Thus z 7y kM for some integer k that is z E y mod M Err ample 4 12 and 6112 yet 4 6 24 does not divide 12 The above reasoning doesn7t apply since 4 6 are not relatively prime Proof of i Here7s a method that gives a formula for a solution then part iii tells us all other solutions For each k de ne M m1m2mN Mk 7 mk mk That is Mk is the product of all the m7 except Note mkle whenever j 74 k 1 We seek a solution in the special form 01M102M2CNMN 2 Here the 07 are new unknown integers Consider any index k E 1 2 N For any coef cients 07 clMl CgMZ CNMN E ckMk mod mk This holds whenever j 74 k by Thus in order to solve the original equation for x we need to solve Mkck E bk mod mk for each k 6 12 N Here the mk are given Mk is de ned in terms of these and bk is likewise given while each ck is an unknown Now we7re in clover We have N linear congruence equations each with a different unknown quantity ck As we learned in the rst part of the lecture each of these can be solved provided that Mkmk are relatively prime for each k Equivalently we need Mk m1m2mk1mk1mN and mk to be relatively prime for each index k This holds by our original hypothesis For any prime factor p of mk is by hypoth esis not a prime factor of any 771 for j 74 k By Lemma 2 on page 183 of our text this means that p doesn7t divide m1m2mk1mk1mN Thus a solution exists and in fact can be found in the special form D Our last topic is Fermat7s Little Theorem Let p be any prime7 and let a E Z If p does not divide a then 11 1 E 1 mod p Moreover a E a mod p for any integer a 1 I hope to return to this to give a proof later in the course There are many proofs See Exercise 17 of 26 in Rosen for one see Math 113 for another We7ll discuss a cute proof by induction7 using a property of binomial coef cients7 once we7ve studied those topics This theorem makes remarkable statements about really big numbers Example 6 100 E 1 mod 1017 since 101 is prime and 6 is certainly not divisible by 101 As we7ll discuss brie y next time7 its one of the crucial ingredients in the widely used RSA public key cryptography protocol Math 55 Euclid s GCD Algorithm May 10 1999 615 pm Given two positive integers a 2 b gt 0 we seek their Greatest Common Divisor GCD which is the biggest integer d that divides both a and b leaving no remainder Ordinary long division computes a positive integer quotient q Labi and leaves a remainder r a 7 qb that satis es 0 S r lt b Clearly every divisor of both a and b divides r too and conversely every divisor of both b and r divides a qb r too therefore GCDa b GCDb r But the pair b r is smaller than the pair a b in the sense that b S a and r lt b This leads to an algorithm Euclid s GCD Algorithm Given integers a 2 b gt 0 set r0 a and r1 b and perform successive long divisions getting for j l 2 3 n in turn until rn 0 quotients qj and remainders rj that satisfy rjq qjrj rJH with 0 S rJH lt rj Here at step j we divide rjq by rj to get quotient qj and remainder rJH stopping when a remainder rn 0 At that point qn gt 1 can you see why The algorithm stops because this decreasing sequence of n1 positive integers r0 a 2 r1 b gt r2 gt gt r1171 gt rn gt rn 0 cannot have n gt b Then GCDa b rn because as explained in the rst paragraph GCDa b GCDrO r1 GCDrl r2 GCDrIH r1 GCDrn rn rn The quotients qJ appear to play no important role in the foregoing algorithm but appearances can mislead By translating the algorithm s recurrence into matrix language we nd uses for qj rj l iq 0Sr ltrandr 0so In 0 1 0 1 0 1 0 1 0 1 r0 JH J H ioj i 1 qn 1 41H 1 41H 1 qZ 1 ql r1 0 1 0 1 0 1 0 1 0 1 Now set row to obta1n two B A i 1 iqr i 1 iqnilj i 1 iqnizl i 1 iqzl i 1 iqu integers A and B not both positive satisfying GCDa b rn 1 0 In B A Ba Ab 0 We have just found that GCDa b is a linear combination of a and b with integer coef cients thus proving the following Cf text p 137 and p 201 ex 58 Set H j rst then for j l 2 3 n inturn con rm that r1 0 1 r14 with r1 1 rj Theorem 1 As A and B run independently through all integers the expression Ba Ab runs through a set of integers among which the smallest positive integer is GCDa b Ba Ab Iiard Exerciie Running A and B through all integers is unnecessary Theorem 1 remains true after restrictions lAl lt a and Bi S b S a are imposed why Can you prove lAl lt aGCDa b and Bi S bGCDa b 7 See below There are two ways to compute A and B The easiest is to evaluate fromlefttoright the matrix product de ning B A after all the qj s have been computed this gives rise to a recurrence sn l sIH 7qn1 for j n72 n73 2 l in turn sJ j27qjsj1 Finally A s1 and B s2 Another way to compute them is to evaluate fromrighttoleft the matrix product de ning row B A simultaneously with the computation of the qj s Prof W Kahan Page 1 The r n nm A xxvna quotAnnl ML 17mm Ah Anlmr A n A Math 55 Euclid s GCD Algorithm May 10 1999 615 pm BO A001 B1 A1 1 7qu for j 2 3 nil inturn B Aj 1 iqj 14 14 jrl jrl Finally B A IBn71 Aml Note that qn never gures in the computation of A and B Whichever way be chosen to compute A B and GCDa b Ba Ab the algorithm is called the Extended Euclidean Algorithm and has important applications Here is one of them Exercise Given integers a c and b gt 0 when does a39XE 0 mod b have integer solutions x 7 Here p a q mod b is pronounced p is congruent to q mod b and means that piq is divisible by b Let d GCDa b Exhibit all d noncongruent solutions x if and only if d divides c otherwise prove no solution x exists Continued Fractions If d GCDa b then adbd exhibits ab in lowest terms but is not the only unique encoding of rational numbers By substituting rJ71rj qJ lrjrJH repeatedly for j l 2 n in turn we obtain a Terminating Continued Fraction q2 T 13 T 1 qn71 a This is the continued fraction for the rational number ab Here ql 2 1 because a 2 b gt 0 in l fact every qJ 2 l and the last qr1 2 2 to ensure that the encoding of each rational ab gt 1 by a nite sequence q1 q2 q3 qIH qnil of positive integers be unique Euclid s algorithm converts a rational number given as a ratio of integers into its continued fraction how do we get back The obvious way evaluates the continued fraction bottomup Rn1 0 Rn l for j n nil n72 2 l in turn qu qjRj RJH nally ab RORl in lowest terms Exercise Con rm that every integer rjGCDa b Translating the bottomup evaluation of the continued fraction into matrix terms yields rst RH qj 1 R1 then ql 1 1 qnel 1 J n 1 This last expression offers RJ10RJ1 1010 10100 two interesting opportunities One is a way to evaluate the continued fraction topdown 1101 111 q1 for j 2 3 n in turn hj l hi4 nally R0 1 11quot go 0 g1 1 gj gH gj2 1 R1 gn This topdown evaluation turns out to be a good way to evaluate endless continued fractions that encode nonrational numbers successive ratios hjgj can be shown to converge alternatingly Exercise The endless continued fraction in which every qj 1 represents u l V52 can you see why Another opportunity offered by that long matrix product is a clear proof of Lame 3 Theorem To compute d GCDa b for a 2 b gt 0 Euclid s algorithm needs n S llnbdlnu divisions Exercise Prove it by showing every Rj is at least as big as if every qj 1 except qI1 2 so R1 2 fn a Fibonacci number and fr un1 7 fluquot1u lu 2 NH Cf text p 206 R0 1 Prof W Kahan Page 2 Math 55 Euclid s GCD Algorithm May 10 1999 615 pm Exercises Suppose given integers M gt 1 and N gt 1 have GCDM N l nM imN for some integers m and n whose signs are not yet determined 1 Show why m and n must have the same nonzero sign Henceforth we can assume that n gt 0 and m gt 0 otherwise swap M and N etc 2 What is GCDm n 3 Show how to replace m and n respectively by E and H satisfying 0ltmltM 0ltnltN and l nMimN nMimN Henceforth we can assume that 0 lt m lt M and 0 lt n lt N and nM 7 mN l T 4 Exhibit instances of pairs M N and m n which satisfy these assumptions T but for which M gt N in one instance and M lt N in another 5 Given that the pairs M N and m n satisfy T show how to obtain a pair 5 E that satis es 0 lt E lt M and 0 lt H lt N and EN inM l as if M and N had been swapped 6 Show why T implies that MiN and min have the same nonzero signs unless m l n Hint mnMiN71 minMN1 Prof W Kahan Page 3 Math 55 Computing Xn March 20 1999 518 pm This note shows how a nontrivial but still simple algorithm npow is proved correct Given X and n how quickly can Xn be computed We assume that n is an integer and that X is a real number or a matriX or a polynomial for which multiplication takes so much longer than everything else in our algorithm that only the number of such multiplications matters In the algorithm that follows Matrix or Polynomial can be substituted for Real whereas a formula like Xn eXpnlnX would not be practical for polynomials X As it happens no simple algorithm is known that computes Km for every integer n 2 0 in the least possible number of multiplications and no divisions for that n However here is an algorithm that is optimal in this regard for lnl lt 15 and otherwise not much worse than optimal Real Function npowReal x Integer n quotramnszg Real z Begin If n lt O Return reciprocal npowx n and Exit If n O Return Reall and Exit While n iseven Do xx2 nn2 z x Do n floorn2 If n O Return z and Exit x x2 If n is odd z xz forever End npow Let s follow the progress of npow X 15 as each variable changes its value n 15 x X Arguments are copied passedby value Z X n 7 x X2 z X3 2 Real multiplications n 3 x X4 z X7 2 more Real multiplications n l x X8 z X15 2 more Realmultiplications n O return X15 in 6 Real multiplications But there is afaster way X15 X22X2X22X in 5 Real multiplications Anyway the algorithm s number of multiplications must grow like Qlog2lnl as n 7gt 00 since k multiplications are insufficient to compute Xn if n gt 2k can you see why How can npow be proved correct At best we can try to prove that this algorithm ful ls some eXpectation eXpressed as a set of specifications Here a question arises reminiscent of the question raised by the Roman satirist Juvenal ca 60 140 AD Sed quis custodiet z39psos Custodes But who is to watch the Watchers Many a program has been proved correctly to implement incorrect specifications This is no eXcuse for shirking such proofs rather it is a warning that first our specifications also have to be proved correct instead of mere wishful thinking perhaps inconsistent and secondly good reasons eXist to test programs even if tests can prove no more than that something is wrong Prof W Kahan Page 1 The r n nm an xxvna ranfar ML 17mm Al Anlmr A n A Math 55 Computing Xn March 20 1999 518 pm The best known speci cations for npow x n X are recursive XO l X XX 1 for all integers n gt 0 The rst speci cation for n 0 is a convention valid for all X including X 0 and X oo here l is the familiar number if X is a number the identity matriX of the same dimension as X if it is a square matriX and the constant polynomial 1 if X is a polynomial in variables not mentioned The second speci cation leaves X unde ned for integers n lt 0 by relaXing the constraint n gt 0 we can deduce by induction that X X 1 X75711 for integers n lt 0 provided X is a nite nonzero scalar or an invertible nonsingular matriX Presumably reciprocal 2 will return 12 or 2 1 if it eXists and otherwise an 00 0 1 or a NaN NotaNumber or something like it or in desperation an errormessage These contentious details will be left to another occasion together with the roundoffrelated reasons for preferring reciprocal npowx n to npowreciprocal x n The rst step in our proof of the correctness of npow is the conversion of its speci cations to XO l 0 X X 1 for n lt 0 71 X XX 1 for odd n gt 0 l X X2 2 for even n 2 0 2 The formal proof of that last specification 2 eXercises both multiplication s associativity and mathematical induction it is left to the diligent reader Con rming formally that if n is odd then oorn2 nil2 is left to the reader too NeXt we merge speci cations 1 and 2 into a single recursive rule for the computation of y zX for nonnegative integers n namely if n is odd then y zXX2 Oor 2 else y zX2 Oor 2 whose formal proof is left again to the reader Finally to prove the correctness of npow we interpolate comments into its teXt Real Function npowReal x Integer n invokedto return Y XN Real z Begin having copied the arguments XX and nN If n lt O Return reciprocal npowx n and Exit If n O Return Reall and Exit Specs 71 and 0 have been met Henceforth Ngt0 The neXt loop invokes spec 2 repeatedly to keep Y XNX for XX2 if nN2 While n iseven Do xx2 nn2 Now YXN foranew XX andanewreducedodd Nngt0 and z x z X for which we shall return YXNzX2N 12 The neXt loop starts with Z z Nngt0 XX and Y ZX2 OorN2 Do n floornZ New n oorN2ltN If n O Return z and Exit iwaas l x x2 else ngt0 andnew XX2 so YZX If n is odd z zx new ZZ39X39 else ifn isevenleave ZZ Now Y 01dzX2 00rN2gtnewzx2 00rW2gt This formula for Y is Loop Invariant forever End npow which terminates because 0ltnltN can t repeat forever Prof W Kahan Page 2 Math 55 The Law of Large Numbers May 29 1999 710 am The Law of Large Numbers says roughly this The probability distribution of practically any random variable can be determined to any desired degree of accuracy as nearly certainly as desired by sampling that random variable independently and often enough First this note applies Chebyshev s Inequality to justify the Law of Large Numbers in a typical special case NeXt comes a description of the Central Limit Theorem which is proved valid in a very special case Sometimes this Theorem is confused with the Law of Large Numbers both ideas are important for most practical applications of probability Consider a random variable X distributed over a given finite population of individuals i or sample space of outcomes i Actually X is a function that takes the value Xi at i which will occur or be chosen at random with probability probi The simplest nontrivial random variable is just Xi probi Often probi is the same for all individuals i but we shall not assume this we do take for granted as usual that every probi 2 0 and that Eiprobi l More generally the probability that any preassigned subset 5 of the population will include a notyetspecifred individual chosen at random from the whole population is 24 in probi The Mean Average or Expected value of X over the whole space is denoted in this note by PEX EiprobiXi 2X ProbabilityX XX The last sum is over all values X Xi that X takes in the given population This note concerns the estimation of PEX given function X without knowing those probabilities in advance To know the probability distribution of X is to know ProbabilityX X for every number X or more usefully to know ProbabilityX S X S XA for every X and A 2 0 A way to estimate this latter probability given X and A is to de ne another random variable y thus yi 1 if X S Xi SXA otherwise yi 0 Then PEy ProbabilityX S X S XA can you see why This is why we wish to know how to estimate PE in general not merely for one random variable X In other words PE is a functional a function whose eXplicit argument is a function and whose implicit argument is a population or sample space PE maps functions de ned over populations to numbers PE is a linear functional in the following sense If X and y are two random variables over a population and if LL and B are constants each taking just one value over the population then rZEGL39X By uPEX BPEy can you see why More generally however for an arbitrary function fX y we almost always find that fX y i fPEX PEy This is why the estimation of E can be technically challenging Random variables X and y are called Statistically Independent or just Independent if ProbabilityX X and y Y ProbabilityX XProbabilityy Y for all constants X and Y in which case PEXy PEXPEy can you see why But when X and y are not independent PEXy 7 XPEy equals something called the covariance of X and y as we shall see later Thus multiplication of random variables is quite different from addition because PEXy PEXPEy regardless of independence Whether random variables are independent is always important though sometimes difficult to ascertain Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm AT Anlmr A n A Math 55 The Law of Large Numbers May 29 1999 710 am Random Sampling Suppose we plan to select but not remove an individual to be called I from the given population This I will be a Random Sample if ProbabilityI i probi Similarly for another random sample J Then the two samples will be regarded as statistically independent if Probability I i and J j probiprobi The future tense is used here because the word random may be inappropriate to describe a sample J after it has been selected Moreover nobody knows how to choose samples that are perfectly random and independent although some pretty good approximations are known the art of systematic random sampling is a topic discussed in Statistics courses especially courses about the Design of Experiments The generation of good pseudo random numbers is treated in vol II of DE Knuth s The Art ofComputer Programming AddisonWesley For example tossing a coin has two outcomes heads and tails that are sampled ostensibly at random every time the coin is tossed however the outcomes can be both biased and correlated if the tosser repeats too accurately his motions for each toss A casting director chooses extras for a movie s crowd scene not by sampling them at random from whoever is available but rather by correlating her selections to ensure that the crowd looks more nearly representative of the population intended by the scriptwriter Japanese ower arrangements look random only if some artistry goes into their placement So random sampling is hypothetical if not mythical And to the extent that individuals can be sampled at random so can a random variable x we shall let X x1 denote the samplevalue of x obtained from individual I sampled at random We shall contemplate large numbers n of random samples X1 X2 X3 Xn of random variable x corresponding respectively to individuals 11 12 I3 In to be selected but not removed at random and independently from a population And then we shall compare several statistics x PEx the mean of x over the population with PEX where X X1 X2 X3 Xnn the samples mean and 0392 PEx 72 the variance of x over the population with 14382 where 82 XliX2 XTX2 XniX2n the samples variance Note that at least until the samples have been drawn each of X1 X2 X3 X is a random 1391 variable distributed the same way as x is Consequently X and 82 are random variables too but over a population of ntuples II 12 I3 In composed from the nfold Cartesian product of the given population with itself Until the samples have been drawn ProbabilityIl 12 I3 IIQ probIlprob12probI3probIn because the samples are independent It follows that each of X1 X2 X3 Xn is independent of all others why so PEXkXm PEXkPEXm PExPEx x 2 for l S k lt m S n But every Xk2 x2 generally differs from x 2 as we shall see Moreover random variables X and 82 are not generally independent of each other nor of the samplestobe Xk Let s digress for a moment to consider two random variables x and y that are not necessarily independent Analogous to x and 0392 are the statistics Prof W Kahan Page 2 Math 55 The Law of Large Numbers May 29 1999 710 am y PEy the mean of y over the given population and 172 PEy 7 W the variance of y over the population To these we add the statistic y PEX7Xy7y the covariance of X and y over the given population In the very special case that X and y are independent we nd that y PEXy 7Xy 7 xy a gagyea gy 0 In general 7 0 except by accident and it is possible to nd 7 0 even though X and y are not independent In all cases PEXy Xy y can you see why Moreover 72 S 52172 to see why consider the discriminant of a quadratic uy7y 7 X7X2 2 0 for all real LL About terminology Variances 0392 and 172 are the squares respectively of standard deviations 039 and 17 which are nonnegative by convention And here independent can mean Pairwise Independent because this note allows for ostensibly bizarre situations like when of three random variables X y and z every two are independent though those two determine the third Now the eXpected values of a few sample statistics can be computed for comparison with population statistics PEX 2k Xkn 2k Xkn 2k PEXn nXn X and 2EY72EY2 Ami Xi 7 MY Edi 2m Xi7 Xm7 n2 n392 0 n2 since Xk and Xm are independent if k i m 0392n Therefore as a random variable the samples mean Y has the same mean X as has X over the whole population But Y has a variance 0392n smaller than the population s variance 0392 which is NOT the same as the samples variance 82 though they are close enough to justify the Law of Large Numbers as we shall see later First we digress to Chebyshev s Inequality If a random variable X has mean X and standard deviation 039 then Probability lX 7 Xi 2 57 S 7 2 for every positive 7 lt l Proof Let 35 be that subset of the population s individuals i for which X 7Xl 2 57 Then 62 2am promoXi gt02 2 2M probiXi 2 2 EM promoom2 7 5273 Probability lX 7 a 2 57 Divide by 5212 to nish the proof Chebyshev s Inequality tends to be eXtremely pessimistic because Probability lX 7 Xi 2 57 is almost always very much tinier than 7 2 Without additional information about X this 7 2 cannot be replaced by something smaller because there are random variables X that satisfy Probability lX 7 Xi 2 57 7 2 for at least one 7 gt 0 For eXample suppose X takes only three values namely X i1 each with probability 7 22 and X 0 with probability 1 7 7 2 then X 0 039 7 and Probability lX 7Xl 2 57 7 2 eXactly Later we shall see how pessimistic Chebyshev s Inequality is for now it is adequate to prove Prof W Kahan Page 3 Math 55 The Law of Large Numbers May 29 1999 710 am The Law of Large Numbers If a random variable x has mean E and standard deviation 039 then given any two tiny positive tolerances LL and B choosing a big n gt GM2B will ensure that the samples mean Y of n independent random samples of x differs from the population s mean x by less than LL except with probability smaller than B Proof For any n gt GM2B set 7 5LLWn lt VB to infer that Probability liixl 2 LL lt B from Chebyshev s inequality because the standard deviation of Y is GWn End of proof The Law of Large Numbers is often misapplied For example consider a large number n of fair tosses ofa fair coin just as likely to come up Heads as Tails The expected number of each is n2 from which some people wrongly infer that the difference between the numbers of Heads and Tails is likely to be small and more likely as n increases If the coin has come up Heads rather more often then Tails for a while these people would bet that Tails are more likely to appear in the next several tosses Not so Even if the tosses are perfectly fair that difference can be proved almost certainly bigger than any big number chosen in advance while the ratio of the numbers of Heads and Tails is almost certain to differ from 1 by less than any tiny positive number chosen in advance provided the number n of tosses is chosen big enough in advance Choosing n in advance is obligatory lest the Law of Large Numbers as stated above be violated It is violated when n is chosen by drawing ever more samples until a tolerance is exceeded and stopping then No matter how unlikely this stopping event may be unless it is impossible it will surely occur at least once if Fate is tempted often enough Any application of the foregoing Law of Large Numbers to estimate the mean x of x uses an estimate of the variance 0392 of x to decide how big the sample size n should be but if x is not yet known where can an estimate of 0392 come from From the samples variance 82 Not exactly First until the samples have been drawn 82 is a random variable Second it is likely to somewhat underestimate 0392 in other words 82 is a statistically biased estimator of 0392 More precisely as shall be proved next 14382 1 7 ln0392 Lemma If independent random variables yJ all have mean PEyJ 0 and respective variances PEyJ2 172 then 14323 yj2 2J sz Proof 2E2j yj2 Edk 2 mp 2k 2 ykyj zj zEltyfgt 2k Zia 0 EJ rf Now set every yJ 4x3 except yk nilinx for any positive k S n to find that 2EnXk 7 m2 2Eyk Elan2 Hflt52 n713962 minlt52 Consequently n3PESZ E 2knxk inY2 2k AEnXk inY2 n2nil0392 Divide by n3 to conclude that PESZ l 7 ln392 as claimed above End of proof An initial batch of n samples could be drawn to provide an estimate SZl 7 ln of 0392 after which at least GM2B new samples would very likely estimate x adequately but these are almost always far too many new samples because Chebyshev s inequality is so pessimistic Prof W Kahan Page 4 Math 55 The Law of Large Numbers May 29 1999 710 am The Central Limit Theorem Summarized Its proof is difficult not for everybody It says something astonishing roughly this Practically regardless of how the random variable x is distributed there is one universal Normal Distribution by which the probability distribution of the samples mean Y comes to be approximated ever better as the number n of samples increases This Normal Distribution is characterized by a function 132 that increases smoothly from 137 0 through 130 12 to Igtoo l with a derivative D39z exp722227E The graph of 132 is its own re ection in its midpoint 1372 132 l And as z gt 00 iz approaches its limits ioo extremely rapidly for every 2 gt 0 it can be proved that 0 lt zz lz lt 1372 l 7 132 lt D39zz Tables of values of 132 are available widely especially in Statistics texts Physicists more often use the Error Function erfz 2ClgtZ27l Computer programs based upon continued fractions or other formulas can compute 132 as accurately as need be though not so quickly as we would like but it has been proved that no formula that invokes algebraic operations 7 and elementary transcendental functions like exp 1n tan arctan only finitely often can compute 132 exactly 132 and its derivative Clgt39z are plotted on the next page We say arandom variable u is Distributed Normally with mean E and variance v2 just when Probability u S U 13U7uv for all real U or equivalently Probability U lt u S U 13U7uv 7 13U7uv whenever U lt U It turns out that Y is distributed approximately Normally with mean x and variance 0392n Probability x s U z 13U7x039n and this approximation improves as n increases However out on the tails of the distribution where lY7xl6Wn exceeds 3 or 4 the approximation improves so slowly that its use to estimate tiny probabilities of extreme departures from the mean is imprudent An appropriate use for the Central Limit Theorem is to estimate where the values of Y are most likely to be found this estimate depends upon n x and 039 but is otherwise affected little by the way x is distributed For example let us estimate p3 Probability lY7xl lt 36Wn Chebyshev s inequality implies p3 gt 1 7 132 08888 but this underestimates p3 substantially when n is big in which case the Central Limit Theorem implies that p3 rs 133 7 1373 09973 More generally for k l 2 3 let yk be mutually independent random variables the probabihty of each is unaffected by whatever may be known about all others with respective means yk and standard deviations 17k and let y yl y2 y3 yn for some large n This y has mean y 1 2 y3 yn and variance 172 1712 1722 1732 17112 according to the Lemma above Provided maxlskSn 113172 gt 0 as n gt 00 the Central Limit Theorem says that y7y l7 is distributed ever more nearly Normally with mean 0 and variance 1 as n increases Again the approximation is best for central tendencies but remains relatively inaccurate out on the tails For proofs see W Feller s An Introduction to Probability Theory and its Applications vol II 2d ed 1971 Wiley it is heavy reading A comparatively elementary treatment of a special case appears in the following pages Prof W Kahan Page 5 Math 55 The Law of Large Numbers May 29 1999 710 am Graph of the Normal Distribution 132 and its Derivative D39z The Normal Distribution Phiz and its Derivative Phi39z i i i i i The DemoivreLaplace Limit Theorem Now we shall demonstrate the Central Limit Theorem s validity in the special case of a huge number n of fair and independent tosses of a fair coin This is de nitely not for everybody This case was discussed in 1718 by Abraham DeMoivre a Huguenot who had ed to England from France because Louis XIV revokedin 1685 the religious tolerance promulgated by HenrilV s Edict of Nantes in 1598 In 1812 DeMoivre s discussion was re ned by Pierre Simon Laplace whose name too is now attached to this demonstration Many texts and notes exhibit awed versions of this demonstration 1 hope this one isn t awed too Let random variable hn count how many heads will appear after n independent and fair tosses of a fair coin as likely probability 12 to come up heads as tails We already know that Probability hn k an2n where combinatorial coe icient an niki n7k for all integers k provided we accept the convention that nCk 0 whenever k lt 0 or k gt n Also known is that h has mean hn PEhn n2 and standard deviation vn W 143hn7hn2 V z see our text s Example 22 on pp 2812 To con rm the Central Limit Theorem we must prove that as n tends Prof W Kahan Page 6 Math 55 The Law of Large Numbers May 29 1999 710 am towards 00 the random variable un hn 7 h vn becomes distributed ever more nearly like a normal random variable with mean 0 and variance 1 A which means the approximation Probability U lt un S U rs CDU 7 CDU whenever U lt U becomes ever more accurate as 11 increases provided U and U are xed rst The function FnU Probability un S U Probability hn S hn vnU but h is an integer 7 Probability 11H 3 LE 7 vnUl 7 Probability un s LEn 7 vnU J 7 hnvn Fn LE vHUJ 7 Hum In other words FnU is for each n gt 0 a nondecreasing stepfunction of U determined by its values at regularly spaced discrete arguments U Umk k 7 hnvn for all integers k Since FnU 0 for all U lt 7n do you see why the set of all di erences FnU 7 FnU 7 lvn Probability U 7 lvn lt un S U 7 Probability LE 7 vnU J 7 1 lt 11H 3 LE 7 vnUl 7 Probability 11H 7 L n 7 vnUl nCkZn where integer k lhn vnUl determines Fn too by a telescoping sum FnU Ej20 FnU 7jvn 7 FnU 7 Olvn Thus our strategy is to deduce the approximation FnU rs CDU from a proof that the differenced approximation FnU 7 FnU 7 lvn rs CDU 7 CDU 7 lvn has high relative accuracy if n is big enough But as n gt 00 these differences tend to zero since lvn 2n gt 0 to remedy that we divide by lvn and nd that CDU 7 CDU 7 lvIQ lvIQ gt D39U gt 0 as n gt 00 This simpli es our strategy reducing our task to the proof that also for any xed U FnU 7 FnU 7 lvn lvn gt ltIgt39U as n gt 00 Recall that FnU 7 FnU 7 lvIQ nCkZn where integer k lhn vnUl For any xed U this integer k lhn vnUl ln UWn2l increases somewhat irregularly as n increases To attenuate that irregularity we de ne u k 7 hnvn 2ln UWn2l 7 n2n which is designedto satisfy k n uVn2 ln UWn2l with U 7 2n lt u S U Clearly u gt U as n gt 00 and now FnU 7 FnU 71v191v19 7 nCkx zn1 7 nlWhkln7k2n 7 n V n uWn2 n 7 uWn2 an Now is the time to invoke Stirling s Approximation n rs WZTEn nen proved in the class notes on Some Inequalities at three places after a lot of algebraic simpli cation we nd FnU 7 FnU 7 lvn lvn z 1 7 uWnuVE2 l 7 1121001 gt21 uWnuW2 Calculus classes teach that if t gt T as K gt too then 1 tKK gt expT eT which implies here that asin gt 00 1 7uxn1W2 gt exp7U22 1 7 1121001 W gt exp7U22 1 uxn1W2 gt expU22 and consequently as claimed above for any U xed in advance Prof W Kahan Page 7 v 7 L If ltIgt39tdvdt 7 L u7tltIgt39tdt ultDu D39u because dCD39tdt 7tltIgt39t and D397oo 137 0 and infer that 0 lt ltIgtu lt u7u exp7u227u so long as 7u gt 0 An analogous estimate can be obtained for FnU by observing that I1 1Ck 7 1 Ck1 l 7 21dnan and then 0 S 22iltk EOSJSi nCJ 2k 7 n Ejltk I1CJ kan whence Ejltk nCJ S ldn 7 2kan so long as k lt n2 Can you carry out the algebra Consequently so long as Wn gtgt 7u gt 0 Fnu 7 lvn S 1 uWn7u Fnu 7 Fnu 7 lvn lvn cs 1 uVnltDu7u This means that Fnu decays on its tail faster than u does until n becomes big compared with 7u2 Still 13u decays rapidly enough as u gt we that a rather large number n of samples are generally needed before the Central Limit Theorem can approximate the tail of the Normal Distribution with a tolerably tiny relative error It is a topic treated only in advanced texts on Probability and or Statistics Prof W Kahan Page 8 Math 55 The Law ofLarge Numbers Mayz9 19997 10am Graphsnf qgtu vs mu far 11 4 9 and 100 mu v mm m quot4 me w mm Page 9 Math 55 The Law of Large Numbers Mayz9 19997 10 am mu v mm mmnn meWKal39lan Fag Math 55 Fermat s Little Theorem March 1 1999 1015 am Choose an arbitrary prime number p and any integer z then F ermat s Little Theorem says zp E 2 mod p and if p does not divide 2 then 2V1 E 1 mod p This is Theorem 5 on p 145 ofthe text which proves the theorem on p 149 ex 14 17 by rst proving Wilson 3 Theorem pEl E pEl mod p What follows are two more direct proofs of Fermat s Little Theorem The rst was recommended by Prof Ken Ribet I First recall the Binomial Theorem x yp E Z r xk r ypik in which the combinatorial k E 0 coef cient E ppElpE2 39pEk2 pEk1k and observe that E 0 mod p for 0 lt k lt p Consequently x yp E xp yp mod p for all integers x and y We shall use this congruence to prove Fermat s Little Theorem by Mathematical Induction 7 Evidently the assertion zp E 2 mod p is true when 2 E 0 and when 2 E i1 If the assertion were ever false the smallest integer Z gt 1 for which it was false would have to exist though the assertion is true for 0 S 2 lt Z But then we could set x E ZEl lt Z and y E 1 lt Z whence xpExmodp and ypEymodp andthen nd ZpExypExpyp Exy EZ modp this would prove the assertion true for z E Z too contradicting the characterization of Z as the smallest integer for which the assertion was false Therefore the assertion can never be false for any positive integer z and the identity zp E E1pEzp propagates the assertion to negative integers con rming the theorem s rst congruence When 2 is not a multiple of prime p an integer 2 1 mod p exists multiplying the theorem s rst congruence by that inverse yields the second End of rst proof Second proof Suppose 0 lt k lt p and consider the multiples k 2k 3k pE1k evidently no two of these can be congruent mod p nor can any be congruent to 0 mod p Therefore these multiples must be congruent mod p to 1 2 3 pEl in some order The product of all these congruences implies kEH pE1 EpE1 mod p and since the prime p does not divide pEl we can nd its integer inverse mod p and multiply by it to conclude that kp 1 E 1 mod p which con rms the theorem s second congruence for all z E k mod p Multiply by z to con rm the rst congruence which holds also when 2 E 0 mod p End of second proof Fermat s Little Theorem is most often applied in the 2 1 E 1 mod p form For example if the congruence 2 quot1 E 1 mod n is dissatis ed when tested for some 2 and n then n is certainly not a prime even if its factors are unknown Unfortunately the converse is untrue that congruence can be satis ed by some 2 but not others when n is what is called a pseudoprime Worse in nitely many Carmichael Numbers n satisfy that congruence for all integers z for which GCDZ n E 1 though these nonprimes n are very rare Still as tests for nonprimes go this test is relatively cheap because modular exponentiation is so fast cf text p 163 ex 14 Fermat s Little Theorem justi es posting two integers n and e on your web site by which you can be sent an enciphered message that nobody else who intercepts it can read The sender rst encodes his message into an integer M lt n then encrypts it into C E M6 mod n and sends you C You decrypt M E Cd mod n by using your secret key d E e 1 mod pElqu where p and q are the two secret huge prime factors of n E pq and you have chosen e to satisfy GCDe VD14 E l Why does this work Unless le or qlM in which case extra argument is needed Mp 1 E l modp and Mq 1 E 1 mod q Then since de E l kpElqu for some integer k Cd E Mde E M1kPE1qE1 a M mod p and mod q Therefore Cd E M mod pq Cf text p 147 Prof W Kahan Page 1 The r n nm an xxvna quotAnn1 ML 17mm at Anlmr 1 n 1 Math 55 Discussion of two problems in the text Problem 14 l on page 34 Let variables w X y 2 run over the students in a class Let propositional function CX y stand for Students X and y have chatted It seems obvious that CX y ltgt Cy X Not so obvious is whether CX X is ever True The proposition to be formalized is There are two students in the class who have not chatted This proposition is ambiguous in English both meanings will be formalized in turn To keep eXpressions from over owing the line the abbreviation GX y ltx y A ax y will be used it is the proposition Students X and y are distinct and have not chatted The term X qty ensures that GX X be False regardless of CX X First meaning There are at least two students in the class who have not chatted turns into EIX Ely GX y the answer most likely intended Second meaning There are just two students in the class who have not chatted turns into 3X 3y VW VZ GX Y A GW Z gt W XAZ YVW YAZ X l It could just as well be written 3X 3y GX Y A VW VZ GW Z gt W XAZ YVW YAZ X l It cannot be written EHX Ely GX y which is always False because GX y ltgt Gy X In class on Thurs 28 Jan a student raised the interesting question Can this proposition be eXpressed with three quanti ers instead of four He olfered an eXpression like EIXEyGXyAVz Cz y H ZX but this proposition is True for a class with three students X Y Z in which only Y and Z have chatted with each other and Y has chatted with himself Any correct eXpression of the form EIX Ely GX y Vz PX y 2 in which P is a predicate with no quanti er would have to distinguish two classes each with four students A B X Y among others in which X has not chatted with Y In one class everyone eXcept X and Y has chatted with everyone else and the eXpression would have to be True in the other class A has not chatted with B just as X has not chatted with Y but otherwise everyone has chatted with with everyone else and the eXpression would have to be False But PX Y z is the same for all choices 2 in both classes Therefore no correct P without any quanti ers can be constructed The problem could be solved easily with two quanti ers if the variables ran not over individual students but over pairs of distinct students Thus our choice of Universe osz39scourse may sometimes determine whether our problem s solution will be simple or complicated Prof W Kahan February 3 1999 221 pm Math 55 Discussion of two problems in the text Problem 26 on page 20 For de niteness we consider compound logical propositions Lp q r of three logical variables The text explains that every such proposition has a Disjunctive Normal Form consisting of a disjunction of conjunctions of the variables or their negations In other words Lp q r ltgt c1 vc2vc3v cn in which every cJ is pj A qJ Arj and pJ is either p or p and qj is either q or q and r is either r or r The number n of terms cJ depends upon L This Disjunctive Normal Form intended by the text s author is obtained directly from the Truth Table of L as follows p q r c Lpqr T T pAqAr T F pAqA ur F T pqur F pA qu ur T T pAqAr F F pAqA r F T pqur F pA qA r For every instance of T in the column Lp q r select the corresponding conjunction in the 4 gt7 column c for inclusion in the disjunction For instance when Lp q r is p A q H r p Aq Hr ltgt pAqAr v p A qu ur v IpAqA Ir v p A qu ur exhibits Lp q r in its Disjunctive Normal Form When L is the trivial proposition False it has no conjunctions its Disjunctive Normal Form is False But this form is often inef cient it can require many conjunctions for simple propositions For example when L is the trivial proposition True it requires the disjunction of all eight conjunctions c A different Disjunctive Form DF can be de ned in a way not quite inconsistent with the wording in problem 26 It allows a conjunction cJ to omit some or all of the variables This DF of True is just itself this DF of pqur is itself instead of the disjunction of seven conjunctions c Unfortunately this DF is not unique see the text s Chapter 9 For instance p Aq Hr ltgt p AqAr v pA qu ur v p A Ir ltgt p AqAr v qu ur v upA ur What is the maximum number of conjunctions cJ that any Lp q r needs for this DF Answer Four Example p A q A r v p A q Ar v p A q A r v p A q A r Prof W Kahan February 3 1999 221 pm Math 55 Waiting for a Bus April 12 1999 1144 am How long can one expect to have to wait for a bus at a bus stop Common experience suggests that transit authorities about 39 J 39 and f 1 39 of service are optimistic Actually the public shares some of the responsibility for misinterpreting those reassurances in an overly optimistic way whenever traf c congestion and other contingencies introduce unavoidable variations in schedules Let w minutes be the intended waiting period between consecutive busses arrivals at a bus stop If busses adhered strictly to that intention a wouldbe passenger ignorant of their schedule who came to the bus stop at a randomly chosen moment would expect to wait for w 2 minutes until the next bus arrived This gure w 2 is the average waiting time computed by observing that coming at atime f w after the departure of the previous bus is as likely as coming at a time f w before the arrival of the next for 0 lt f lt l and the average of their two waiting times w7fw and f w is w2 for all f But something else happens if busses arrive at the stop somewhat irregularly Even if w is the average interval between bus arrivals the average waiting time for a bus will then exceed w2 This is obvious if busses get bunched up in convoys because then the average waiting time will be at least half the average time between arrivals of convoys instead of busses What follows explains what happens when arrival times vary less drastically Let w1 w2 w3 wj be possible intervals between arrivals of consecutive busses and let pJ be the probability or relative frequency of the occurence of wJ Of course pj 2 0 and EJ pJ l The expected average interval between consecutive busses is w 2J pjwj A wouldbe passenger who comes to the bus stop at random in an interval of width wJ must expect to wait wj2 minutes on average The probability of coming to the bus stop in an interval of width wJ is proportional to wJ and also to the probability pJ with which wJ occurs so the average waiting time for a random wouldbe passenger is W 2 2J pj wJ wj22j pjwj What comes next will prove that W2 gt w2 unless wJ wk whenever pj pk gt 0 This proof is traceable to Lagrange 0 S 2 Ek pjpkwj 7 wk2 2wW 7 w Fill in the yourself 7 7 2v2 where V2 2J pjwj 7 w2 is the Variance in the arrival times wJ their Standard Deviation is V Therefore W w V2w gt w Therefore the average waiting time W2 exceeds half the average time w between arrivals by relatively little unless some of the likelier intervals wJ are relatively rather di erent from the average w of all the wJ s Prof W Kahan Page 1 The r n nm an xxvna quotAnnl ML 17mm Al Anlmr A n A

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.