MATHEMATICS 152, FALL 2004METHODS OF DISCRETE MATHEMATICSOutline #10 (Sets and Probability)Last modified: November 10, 2004This follows very closely Apostol, Chapter 13, the course pack.Attachments and Supplements:• Notes that provide details of some of the examples.• The ”Bayesian Bible,” which presents some standard probability prob-lems in unusual contexts.• The Durango Bill Web pages with bridge and poker probabilities.• sets.exe and enum.exe, Windows programs available on the course Website.1. (This is preliminary material that Ap ostol takes for granted)Given two sets A and B and a universal set S, define union, intersection,complement, and difference. Illustrate your definitions with an examplewhere S consists of the integers 0 through 15, using the program sets.exe,and with an example where S is the set of points in a square region ofthe blackboard.2. • Show how to express the intersection and difference of A and B interms only of union and complement and illustrate the connectionusing the examples mentioned in the previous item.• State Apostol’s definition of a Boolean algebra and explain why theclosure requirements that he imposes are sufficient to prove closureunder difference and intersection. (Apostol, p.471)3. Define “finitely additive set function,” “finitely additive measure,” and“probability measure,” making it clear what additional requirements areimposed with each new definition.4. Prove that for a finitely additive set function,f(A ∪ B) = f(A) + f(B − A) = f(A) + f(B) − f(A ∩ B)and illustrate this theorem with a “Venn diagram” where S is the set ofpoints in a square region of the blackboard.Prove that for a finitely additive measure f ,• f(A ∪ B) <= f (A) + f(B)1• f(B − A) = f(B) − f(A) if A ⊆ B.• f(A) ≤ f(B) if A ⊆ B.5. Following the examples in Apostol, section 13.8, explain how to answerthe following questions:(a) What is the probability of getting exactly two heads when a faircoin for which P (h) =12is tossed three times?(b) What is the probability of getting a total of either 7 or 11 whentossing two ”unloaded” dice?6. Use induction to prove the following results about probability and count-ing. Both are so obvious that it takes a minute to realize that they canbe proved. The proof is basically the same in both cases.• If A1...Anare mutually exclusive events, the probability that anyone of them occurs is the sum of the probabilities for the individualevents. (This is equivalent to problem 4 on p. 473 of Apostol.)• Consider a set T of n-tuples of the form x1, x2, ..., xn. Suppose thereare k1distinct choices for x1, k2distinct choices for x2, and so forth.Prove that the numb er of elements of T is k1k2...kn.(Apostol, pp.482-483)7. Calculate the probability, when a pair of cards are drawn at randomfrom a single deck of cards, that at least one of them is a spade. LetA be the event that the first card drawn is a spade; let B be the eventthat the second card drawn(from 51 cards) is a spade. Show that youget the same answer,1534, by each of the following approaches. State inwords, and illustrate with a Venn diagram, the reasoning behind each ofthe four approaches.(a) P (A ∪ B) = 1 − P (A0∩ B0)(b) P (A ∪ B) = P (A) + P (B) − P (A ∩ B)(c) P ((A ∪ B) = P (A) + P (A0∩ B)(d) P ((A ∪ B) = P (A ∩ B0) + P (A0∩ B) + P (A ∩ B)In each of the next three items, refer to the four principles of countingas listed in the notes:1. Multiply to do sequential counting2. Divide to correct systematic overcounting3. Divide and conquer4. Subtract off special cases28. In the carnival game “Chuck-A-Luck,” you pick a number between 1 and6. Three fair dice are tossed, and you win if your chosen number appearson one or more dice.• Show that your probability of winning is less than 1/2.• Determine the probability that your chosen number will appear on0, 1, 2, or all 3 dice.• Show that if you pay 1 dollar to play the game and receive 2 dollarsfor each occurrence of your chosen number, then the game is fair.(Chuck-A-Luck is discussed in the notes.)9. Count the number of ways to get each of the following types of 5-cardpoker hands, using a deck of 52 cards with 4 cards of each of 13 ranks.• 4 of a kind(four cards of one rank, the fifth of a different rank)• a full house(three cards of one rank, two of another)• 3 of a kind(three cards of one rank, two others of different ranks)(Poker is discussed in Apostol, section 13.10, in the notes and on theattached Web page)10. • Count the number of bridge hands with 6 spades, 4 hearts, 2 dia-monds, and 1 club.• Count the number of bridge hands with 6-4-2-1 suit distribution (6cards in the longest suit, 4 in the second-longest, 2 in the third-longest)• Count the number of bridge hands with 4-4-3-2 or 4-3-3-3 suit dis-tribution, and show that the former has a higher probability by afactor of slightly more than 2.(Bridge is discussed in Apostol, section 13.10, in the notes and onthe attached Web page.)11. Define conditional probability and use sets.exe to show examples of howto calculate it. (Apostol, se ction 13.12)12. Use the formula for conditional probability to analyze the “bearded man”problem in the notes, the ”Paul at Lystra” problem (#1 in the BayesianBible) or a similar example of your own invention. It is very useful toarrange the data in a 2-by-2 grid.13. Use conditional probability to analyze the “math roommate” problem inthe notes. (This is very similar to Apostol’s Example 2 on p, 488, buttwo variant versions are also discussed in the notes.)14. Describe the “Monty Hall problem” and analyze it in terms of conditionalprobability. (Discussed in the notes and all over the Web. An alternativestory line is in #2 of the Bayesian Bible.)315. Explain how to solve the following problem, which is based on a truestory.Lisa purchases six Dunkin Munchkins, four plain and two chocolate. Shechooses three at random and puts them in a bag for her son Thomas.The other three go into a bag for her daughter Catherine.(a) How many ways are there for Lisa to select three of the six Munchkinsfor Thomas?(b) Show that the probability that Thomas’s bag has both of the choco-late Munchkins (event A2) is 0.2.(c) Show that the probability that each child has exactly one chocolateMunchkin (event A1)is 0.6. Explain why P (A1) + 2P (A2) = 1(d) Catherine reaches into her bag and extracts a Munchkin at random.It is a plain one (event B). Show