1.5 Assignment: Organized Counting PDF

1.5 Assignment: Organized counting 1. In 1-3 sentences, define each of the following terms in your own words and provide an example: a. Permutation (2 marks) A sorting or arrangement of items where the order matters. This means that putting item A before item...

1.5 Assignment: Organized counting 1. In 1-3 sentences, define each of the following terms in your own words and provide an example: a. Permutation (2 marks) A sorting or arrangement of items where the order matters. This means that putting item A before item B would be different from putting item B before item A. An example of a permutation problem is shuffling a deck of cards. The order of the cards would matter in this case. b. Combination (2 marks) A sorting or arrangement of items where the order doesn’t matter. Putting item A before item B would result in the same combination as putting item B before item A. An example of a combination problem is picking 3 candies from a shop. The order of picking the candies doesn’t matter, you’ll end up with the same candies. c. Factorial (2 marks) A factorial of a number N is the product of all numbers from 1 to N. It is identified with an exclamation mark after the number, so N factorial is written as N!. The exact formula goes like this: 𝑁! = 𝑁 × (𝑁 − 1) × (𝑁 − 2) × (𝑁 − 3) ×... × 3 × 2 × 1. The factorial of 0, or 0!, is equal to 1. d. Mutually exclusive (2 marks) Mutually exclusive means two or more events that cannot happen at once. For example, if event A had happened, it is impossible that event B or event C happened. For instance, when tossing a coin, it can only land on heads or tails, not both. 2. Chris (they/them) is planning a meal for a party. The meal will include an appetizer, a main course, and dessert. They have three choices for an appetizer (Artichoke, Bruschetta, or Caviar), two choices for a main course (Drumsticks or Eggplant), and three choices for dessert (Fritter, Gelato, or Hot chocolate). a. Create a tree diagram that depicts all possible options for Chris’ meal. You may create your diagram on the computer, or draw it on paper using a ruler and dark pen and then insert a clear photograph or scan into your assignment submission. (3 marks) b. How many different meals are possible? (1 mark) Counting the right-side options, there are 18 different possible meals.  c. How many different meals are possible if Chris cannot serve Eggplant and Fritter together? Explain your answer. (2 marks) To find the answer, we can count the right-side options that include both eggplant and fritter, then subtract that from the number of total possible meals (18). By looking at the diagram, we can see that 3 options include both eggplant and fritter, therefore there are 18 − 3 = 15 different possible meals. d. How many different meals are possible if Chris must serve at least one of Artichoke, Eggplant, and Hot chocolate? Explain your answer. (3 marks) We can count the right-side options that do not include any of artichoke, eggplant, or hot chocolate, then subtract that from the number of total possible meals (18). By looking at the diagram, we can see that 4 meals do not include any of the required choices, so there are 18 − 4 = 14 different possible meals. 3. A teacher is creating a test from a question bank. If question 1 can be chosen from 8 options, question 2 chosen from 3 options, question 3 from 2 options, and question 4 from 21 options, use the multiplicative counting principle to determine the number of different tests the teacher could make. (3 marks) The multiplicative counting principle states that if there are X ways to make the first decision and Y ways to make the second, the number of different outcomes is X times Y. 8 × 3 × 2 × 21 = 1008. Therefore, there are 1008 different tests the teacher could make. 4. Given the 8 letters in the word ABSOLUTE, a. How many ways can the letters be rearranged? (2 marks) This is a permutation problem because putting A before B would not have the same result as putting B before A. 𝑃(8, 8) = 8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40320. Therefore, there are 40320 different ways the letters can be rearranged.  b. How many arrangements can be formed if A and B must be together? (3 marks) We can consider AB as one letter, meaning we have 7 letters to rearrange and we have 𝑃(7, 7) = 7! possibilities. 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040. There are 2! ways to arrange AB, so 5040 × 2 × 1 = 10080. Therefore, 10080 arrangements can be formed if A and B must be together c. How many arrangements can be formed if the word must start with a vowel (A, E, O, or U) and end with “A” or “T”? (5 marks) Option 1: Ends with A This leaves 3 options for the first letter (E, O, U) and 1 option for the last letter. 3 × 6 × 5 × 4 × 3 × 2 × 1 × 1 = 2160 Option 2: Ends with T This leaves 4 options for the first letter (A, E, O, U) and 1 option for the last. 4 × 6 × 5 × 4 × 3 × 2 × 1 × 1 = 2880 Using the additive counting principle, the total is: 2160 + 2880 = 5040 Therefore, 5040 arrangements can be formed if the word must start with a vowel and end with A or T. 5. Given the digits {1, 2, 3, 4, 5}, how many 3-digit numbers can be formed if: a. No digit is repeated? (2 marks) This is a permutation problem, because putting 1 before 2 would not have the same result as putting 2 before 1. 5! 5! 𝑃(5, 3) = (5−3)! = 2! = 5 × 4 × 3 = 60 There are 60 possible 3-digit numbers with no digits repeated. b. The result must be even, and no digit is repeated? (2 marks) For the result to be even the last digit must be either 2 or 4. Since the first and second option can’t be the same as the third option, it means that we have one less option for both. 4 × 3 × 2 = 24  There are 24 possible 3-digit numbers that are even and contain no repeated digits. c. The number must contain at least 1 repeated digit? (3 marks) To find the number of possibilities that contain at least 1 repeated digit, we can find the number of total possibilities and subtract the number of possibilities that contain no repeated digits. 𝐴𝑛𝑠𝑤𝑒𝑟 = (5 × 5 × 5) − (5 × 4 × 3) 𝐴𝑛𝑠𝑤𝑒𝑟 = 125 − 60 = 65 There are 65 possible 3-digit numbers that contain at least 1 repeated digit. 6. A deck of cards in a game contains all four suits (Clubs ♣ and Spades ♠, which are black, and Hearts ♥ and Diamonds ♦, which are red), but only the cards with values 5, 6, 7, 8, 9, and 10. a. How many different 5- card hands can be formed using this deck? (3 marks) This is a combination problem, because picking a red 5 before a black 5 would have the same result as picking a black 5 before a red 5. 24! 24! 𝐶(24, 5) = (24−5)! 5! = 19! 5! = 42504. Therefore, 42504 different 5-card hands can be formed using this deck. b. How many different 5-card hands can be formed that contain at least 4 red cards? (4 marks) There are 12 red cards and 12 black in the deck. Hands containing at least 4 red cards have either 4 red cards and 1 black card or 5 red cards. 12! The first case is if the last card is black. There are 𝐶(12, 4) = 8! 4! = 495 ways to pick the first 4 red cards, and 𝐶(12, 1) = 12 ways to pick the last black card, meaning there is a total of 495 × 12 = 5940 ways to form hands with 4 red and 1 black card. The second case is if the last card is red. This means that there are 12! 𝐶(12, 5) = 7! 5! = 792 ways to form hands with 5 red cards. Using the additive counting principle, 5940 + 792 = 6732 hands are valid.  Therefore, 6732 different hands can be formed containing at least 4 red cards. c. How many different 5-card hands can be formed that contain at least one club and at least one heart? (4 marks) To calculate how many hands are possible, we can first find how many hands can be made not containing both a club and a heart, then subtract that from the total number of possible hands (42504). Since there are 6 hearts, that means we have 18 cards that can be used to make 18! a 5-card hand without a heart. 𝐶(18, 5) = 13! 5! = 8568 There are also 6 clubs, so there are 8568 hands without clubs as well. However, subtracting like this would mean that hands with neither clubs nor hearts would be subtracted twice, so we need to add them back. 12! 𝐶(12, 5) = 7! 5! = 792 Now, we can calculate the final answer. 42504 − 8568 − 8568 + 792 = 26160. Therefore, there are 26160 different 5-card hands that can be formed containing at least one spade and at least one heart. d. How many different 5-card hands can be formed that contain at least one spade and at least two 10s? (5 marks) To do this, we can find the possible hands that contain at least two 10s, then subtract any hands that do not contain spades. There are 4 10s, one of which is the 10 of spades. There are 6 spades, one of which is the 10 of spades. This means that there are 15 cards that are neither spade nor 10 (24 - 6 - 4 + 1 = 15). First, we can find the number of valid hands that have exactly two 10s. There are 4! 20! 𝐶(4, 2) = 2! 2! = 6 ways to pick the two 10s, and 𝐶(20, 3) = 17! 3! = 1140 ways to pick the last 3 cards without any of them being a 10. 6 × 1140 = 6840 different hands that can be formed. Before we move on, we need to subtract any hands that do not contain a spade. Since we can’t choose the 10 of spades, we have 3 options for the two 10s, or 3! 𝐶(3, 2) = 2! = 3 ways to pick the 10s. The last 3 cards have to be neither spade  15! nor 15, leaving 𝐶(15, 3) = 12! 3! = 455 options. 3 × 455 = 1365 options have exactly 2 10s, but no spades, meaning they are invalid. 6840 − 1365 = 5475 possible hands contain exactly two 10s and at least one spade. Now we need to find the number of valid hands that have exactly three 10s. This 4! means we have 𝐶(4, 3) = 3! = 4 ways to choose three out of the four tens and 20 𝐶(20, 2) = 18! 2! = 190 ways to choose two of the 20 non-10 cards left. 4 × 190 = 760 hands contain exactly three 10s. Now we subtract any hands that do not contain spades, which can be made using all 3 non-spade 10s 15 (meaning only one way to choose) and 𝐶(15, 2) = 13! 2! = 105 ways to choose the other two non-10 and non-spade cards. 760 − 105 = 655 hands contain exactly three 10s and at least one spade. Finally, we calculate the hands that contain 4 10s. This leaves one option for the first four cards (since all 10s have to be used) and 𝐶(20, 1) = 20 ways to pick the last card, meaning there is a total of 1 × 20 = 20 possible hands. Since the 10 of spades must be used, all hands with four 10s have at least one spade. Now, we use the additive counting principle: 5475 + 655 + 20 = 6150. Therefore, 6150 hands contain at least two 10s and at least one spade. 7. Write row 8 of Pascal’s triangle, and explain how you found it. (3 marks) Elements in Pascal’s triangle can be represented by 𝐶(𝑛, 𝑟) where n is the row number and r is the position of the element. Therefore, row 8 of Pascal’s triangle is equal to: 𝐶(8, 0), 𝐶(8, 1), 𝐶(8, 2), 𝐶(8, 3), 𝐶(8, 4), 𝐶(8, 5), 𝐶(8, 6), 𝐶(8, 7), 𝐶(8, 8). This equals 1, 8, 28, 56, 70, 56, 28, 8, 1 8. Write the 11th row of Pascal’s triangle and explain how you found it. (3 marks) The 11th row is actually Row 10 because Pascal’s Triangle starts at row 0. We can use the same strategy as above to find Row 10 of Pascal’s triangle 𝐶(10, 0), 𝐶(10, 1), 𝐶(10, 2), 𝐶(10, 3), 𝐶(10, 4), 𝐶(10, 5), 𝐶(10, 6), 𝐶(10, 7), 𝐶(10, 8), 𝐶(10, 9), 𝐶(10, 10). This equals 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 9. Consider the Cartesian (x-y) grid. If you can only move right and up, how many paths are there: a. From A(0, 0) to B(6, 3)? (4 marks) To get from (0, 0) to (6, 3) is 9 movements total because it is 6 movements in the x direction (right) and 3 movements in the y direction (up). Counting the number of paths is equivalent to deciding which of those 9 movements are the 6 right movements (note: the same result would be achieved if you decide which of the 9 movements are the 3 up movements instead.) 9! This is a combination problem, so 𝐶(9, 6) = 6! 3! = 84 total paths are possible. b. From A(0, 0) to C(9, 10) if you must pass through D(5, 4) and E(7, 8)? (5 marks) Because we can only move up and right, we have to go from A to D, then from D to E, then from E to C. The number of total possible paths is the number of possible paths from each point to the next multiplied by each other. From A to D is 9 steps total, and 5 steps of those are right. 9! Using the same logic as in the previous question, there are 𝐶(9, 5) = 5! 4! = 126 possible paths from A to D. 6! From D to E is 6 steps, 2 of them to the right. There are 𝐶(6, 2) = 4! 2! = 15 possible paths from D to E. Finally, from E to C is 4 steps, 2 of them to the right. There are 4! 𝐶(4, 2) = 2! 2! = 6 possible paths from E to C. Multiplying all the numbers together, we get 126 × 15 × 6 = 11340. Therefore, there are 11340 different paths from A to C. 10. In a survey of 200 MDM4U students, the following information was found: 68 enjoy crosswords, 97 enjoy baking, 71 enjoy acting, 20 enjoy acting and crosswords, 29 enjoy acting and baking, 23 enjoy baking and crosswords, 28 do not enjoy any of those three activities. Explaining any calculations, a. How many people enjoy all three activities? (4 marks) To solve this, we can use the inclusion-exclusion principle and find for 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶). 𝑛(𝐴 ∪ 𝐵 ∪ 𝐶) = 𝑛(𝐴) + 𝑛(𝐵) + 𝑛(𝐶) − 𝑛(𝐴 ∩ 𝐵) − 𝑛(𝐴 ∩ 𝐶) − 𝑛(𝐵 ∩ 𝐶) + 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) 200 − 28 = 71 + 97 + 68 − 29 − 20 − 23 + 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) 172 = 164 + 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) = 172 − 164 = 8 Therefore, 8 people enjoy all three activities. b. How many people enjoy only acting? (2 marks) The number of people who enjoy only acting can be calculated by finding the number of people who enjoy acting, subtracting the number of people who enjoy acting and baking or acting and crosswords from it, and adding the number of people who enjoy all three activities since they have been subtracted twice in the overlaps. 𝑛(𝐴) − 𝑛(𝐴 ∩ 𝐵) − 𝑛(𝐴 ∩ 𝐶) + 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) 71 − 29 − 20 + 8 30 Therefore, 30 people enjoy only acting. c. How many people enjoy only baking? (2 marks) We can repeat the same process from the previous question. 𝑛(𝐵) − 𝑛(𝐵 ∩ 𝐴) − 𝑛(𝐵 ∩ 𝐶) + 𝑛(𝐴 ∩ 𝐵 ∩ 𝐶) 97 − 29 − 23 + 8 53 Therefore, 53 people enjoy only baking. d. Create a Venn diagram that depicts the number of students who enjoy the activities. You may draw your diagram and scan or photograph it, you may create it electronically, or if you are unable to complete this activity visually, you may describe the components of the diagram in detail. (5 marks)