PROBLEMS IN PROBABILITY AND THE PIGEONHOLE PRINCIPLE Instructions: For the following project, you are encouraged to work in groups of up to four people. If you do work in a group, each group member is expected to participate equally. The problems in this project are well-known (and hopefully interesting) problems in probability theory. Instead of just asking for the answer to these counterintuitive questions, each part has smaller questions which will guide you to the answer to the larger problem. With this in mind, I will be upfront and state now that some questions will be worth a lot more than others (since some of the guiding questions just have an answer of "Yes" or "No," while others require a decent amount of thinking). However, I will try my hardest to be fair and will distribute points in a way such that all work will be rewarded appropriately. Most questions asked in this project require at least some additional work before pre- senting the answer. Please show all of your work to receive full credit. Correct answers with no work may receive no credit. Incorrect answers with partially correct work may receive partial credit. Also, make sure that you use notation and methods that have been either taught in class or discussed during the project. You are permitted to use outside sources such as the ACE Tutoring Center, your instruc- tor, etc. However, any resources you use must be listed at the end of this project. Failure to list your resources will be considered cheating and may result in a zero on the project for you and your group. Your group should read the statement at the end of this project before you begin working together. Failure to sign the statement at the end of this project may result in a zero on the project for you and your group. This project covers mostly material from Chapters 6 and 7 and is due on Thursday, April 28, 2022 at the start of class. You only need to submit one copy of the project per group. The Monty Hall Problem The information for the following discussion was found on Wikipedia under "The Monty Hall Problem." If you want to read more about this, please refer to the Wikipedia page or search it yourself to see what you might find out! The Monty Hall problem is a question in probability that was based on the television game show Let's Make A Deal, and the problem gets its name from the host of the show Monty Hall . Although the problem was originally posed and solved in 1975, it became famous due to appearing in a 1990 Parade magazine column named "Ask Marilyn." In this particular issue, Marilyn vos Savant answered the following question asked by a reader: Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car and behind each of the other two doors there is a goat. You pick a door, say door B. The host, who knows what's behind the doors, opens another door, say door A, which has a goat. He then asks you "Do you want to stay with door B or switch to door C instead?" Is it to your advantage to switch your choice? A B (A sketch of the game, and proof that I am not an artist) Upon hearing this problem, people initially assume that there is no advantage to switching doors. There are multiple ways to view the problem and come to this incorrect conclusion For example, each of the following lines of thought are incorrect: Perhaps one might think that, no matter what, you are choosing one door out of three doors, so there is a 1/3 probability of selecting the door with a car when you switch as well as a 1/3 probability of selecting the door with a car when you choose to stay with the door you selected initially. Perhaps you might think that after the host reveals a goat, then you have two doors and you are effectively choosing one door out of two doors and so there is a 1/2 probability of selecting the door if you switch and a 1/2 probability of selecting the door with a car if you choose to stay with the door you selected initially. In the Monty Hall Problem, we make two particularly important assumptions about the behavior of the host: The door the host reveals must contain a goat and cannot be the door that the con- testant has chosen. The host must always offer the contestant the chance to switch between the originally chosen door and the remaining closed door. 1. Without loss of generality, suppose that you initially choose door B. The host opens another door revealing that it contains a goat, He now offers to let you switch from door B to the other unopened door. In each of the following parts, determine whether you win or lose: (a) The car is behind door A and you choose to stay (b) The car is behind door A and you choose to switch. (c) The car is behind door B and you choose to stay. (d) The car is behind door B and you choose to switch. (e) The car is behind door C and you choose to stay (1) The car is behind door D and you choose to switch. 2. Given that you have chosen to stay with the door you chose initially (door B), what is the conditional probability that you win? 3. Given that you have chosen to switch to the other door that is not yet revealed, what is the conditional probability that you win? 4. So, should you switch or stay? Why? Marilyn vos Savant responded with the correct answer that one should always switch doors. On the website https://www.gpposner.com/vos_Savant.html you can see sev- eral responses to her answer. Despite being attacked by the media, Marilyn did not back down. Instead, she explained her reasoning and replied "When reality clashes so violently with intuition, people are shaken." Most of those who disagreed with her immediately saw that they were indeed incorrect, but several still refused to believe er solution for years to come. Rest assured, however, that her answer is correct. MATH-104 Finite Mathematics Project 2 Due: 04/29/22 Part II: The Birthday Problem Think back to the first day of class. While I was going over administrative stuff for the course, I handed out a piece of paper and asked for everyone's birthday (just the month and day - not names nor years). Despite our section having only 30 students, surprisingly it turned out that two people in the class had the same month and day of birth. At the time, this probably seemed odd and unlikely since there are only 366 possible birthdays (I always count February 29), so this size discrepancy may seem way to large. It turns out that this is actually not the casel In other words, it is actually unlikely for there to not be a pair of matched birthdays in a group of 30 people. We are now going to investigate why this is the case. Throughout the following problems, we will count February 29 and assume that there are 366 days in a year. We will also assume that a person is equally likely to be born on any day of the year, meaning each day has a probability of 36 to be a random person's birthday. These will be made for ease of computation. We will also come back and discuss why that doesn't change the computation much at the end of this part. For Problems 5 through 7. I recommend leaving everything in fractions. These questions are here to figure out an important pattern that will be used. I also recommend not multiplying things out for these parts - if you have 4 x 3, leave it as just that (don't simplify it to 12). I also recommend writing powers whenever relevant (so write 42 instead of 16). Before we study the main problem at hand, we will first look at the probability that no people in a room share a birthday. 5. Two people are in a room. What is the probability that the two of them do not share a birthday? 6. A third person walks into the room. (a) Assuming we knew that the two people in the room do not share a birthday, what is the probability that this new person does not share a birthday with either of the first two people? (b) In general, what is the probability that, in a room of three people, no two of them share a birthday? (Hint: In Part (a) of this problem, we already assumed that the two people in the room already didn't share a birthday, so this is not just the answer to Part (a) and so a modification will need to be made.) 7. A fourth person walks into the room. (a) Assuming the three people in the room already don't share a birthday, how likely is it that this new person doesn't share a birthday with any of the other people in the room? (b) In general, what is the probability that, in a room of four people, no two of them share a birthday? (Hint: Modify the hint from Problem 6 part (b) for the new number of people.) IF you are writing your answers as fractions, hopefully you are starting to see a pattern. Remember that, in the Section 6.4 and 6.5 lecture notes, we had a special notation for 10! products like 10 x 9 x 8 x 7 = 8. Write your answers to questions using the notation from Chapter 6. Using the pattern that you identified, what is the probability that two people in a room with k people in it do not share a birthday? 6! Finite Mathematics Due: 04/29/22 9. Using your general formula, what is the probability that two people in a room of 30 people do not share a birthday? (Compute the actual number for this problem. Round your answer to two decimal points.) (Most scientific calculators have the operations you will want to use under a button labeled PRB (or something similar). If you can't find this, I highly recommend using a calculator on the Internet for this computation (since you would otherwise have to type in at least 30 different numbers).) 10. (The Birthday Problem) In a room with 30 people, what is the probability that there is a pair of them that share a birthday? (Show your work, and also compute the actual number for this problem. Round your answer to two decimal points.) 11. In order to do these questions, we made a few assumptions to make life simpler. (a) The most impactful assumption that we made was that all 366 possible birthdays are equally likely. In reality, this is not the case. What is one reason for this? (b) Since not all days are equally likely, this implies that some days would have a higher chance of being someone's birthday than others. With this mind, if we ignored the assumption that we made that all birthdays are equally likely, would the odds of two people sharing a birthday increase or decrease? (c) With your answers to this Problem in mind, were we justified in making the as- sumptions that we did? Fun fact: With your general formula, you can actually show that you only need about 23 people in a room for there to be at least a 50% chance of two of them sharing birthday! See the Wikipedia page for more information. MATH-104 Finite Mathematics Project 2 Due: 04/29/22 Part III: The Pigeonhole Principle The Pigeonhole Principle can be stated as follows: Theorem (Pigeonhole Principle). Given n objects and k boxes, if we put each of then objects into one of the k boxes, if n >k then one of the boxes contains at least 2 objects. Casually put, if we put 11 pigeons into 10 holes, then there must be a hole with at least two pigeons in it. At a first glance, this should seem fairly obvious, but it turns out that this has some very interesting consequences. The following problems can be solved using the pigeonhole principle. In addition to answering the question asked, state what were your boxes (holes) and what were your objects (pigeons) 12. Morgan is dealt five cards from a standard 52 card deck of cards. What is the probability that he has at least two cards of the same suit? 13. Humans, on average, have about 100,000 follicles of hair on their head. Since this is an average, we should be able to safely assume that no human has more than 300,000 follicles of hair on their head. According to the recent census, New York City currently has a population of 8.4 million people, (a) Do two people in NYC have the same number of hairs on their heads? (b) Can you make this claim with absolute certainty about the city of Fargo? Why or why not? 14. Suppose that there are 400 students taking Calculus courses at NDSU this semester. (a) What is the probability that two of these students share a birthday? (b) What is the smallest number of people needed to always obtain this probability? Why? 15. Suppose we had 12 pigeons and 10 holes, and we put each pigeon in one of the holes Does the pigeonhole principle guarantee that there are two holes with two pigeons in them? Why or why not? PROBLEMS IN PROBABILITY AND THE PIGEONHOLE PRINCIPLE Instructions: For the following project, you are encouraged to work in groups of up to four people. If you do work in a group, each group member is expected to participate equally. The problems in this project are well-known (and hopefully interesting) problems in probability theory. Instead of just asking for the answer to these counterintuitive questions, each part has smaller questions which will guide you to the answer to the larger problem. With this in mind, I will be upfront and state now that some questions will be worth a lot more than others (since some of the guiding questions just have an answer of "Yes" or "No," while others require a decent amount of thinking). However, I will try my hardest to be fair and will distribute points in a way such that all work will be rewarded appropriately. Most questions asked in this project require at least some additional work before pre- senting the answer. Please show all of your work to receive full credit. Correct answers with no work may receive no credit. Incorrect answers with partially correct work may receive partial credit. Also, make sure that you use notation and methods that have been either taught in class or discussed during the project. You are permitted to use outside sources such as the ACE Tutoring Center, your instruc- tor, etc. However, any resources you use must be listed at the end of this project. Failure to list your resources will be considered cheating and may result in a zero on the project for you and your group. Your group should read the statement at the end of this project before you begin working together. Failure to sign the statement at the end of this project may result in a zero on the project for you and your group. This project covers mostly material from Chapters 6 and 7 and is due on Thursday, April 28, 2022 at the start of class. You only need to submit one copy of the project per group. The Monty Hall Problem The information for the following discussion was found on Wikipedia under "The Monty Hall Problem." If you want to read more about this, please refer to the Wikipedia page or search it yourself to see what you might find out! The Monty Hall problem is a question in probability that was based on the television game show Let's Make A Deal, and the problem gets its name from the host of the show Monty Hall . Although the problem was originally posed and solved in 1975, it became famous due to appearing in a 1990 Parade magazine column named "Ask Marilyn." In this particular issue, Marilyn vos Savant answered the following question asked by a reader: Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car and behind each of the other two doors there is a goat. You pick a door, say door B. The host, who knows what's behind the doors, opens another door, say door A, which has a goat. He then asks you "Do you want to stay with door B or switch to door C instead?" Is it to your advantage to switch your choice? A B (A sketch of the game, and proof that I am not an artist) Upon hearing this problem, people initially assume that there is no advantage to switching doors. There are multiple ways to view the problem and come to this incorrect conclusion For example, each of the following lines of thought are incorrect: Perhaps one might think that, no matter what, you are choosing one door out of three doors, so there is a 1/3 probability of selecting the door with a car when you switch as well as a 1/3 probability of selecting the door with a car when you choose to stay with the door you selected initially. Perhaps you might think that after the host reveals a goat, then you have two doors and you are effectively choosing one door out of two doors and so there is a 1/2 probability of selecting the door if you switch and a 1/2 probability of selecting the door with a car if you choose to stay with the door you selected initially. In the Monty Hall Problem, we make two particularly important assumptions about the behavior of the host: The door the host reveals must contain a goat and cannot be the door that the con- testant has chosen. The host must always offer the contestant the chance to switch between the originally chosen door and the remaining closed door. 1. Without loss of generality, suppose that you initially choose door B. The host opens another door revealing that it contains a goat, He now offers to let you switch from door B to the other unopened door. In each of the following parts, determine whether you win or lose: (a) The car is behind door A and you choose to stay (b) The car is behind door A and you choose to switch. (c) The car is behind door B and you choose to stay. (d) The car is behind door B and you choose to switch. (e) The car is behind door C and you choose to stay (1) The car is behind door D and you choose to switch. 2. Given that you have chosen to stay with the door you chose initially (door B), what is the conditional probability that you win? 3. Given that you have chosen to switch to the other door that is not yet revealed, what is the conditional probability that you win? 4. So, should you switch or stay? Why? Marilyn vos Savant responded with the correct answer that one should always switch doors. On the website https://www.gpposner.com/vos_Savant.html you can see sev- eral responses to her answer. Despite being attacked by the media, Marilyn did not back down. Instead, she explained her reasoning and replied "When reality clashes so violently with intuition, people are shaken." Most of those who disagreed with her immediately saw that they were indeed incorrect, but several still refused to believe er solution for years to come. Rest assured, however, that her answer is correct. MATH-104 Finite Mathematics Project 2 Due: 04/29/22 Part II: The Birthday Problem Think back to the first day of class. While I was going over administrative stuff for the course, I handed out a piece of paper and asked for everyone's birthday (just the month and day - not names nor years). Despite our section having only 30 students, surprisingly it turned out that two people in the class had the same month and day of birth. At the time, this probably seemed odd and unlikely since there are only 366 possible birthdays (I always count February 29), so this size discrepancy may seem way to large. It turns out that this is actually not the casel In other words, it is actually unlikely for there to not be a pair of matched birthdays in a group of 30 people. We are now going to investigate why this is the case. Throughout the following problems, we will count February 29 and assume that there are 366 days in a year. We will also assume that a person is equally likely to be born on any day of the year, meaning each day has a probability of 36 to be a random person's birthday. These will be made for ease of computation. We will also come back and discuss why that doesn't change the computation much at the end of this part. For Problems 5 through 7. I recommend leaving everything in fractions. These questions are here to figure out an important pattern that will be used. I also recommend not multiplying things out for these parts - if you have 4 x 3, leave it as just that (don't simplify it to 12). I also recommend writing powers whenever relevant (so write 42 instead of 16). Before we study the main problem at hand, we will first look at the probability that no people in a room share a birthday. 5. Two people are in a room. What is the probability that the two of them do not share a birthday? 6. A third person walks into the room. (a) Assuming we knew that the two people in the room do not share a birthday, what is the probability that this new person does not share a birthday with either of the first two people? (b) In general, what is the probability that, in a room of three people, no two of them share a birthday? (Hint: In Part (a) of this problem, we already assumed that the two people in the room already didn't share a birthday, so this is not just the answer to Part (a) and so a modification will need to be made.) 7. A fourth person walks into the room. (a) Assuming the three people in the room already don't share a birthday, how likely is it that this new person doesn't share a birthday with any of the other people in the room? (b) In general, what is the probability that, in a room of four people, no two of them share a birthday? (Hint: Modify the hint from Problem 6 part (b) for the new number of people.) IF you are writing your answers as fractions, hopefully you are starting to see a pattern. Remember that, in the Section 6.4 and 6.5 lecture notes, we had a special notation for 10! products like 10 x 9 x 8 x 7 = 8. Write your answers to questions using the notation from Chapter 6. Using the pattern that you identified, what is the probability that two people in a room with k people in it do not share a birthday? 6! Finite Mathematics Due: 04/29/22 9. Using your general formula, what is the probability that two people in a room of 30 people do not share a birthday? (Compute the actual number for this problem. Round your answer to two decimal points.) (Most scientific calculators have the operations you will want to use under a button labeled PRB (or something similar). If you can't find this, I highly recommend using a calculator on the Internet for this computation (since you would otherwise have to type in at least 30 different numbers).) 10. (The Birthday Problem) In a room with 30 people, what is the probability that there is a pair of them that share a birthday? (Show your work, and also compute the actual number for this problem. Round your answer to two decimal points.) 11. In order to do these questions, we made a few assumptions to make life simpler. (a) The most impactful assumption that we made was that all 366 possible birthdays are equally likely. In reality, this is not the case. What is one reason for this? (b) Since not all days are equally likely, this implies that some days would have a higher chance of being someone's birthday than others. With this mind, if we ignored the assumption that we made that all birthdays are equally likely, would the odds of two people sharing a birthday increase or decrease? (c) With your answers to this Problem in mind, were we justified in making the as- sumptions that we did? Fun fact: With your general formula, you can actually show that you only need about 23 people in a room for there to be at least a 50% chance of two of them sharing birthday! See the Wikipedia page for more information. MATH-104 Finite Mathematics Project 2 Due: 04/29/22 Part III: The Pigeonhole Principle The Pigeonhole Principle can be stated as follows: Theorem (Pigeonhole Principle). Given n objects and k boxes, if we put each of then objects into one of the k boxes, if n >k then one of the boxes contains at least 2 objects. Casually put, if we put 11 pigeons into 10 holes, then there must be a hole with at least two pigeons in it. At a first glance, this should seem fairly obvious, but it turns out that this has some very interesting consequences. The following problems can be solved using the pigeonhole principle. In addition to answering the question asked, state what were your boxes (holes) and what were your objects (pigeons) 12. Morgan is dealt five cards from a standard 52 card deck of cards. What is the probability that he has at least two cards of the same suit? 13. Humans, on average, have about 100,000 follicles of hair on their head. Since this is an average, we should be able to safely assume that no human has more than 300,000 follicles of hair on their head. According to the recent census, New York City currently has a population of 8.4 million people, (a) Do two people in NYC have the same number of hairs on their heads? (b) Can you make this claim with absolute certainty about the city of Fargo? Why or why not? 14. Suppose that there are 400 students taking Calculus courses at NDSU this semester. (a) What is the probability that two of these students share a birthday? (b) What is the smallest number of people needed to always obtain this probability? Why? 15. Suppose we had 12 pigeons and 10 holes, and we put each pigeon in one of the holes Does the pigeonhole principle guarantee that there are two holes with two pigeons in them? Why or why not