Mastering AMC 8 Book PDF

Contents Preface........................................... 7 Motivation....................................... 7 How to Use This Book................................. 7 Information about math competitions......................... 8 Free Mastering AMC 8 Course.................

Contents Preface........................................... 7 Motivation....................................... 7 How to Use This Book................................. 7 Information about math competitions......................... 8 Free Mastering AMC 8 Course............................. 8 Free AMC 8 Fundamentals Classes.......................... 9 Free AMC 8 Advanced/MATHCOUNTS Classes................... 9 Combinatorics 11 1 Permutations..................................... 11 1.1 Permutations Definition............................. 12 1.2 Factorials..................................... 13 1.3 Permutations Fundamentals........................... 15 1.4 Digit Permutations................................ 16 1.5 Circular Arrangements.............................. 19 1.6 Practice Problems................................ 22 2 Combinations..................................... 28 2.1 Combinations Fundamentals........................... 29 2.2 Binomial Identity................................. 31 2.3 Tricky Combinations Examples......................... 32 2.4 Practice Problems................................ 36 3 Word Rearrangements............................... 40 3.1 Word Rearrangments Fundamentals....................... 41 3.2 Word Rearrangements with Constraints.................... 43 3.3 Practice Problems................................ 45 4 Probability...................................... 49 4.1 Probability Fundamentals............................ 50 4.2 Distinguishability................................. 51 4.3 Casework in Probability............................. 52 4.4 Probability of Independent Events....................... 53 1  Contents 4.5 Probability of Dependent Events........................ 54 4.6 Dependent or Independent?........................... 56 4.7 Practice Problems................................ 57 5 Casework....................................... 66 5.1 Casework Fundamentals............................. 67 5.2 Harder Casework Examples........................... 69 5.3 Practice Problems................................ 72 6 Complementary Counting............................. 80 6.1 Complementary Counting Fundamentals.................... 81 6.2 Complementary Counting with Casework.................... 82 6.3 Practice Problems................................ 86 7 Principle of Inclusion Exclusion (PIE)..................... 91 7.1 PIE Strategies................................... 92 7.2 PIE for 2 Events................................. 92 7.3 PIE for 3 Events................................. 95 7.4 PIE for any Number of Events (Optional)................... 97 7.5 Practice Problems................................ 99 8 Stars and Bars.................................... 104 8.1 Stars and Bars Fundamentals.......................... 105 8.2 Stars and Bars with Constraints......................... 106 8.3 Practice Problems................................ 111 9 Geometric Counting................................. 114 9.1 Geometric Counting Fundamentals....................... 116 9.2 Number of Squares in Grid............................ 117 9.3 Number of Rectangles in Grid.......................... 118 9.4 Path Counting.................................. 120 9.5 Practice Problems................................ 123 10 Recursion....................................... 132 10.1 Recursion Fundamentals............................. 133 10.2 Recursion with Constraints........................... 134 10.3 Probability Recursions.............................. 136 10.4 Practice Problems................................ 136 Algebra 140 11 Ratios and Percentages............................... 140 11.1 Ratios Fundamentals............................... 142 11.2 Rate and Work.................................. 144 2  Contents 11.3 Practice Problems................................ 147 12 Algebraic Manipulations and Equations.................... 153 12.1 System of Equations Basics........................... 155 12.2 Advanced Equation Solving Techniques..................... 156 12.3 Word Problems.................................. 158 12.4 Practice Problems................................ 160 13 Speed, Distance, and Time............................ 169 13.1 Speed, Distance, and Time............................ 170 13.2 Practice Problems................................ 172 14 Sequences and Series................................ 178 14.1 Arithmetic Sequences............................... 180 14.2 Special Series................................... 183 14.3 Geometric Sequences............................... 184 14.4 Arithmetico-Geometric Sequence........................ 186 14.5 Practice Problems................................ 186 15 Mean, Median, Mode................................ 191 15.1 Mean, Median, Mode Fundamentals....................... 192 15.2 Mean Median Mode Conditions Examples................... 194 15.3 Practice Problems................................ 196 16 Telescoping...................................... 205 16.1 Telescoping.................................... 206 16.2 Telescoping Basics................................ 206 16.3 Telescoping Sums................................. 206 16.4 Telescoping Products............................... 206 16.5 Telescoping Equation............................... 207 16.6 Practice Problems................................ 207 Number Theory 212 17 Primes and Divisibility............................... 212 17.1 Primes....................................... 213 17.2 Divisibility Rules................................. 213 17.3 Prime Factorization................................ 217 17.4 Legendre’s Formula................................ 223 17.5 Practice Problems................................ 223 18 Factors......................................... 229 18.1 Number of Factors................................ 230 18.2 Sum of Factors.................................. 232 3  Contents 18.3 Product of Factors................................ 233 18.4 Practice Problems................................ 234 19 GCD and LCM.................................... 239 19.1 GCD and LCM Fundamentals.......................... 240 19.2 GCD and LCM Product............................. 240 19.3 More GCD/LCM Properties........................... 241 19.4 Euclidean Algorithm............................... 242 19.5 Practice Problems................................ 245 20 Modular Arithmetic................................. 248 20.1 Modular Arithmetic Fundamentals....................... 249 20.2 Product Rule................................... 249 20.3 Exponent Rule.................................. 250 20.4 Multiple Modular Congruences......................... 251 20.5 Digit Cycles.................................... 252 20.6 Practice Problems................................ 253 21 Diophantine Equations............................... 258 21.1 Quadratic Factorizations............................. 261 21.2 Simon’s Favorite Factoring Trick........................ 263 21.3 Interesting Examples............................... 265 21.4 Cubic Factorizations (Optional)......................... 265 21.5 Practice Problems................................ 266 22 Miscellaneous Number Theory.......................... 273 22.1 Palindromes.................................... 274 22.2 Money Problems................................. 274 22.3 Integer Operations................................ 276 22.4 Chicken McNugget Theorem........................... 278 22.5 Practice Problems................................ 279 Geometry 287 23 Angle Chasing.................................... 287 23.1 Angle Chasing Basics............................... 288 23.2 Inscribed Angles................................. 291 23.3 Polygons...................................... 292 23.4 Advanced Circle Angle Chasing Theorems (Optional)............. 294 23.5 Practice Problems................................ 297 24 Triangles........................................ 306 24.1 Area of a Triangle................................ 307 4  Contents 24.2 Special Triangles................................. 310 24.2.1 Equilateral Triangle........................... 310 24.2.2 45-45-90 Triangle............................. 311 24.2.3 30-60-90 Triangle............................. 312 24.2.4 13-14-15 Triangle............................. 313 24.3 Pythagorean Theorem.............................. 314 24.4 Triangle Properties................................ 315 24.5 Angle Bisector Theorem............................. 317 24.6 Practice Problems................................ 318 25 Quadrilaterals..................................... 328 25.1 Square....................................... 329 25.2 Rectangle..................................... 329 25.3 Rhombus..................................... 331 25.4 Parallelogram................................... 332 25.5 Trapezoid..................................... 333 25.6 Breaking Quadrilaterals into Triangles..................... 334 25.7 Practice Problems................................ 334 26 Circles......................................... 340 26.1 Circle Properties................................. 342 26.2 Circular Area................................... 343 26.3 Length inside Circles............................... 345 26.4 Practice Problems................................ 346 27 Similar Triangles................................... 359 27.1 Congruent Triangles............................... 361 27.2 Similar Triangles................................. 363 27.3 Practice Problems................................ 367 28 Area and Length of Complex Shapes...................... 375 28.1 Hexagon...................................... 377 28.2 Octagon...................................... 379 28.3 Area of Complex Shapes............................. 379 28.4 Length of complex shapes............................ 380 28.5 Practice Problems................................ 383 29 3D Geometry..................................... 395 29.1 Cube........................................ 398 29.2 Prism....................................... 399 29.3 Pyramid...................................... 401 29.4 Cylinder...................................... 403 29.5 Cone........................................ 404 29.6 Sphere....................................... 405 5  Contents 29.7 Similar Triangles in 3D.............................. 407 29.8 Practice Problems................................ 408 30 Additional Techniques and Strategies...................... 416 30.1 Meta-solving Techniques............................. 416 30.2 Silly Mistakes................................... 420 30.3 Other Strategies To Maximize Your Score................... 423 31 Mastering AMC 10/12............................... 425 6 Preface Motivation This book was created to provide a comprehensive overview of the most important concepts on the AMC 8 math contest. The book includes video lectures for every chapter, formulas for every topic, and hundreds of examples and practice problems with detailed video solutions. This book covers the following topics: Combinatorics Algebra Number Theory Geometry How to Use This Book To get the most out of this book, please give each problem your best effort before checking out the solution! Even if you don’t solve it, the act of trying will help you gain useful insights about the problem and will help you develop the intuition needed for the topic. Each chapter includes relevant formulas for the topic along with instructive Example Prob- lems that show interesting applications of the concept. Some of the examples are explained in the video, and some of the examples have detailed explanations. The explanations provided aim to show not just the final solution, but the thought process behind finding the solution. Then, there is a Practice Problems section, which includes problems from AMC 8, AMC 10/12, MATHCOUNTS, BMT, EMCC, and many original problems from Omega Learn. These problems have detailed video solutions. 7  Preface There is also an Additional Problems section with more problems (on the harder side) for extra practice. Hopefully, the curated collection of examples and problems in this book will improve your problem solving skills and help you perform better on the AMC 8 contest. Good Luck! Discord Server Join our Discord Server to discuss problems from the book and for help with math contest preparation in general. Feedback Form If you have any feedback, find any errors, or think of any interesting problems that should be added here, please fill out this Feedback Form or email us at [email protected]. Book Updates We appreciate your feedback and will update the book regularly by adding new topics and problems. Please bookmark OmegaLearn.org to get the Latest Version of this book. Information about math competitions These videos provide some useful strategies for anyone just starting with math competitions or working towards specific competitions like the AMC 8. 1. All you need to know about Math Competitions from Elementary to High School 2. How to prepare for AMC 10/12 and qualify for AIME and USA(J)MO Free Mastering AMC 8 Course Mastering AMC 8 Course This is the video course accompanying this book, and includes video lectures for every chapter. We explain all the important concepts from this book in detail, along with many useful examples showing the application of those concepts. 8  Preface Free AMC 8 Fundamentals Classes AMC 8 Fundamentals Classes This is a crash course covering the most important fundamental concepts on the AMC 8. Free AMC 8 Advanced/MATHCOUNTS Classes AMC 8 Advanced/MATHCOUNTS Classes This is a crash course covering the most important advanced concepts on the AMC 8. 9 Combinatorics 10 Chapter 1 Permutations Video Lecture 11  Chapter 1. Permutations 1.1 Permutations Definition Definition 1.1.1. A permutation is a possible arrangement of objects in a set where the order of objects matter. Example 1.1 How many 3-digit passwords are possible where each digit is a number from 0 to 9? Solution 1.1 This is a permutation since the order of the digits matters! Notice that each digit has 10 choices. From this, how do we find the total number of 3-digit passwords? First, how many 1-digit passwords are there? This is 10 because the password is simply one of the 10 1-digit numbers. How can we try and find the number of 2-digit passwords? Suppose that the first digit is a 3. Then, how many ways are there for the 2nd digit? This is just the number of 1-digit passwords, so it’s just 10. Now, what if the first digit is a 1? Again, there are just 10 ways for the second digit. So for each of the 10 choices for the first digit, there are 10 choices for the 2nd digit. Doing this for all possible first digits, we see that there are 10 × 10 = 100 2-digit passwords. Now, how many 3-digit passwords are there? Well, there are 10 choices for the first digit, and for each first digit, there are 100 2-digit passwords, so it’s just 10 × 100 = 1000 Notice, we can also just see that there are 10 choices for the first digit. For each first digit, there are 10 choices for the 2nd digit. Finally, for each pair of first 2 digit, there are 10 choices for the 3rd digit, so the total number of ways is just 10 × 10 × 10 = 103 = 1000. 12  Chapter 1. Permutations 1.2 Factorials Definition 1.2.1 (Factorials). A factorial is the product of all positive integers less than or equal to a given positive integer. In other words n! = n × (n − 1) × (n − 2) × · · · × 1. Remark 1.2.2 For math competitions, it is recommended to memorize the following factorials as it will save you a lot of time: 0! =1 1! =1 2! =2 3! =6 4! = 24 5! = 120 6! = 720 Definition 1.2.3. A permutation is a possible arrangement of objects in a set where the order of objects matter. Example 1.2 Sohil has 1 wrapping paper in each of 4 different colors: red, orange, green, or blue. He needs to wrap all of them around a box in any order. How many ways are there for him to do this? Solution 1.2 Notice that in this problem, we can’t use the same wrapping paper twice so it’s slightly more complicated. Let’s begin this problem by approaching each layer at a time. Starting with the innermost layer, how many ways are there to choose a color for this layer? We can choose any of the 4 colors so there are just 4 ways for this to happen. How many choices are there for the 2nd layer? For the 2nd layer, since we only have 1 of each paper, only 3 of the colors are left since we already used one. Therefore, for the 2nd layer we have 3 choices for the color. 13  Chapter 1. Permutations For the 3rd layer, we have already used 2 of the wrapping papers, so there are only 2 choices left. For the final layer, we have already used 3 of the papers, so we only have 1 choice for the final paper. Now, how do we find the total number of ways? We must multiply all of the numbers since all the choices are independent. For example, let’s say the first wrapping paper chosen was red. Then, the number of ways to order the wrapping papers is simply the number of ways to arrange wrapping papers of 3 different col- ors. However, notice that this is also true for all the other color choices of the first wrapping paper (orange, green, and blue). Therefore, in total, we must multiply by 4 to the number of ways of arranging 3 wrap- ping papers of different colors. Using this logic, we get that the total number of ways to arrange the wrapping papers is 4 × 3 × 2 × 1 = 24. Notice that this is just 4!. We will see later that we can find a general formula in terms of factorials to solve this type of problem. Example 1.3 Find the number of ways to arrange 4 different books on a bookshelf. Solution 1.3 This problem is very similar to the previous one. We must consider the number of ways for each book. There are 4 choices for the first book on the bookshelf. After that there are 3 books left, so there are 3 choices for the 2nd book. Continuing on, there are 2 choices for the 3rd book, and 1 choice for the 4th book. Therefore, the total number of ways is just 4 × 3 × 2 × 1 = 4! = 24 14  Chapter 1. Permutations Example 1.4 There are 4 different AMC 8 videos. Every student in the class watches the videos in a different order. What is the maximum number of students in the class? Video Solution Theorem 1.2.4 The number of ways of arranging n distinct objects is just n! = n × (n − 1) × (n − 2) × · · · × 1 1.3 Permutations Fundamentals Example 1.5 Sam has 5 different stamps and is making a Christmas card where he puts 3 different stamps in a line. How many different Christmas card designs can he make? Video Solution Theorem 1.3.1 (Permutations Formula) The number of ways to order k objects out of n total objects is n! n Pk = = n × (n − 1) × (n − 2) × · · · × (n − (k − 1)) (n − k)! Example 1.6 Evaluate 7 P3. 15  Chapter 1. Permutations Solution 1.4 If we compare the expression 7 P3 to the formula n Pk , we have n = 7 and k = 3. Substituting these values in the formula for permutations, 7 7! P3 = (7 − 3)! 7! = 4! = 7 × (7 − 1) ×... × (7 − (3 − 1)) = 7×6×5 = 210 Remark 1.3.2 Notice how we can use this formula as a shortcut to the previous problem. Example 1.7 Find the number of ways of selecting a president, vice president, and secretary from a group of 7 people. Solution 1.5 This is very similar to the factorials problems, except now we only have to order positions. How can we approach the problem? Let’s consider the number of ways for each position separately. There are 7 choices for the president. Now, because there are only 6 people left, there are 6 choices for the vice president. Then, because 2 of the people are already chosen for the president and vice president, there are 5 choices for the secretary. In total, the number of ways is 7 × 6 × 5 = 210 1.4 Digit Permutations 16  Chapter 1. Permutations Example 1.8 How many 4 digit numbers have all digits distinct? Solution 1.6 Let’s consider the number of ways to form this number digit by digit. For the first digit, how many choices do we have? Remember, the first digit of a num- ber cannot be 0 so there are 9 choices (any number from 1 to 9). How do we handle the condition that the numbers must have distinct digits? However, unlike the first digit, the 2nd digit can be 0. The 2nd digit can be any num- ber from 0 to 9 except the digit chosen as the first digit, so there are 10 − 1 = 9 choices. For the 3rd digit, again, it can be anything from 0 to 9 except the 2 digits already chosen, so there are 10 − 2 = 8 choices. For the final digit, there are 10 - 3 = 7 choices. So, the total number of possible numbers is 9 × 9 × 8 × 7 = 4536 Remark 1.4.1 Generally, in these types of problems, we want to consider the most restrictive conditions first. For example, in this problem, if we started at the units digit, we would have had issues in calculating the number of options for the thousands digit so we would have had to do casework, which is a more advanced technique that will be covered in a later chapter. Example 1.9 How many 4 digit numbers exist such that the first digit is odd and the other 3 digits are even and all digits distinct? 17  Chapter 1. Permutations Solution 1.7 The first digit has 5 choices (1, 3, 5, 7, or 9). The 2nd digit also has 5 choices (0, 2, 4, 6, 8). Do we have to subtract any of the choices of the 2nd digit to make sure the numbers are distinct? Keep in mind that although the digits have to be distinct, the 2nd digit is even and the first digit is odd, so there is no overlap. The 3rd digit can be any even number except the one chosen for the 2nd digit, so it has 4 choices. The 4th digit can be any even number except those chosen for the 2nd and 3rd digit. In total, the number of 4 digit numbers with these constraints is 5 × 5 × 4 × 3 = 300 Example 1.10 How many 5 digit palindromes are there? A palindrome is a number that reads the same forward and backward. Video Solution Example 1.11 (Omega Learn) How many 6 digit numbers exist such that all the digits are distinct, and it’s first 2 digits are 6 or more, the last 2 digits are 5 or less, and the 3rd digit is a nonzero multiple of 7? Video Solution 18  Chapter 1. Permutations 1.5 Circular Arrangements Theorem 1.5.1 (Circular Arrangements) The number of ways of arranging n objects in a circle where rotations of the same arrangement aren’t considered distinct is (n − 1)! The number of ways of arranging n objects in a circle where rotations of the same arrangement aren’t considered distinct and reflections of the same arrangement aren’t considered distinct is (n−1)! 2 Remark 1.5.2 The reason that this is true is because we can simply fix 1 person to be at the top and there are (n − 1)! ways to arrange the other people. This accounts for rotations since rotating an arrangement will result in someone else on top. We divide by 2 for reflections because of symmetry on both the left and right sides of the person chosen to be at the top. 19  Chapter 1. Permutations Example 1.12 How many ways are there to arrange 5 people in a circle if rotations are not counted as distinct orientations? Solution 1.8 When things are arranged in a circle, we can fix the position of one person, and look for arrangements of others. How many other people are left to arrange? We can simply apply the formula for 5 people where rotations don’t matter. This is just (5 − 1)! = 4! = 24 Example 1.13 (Omega Learn) How many ways are there to arrange 5 people around a circle such that 2 of the people, Alex and Bob, must sit next to each other. Note that rotations are not counted as distinct orientations. Video Solution Example 1.14 (Omega Learn) Gauss, Pauli, Einstein, Newton, Edison, and Faraday are sitting at a circular table. Einstein, Newton, and Faraday are enemies so they refuse to sit next to each other. With this condition, how many ways are there for the 6 physicists to sit at the table if rotations are not counted as distinct orientations? Solution 1.9 Without the condition, the answer would just be (6 − 1)! = 5! = 120 as we can fix 1 of the 6 people at the top and permute the remaining 5 people. Where must the enemies sit so that none of them are sitting next to each other? Since there are only 6 total people, there must be exactly one other person between each of the enemies as seen in the diagram below where the red X’s represent the enemies. 20  Chapter 1. Permutations Should we again try to fix someone at the top to deal with rotations? Yes! By fixing Gauss at the top (arbitrarily), we can now simply order the remaining 5 people without having to worry about the rotation condition. How many ways to permute the enemies? Note that the 3 possible locations of the enemies is fixed so there are 3! ways to permute them. How many ways to permute the people with no enemies? We already fixed Gauss (someone without enemies) so there are 2! ways to permute the other 2 people who don’t have enemies. In total, our answer is 3! × 2! = 12 21  Chapter 1. Permutations 1.6 Practice Problems Problem 1.6.1 Evaluate 6 P3 and 7 P2 Video Solution Problem 1.6.2 How many 3-digit numbers exist with all odd digits? Video Solution Problem 1.6.3 How many 3-digit numbers exist with all even digits? Video Solution Problem 1.6.4 How many 3-digit odd numbers are there with distinct digits? Video Solution Problem 1.6.5 If you have Alice, Betty, and Chase and you need to choose two of them to be the president and vice president of the math club, how many ways are there to do this? Video Solution 22  Chapter 1. Permutations Problem 1.6.6 Find the number of ways of selecting a president, vice president, and secretary from a group of 8 people. Video Solution Problem 1.6.7 Find the number of 3-digit numbers with all of its digits distinct. Video Solution Problem 1.6.8 Find the number of ways to arrange 5 different books on a bookshelf. Video Solution Problem 1.6.9 How many ways are there to pick your favorite and second favorite book amongst 5 books? Video Solution Problem 1.6.10 There are 10 students at a math contest. How many ways are there to select the first, second, and third place winners? Video Solution 23  Chapter 1. Permutations Problem 1.6.11 How many 4 digit numbers are not palindromes? A palindrome is a number that reads the same forward and backward. Video Solution Problem 1.6.12 (AMC 8) A special type of license plate includes 3 distinct letters at the beginning and 4 sin- gle digit numbers after. How many such license plates exist? Video Solution Problem 1.6.13 There is a school race with 12 students. How many different ways to award the gold, silver, and bronze medals if no ties are possible? Video Solution Problem 1.6.14 (AMC 8) How many integers between 1000 and 9999 have four distinct digits? Video Solution Problem 1.6.15 (AMC 8) The Dragonvale Middle School chess team consists of two boys and three girls. A pho- tographer wants to take a picture of the team to appear in the local newspaper. She decides to have them sit in a row with a boy at each end and the three girls in the middle. How many such arrangements are possible? 24  Chapter 1. Permutations Video Solution Problem 1.6.16 (AMC 8) Professor Chang has nine different language books lined up on a bookshelf: two Arabic, three German, and four Spanish. How many ways are there to arrange the nine books on the shelf keeping the Arabic books together and keeping the Spanish books together? Video Solution Problem 1.6.17 (MATHCOUNTS) How many permutations of the digits 1, 2, 3, 4 have 1 before 3 and 2 before 4? One such permutation to include is 2134.] Video Solution Problem 1.6.18 (AMC 10) Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of 5 chairs under these conditions? Video Solution Problem 1.6.19 (Omega Learn Math Competition) Alice, Bob, Claire, Dave, Emma are sitting around a round table. Alice refuses to sit next to Bob. How many different ways can they sit around the table? (Rotations of the same arrangement are not considered different). Video Solution 25  Chapter 1. Permutations Additional Problems Problem 1.6.20 (Omega Learn) 7 people are lining up for a photograph. If the 2 tallest people must be at 1st and 7th positions in any order and the shortest person must be in the center, how many ways are there for them to line up? Problem 1.6.21 (EMCC 2014) Five distinct boys and four distinct girls are going to have lunch together around a table. They decide to sit down one by one under the following conditions: no boy will sit down when more boys than girls are already seated, and no girl will sit down when more girls than boys are already seated. How many possible sequences of taking seats exist? Answers 1.4 24 1.5 60 1.10 900 1.11 900 1.13 12 1.6.1 120, 42 1.6.2 125 1.6.3 100 1.6.4 320 26  Chapter 1. Permutations 1.6.5 6 1.6.6 336 1.6.7 648 1.6.8 120 1.6.9 20 1.6.10 720 1.6.11 8910 1.6.12 156000000 1.6.13 1320 1.6.14 4536 1.6.15 12 1.6.16 5760 1.6.17 6 1.6.18 28 1.6.19 12 1.6.20 48 1.6.21 46080 27 Chapter 2 Combinations Video Lecture 28  Chapter 2. Combinations 2.1 Combinations Fundamentals Definition 2.1.1. A combination is a collection of items where the order of the items does not matter. Remark 2.1.2 Usually, the words permute, order does matter, etc. imply a permutation while the words choose, select, order doesn’t matter, etc. imply a combination Example 2.1 How many ways can I select 3 pencils from 6 different pencils? Solution 2.1 Let’s try to approach this similarly to permutations. There are 6 choices for the first pencil, 5 choices for the 2nd pencil, and 4 choices for the 3rd pencil. So the total number of ways is just 6 × 5 × 4 = 120 Is this the number of ways of choosing or arranging? Remember that we are just selecting 3 pencils, so the order doesn’t matter. Therefore, we are overcounting many cases. For example, choosing pencil A first and pencil B second is the same as choosing pencil B first and pencil A second. So how do we account for this? Well, to answer that question, we must consider how many ways there are to order the pencils. Let’s say we have 3 pencils. How many ways are there to order them? This is just 3!because we are arranging 3 objects in order. Therefore, we are overcount- ing by a factor of 3!. 29  Chapter 2. Combinations So the total number of ways to ”choose” 3 pencils from 6 different pencils is 6×5×4 = 20 3! Example 2.1 How many ways are there to choose a committee of 3 people from 6 people? Video Solution Theorem 2.1.3 (Combinations Formula) The number of ways to choose k objects out of a total of n objects is ! n n! n(n − 1)(n − 2) · · · · (n − k + 1) = = k k!(n − k)! k!. Example 2.2 Evaluate ! 6 3 Solution 2.2 We can see that n = 6 and k = 3. Substituting these values in the formula, we get 6 × (6 − 1) × · · · × (6 − 3 + 1) 6 × 5 × 4 = = 20 3! 6 Remark 2.1.4 Notice that ! ! n n = k n−k This is true because choosing k objects that are part of your selection (left hand side) is equivalent to choosing the n − k objects that are not be part of your selection (right 30  Chapter 2. Combinations hand side). For example, ! ! 6 6 = 2 4. Example 2.2 (Omega Learn) You are working on the Mastering AMC 8 Book, and you must choose 7 of the 10 combinatorics chapters to work on. How many ways are there to do this? Video Solution Example 2.3 (Omega Learn) You are working on the Mastering AMC 8 Book, and you must choose 7 of the 10 com- binatorics chapters to work on. However, the first 2 chapters are required to understand the remaining chapters so they must be chosen. How many ways are there to do this? Video Solution 2.2 Binomial Identity Theorem 2.2.1 (Binomial Identity) The binomial identity states that ! ! ! n n n + +···+ = 2n 0 1 n Remark 2.2.2 Both of the above methods can be used for calculating the number of ways of choosing any # of items from n different items. 31  Chapter 2. Combinations Example 2.3 Nihir has an apple, orange, banana, pear, and raspberry. He wants to take a fruit basket to a picnic. How many different types of fruit baskets can he take using the fruits he has? Solution 2.3 We can do this by listing the number of ways of choosing all possible combination of fruits. Is there any easier way to solve this question? Notice that for each fruit, we have 2 choices. You can either take it, or leave it. We then have to multiply this for all of the 5 fruits. Therefore, the number of ways is simply 25 = 32 Note that one of the fruit baskets will have none of the fruits (which is mathematically a possible type of fruit basket and the problem statement does not explicitly says that it is not allowed). Example 2.4 You have 5 different pencils and 3 different erasers and must choose some of them to take to the AMC 8. How many ways are there to do this? Video Solution 2.3 Tricky Combinations Examples Example 2.4 (Omega Learn) There are 6 experienced applicants and 7 inexperienced applicants applying for a job. Out of the experienced applicants, 2 managers are selected. Out of all of the other applicants who aren’t selected for a manager (both experienced and inexperienced), 4 other employees are selected. How many ways are there to do this? 32  Chapter 2. Combinations Solution 2.4 To solve this problem, we will find the number of ways of choosing managers and other employees separately. First, how many ways are there to select 2 managers? Since they must be from the 6 experienced applicants, there are ! 6 6 × 5 30 = = = 15 2 2! 2 Next, how many ways are there to select the 5 other employees? Since 2 of the experienced applicants were already selected, there are 4 experienced ap- plicants and 7 inexperienced applicants left. Therefore, we must select 4 employees out of the 11 remaining people. We can do this in ! 11 11 × 10 × 9 × 8 11 × 10 × 72 72 = = = 11 × 10 × = 11 × 10 × 3 = 330 4 4! 24 24 Therefore, in total, how many ways are there to select the 3 managers and 5 other employees? Since there are 15 ways to select the managers and 330 ways to select the other employ- ees, there will be 15 × 330 = 4950 ways to select both the managers and the employees. Example 2.5 (Omega Learn) You have 12 different energy bars that you need to give to 3 people: Alice, Betty, and Chase. Alice needs 3 bars, Betty needs 4 bars, and Chase needs 5 bars. How many ways are there to distribute the 12 bars to satisfy their requirements? Video Solution 33  Chapter 2. Combinations Example 2.6 (EMCC) How many ways are there to place 4 balls into a 4 × 6 grid such that no column or row has more than one ball in it? (Rotations and reflections are considered distinct.) Video Solution Example 2.5 (AIME) Robert has 4 indistinguishable gold coins and 4 indistinguishable silver coins. Each coin has an engraving of one face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the 8 coins. Solution 2.5 First, let’s deal with the orderings of the coins. How many ways to arrange the 4 gold and 4 silver coins? 8! We can use the word rearrangement formula to get 4!×4! = 70. Now, we will the num- ber of ways to put the coins face up or face down in the stack If a coin is face down, what must the coin above it be? It can be anything and the faces will never meet. If a coin is face up, what must the coin above it be? It must also be face up as if it’s face down, then the faces will meet. The moment the coin first becomes face up, all the remaining coins on top must be face up as well! If none of the coins are face up, then there is 1 orientation. How many orientations exist if at least 1 of the coins is face up? We simply have to pick a coin to be the first face up coin and every other coin’s orien- tation is fixed. There are 8 ways to do this.   8 In total, we have 9 orientations for the faces of the coins and 4 = 70 ways to order the gold 34  Chapter 2. Combinations and silver coins giving us an answer of 70 × 9 = 630. 35  Chapter 2. Combinations 2.4 Practice Problems Problem 2.4.1 If you have Alice, Betty, Chase, and Dave and you need to choose two of them to be the leaders of the math club, how many ways are there to do this? Video Solution Problem 2.4.2     8 9 Evaluate 4 and 7 Video Solution Problem 2.4.3 How many ways are there to select 3 fruits amongst 8 different fruits? Video Solution Problem 2.4.4 How many ways are there to choose 4 balls from a bag which contains 9 balls of dif- ferent color? Video Solution Problem 2.4.5 Mrs. Jones is organizing a potluck and wants to serve 8 different dishes. Each fam- ily can bring 3 dishes. How many families can Mrs. Jones invite so that no two families bring the same combination of dishes? 36  Chapter 2. Combinations Video Solution Problem 2.4.6 There are 9 different flavors of ice cream at an ice cream shop. Joe wants to buy 2 or 3 scoops of different ice cream flavors. He doesn’t like 2 of the flavors Mango and Chocolate together so won’t buy them together. How many ways can he buy ice cream? Video Solution Problem 2.4.7 (AMC 10) A set of 25 square blocks is arranged into a 5 × 5 square. How many different com- binations of 3 blocks can be selected from that set so that no two are in the same row or column? Video Solution Video Solution Problem 2.4.8 (AMC 10) Henry’s Hamburger Haven offers its hamburgers with the following condiments: ketchup, mustard, mayonnaise, tomato, lettuce, pickles, cheese, and onions. A customer can choose one, two, or three meat patties and any collection of condiments. How many different kinds of hamburgers can be ordered? Video Solution Additional Problems Problem 2.4.9 (AMC 8) 37  Chapter 2. Combinations How many integers between 2020 and 2400 have four distinct digits arranged in in- creasing order? (For example, 2347 is one integer.) Problem 2.4.10 How many 5 digit positive integers exist such that the third digit is 8, the first 3 digits ascending, and last 3 digits are descending? Problem 2.4.11 (Omega Learn) There are 12 astronauts who applied to go on a mission to explore Mars. 2 differ- ent rockets will be sent from Earth: one carrying 3 people and another carrying 4. Out of the 12 astronauts, 4 of them are very experienced so they must go on either rocket. How many ways are there to place the astronauts in the rockets? Answers 2.1 20 2.2 120 2.3 56 2.4 256 2.5 27720 2.6 360 2.4.1 6 2.4.2 70, 36 2.4.3 56 2.4.4 126 38  Chapter 2. Combinations 2.4.5 56 2.4.6 112 2.4.7 600 2.4.8 768 2.4.9 15 2.4.10 588 2.4.11 1960 39 Chapter 3 Word Rearrangements Video Lecture 40  Chapter 3. Word Rearrangements 3.1 Word Rearrangments Fundamentals Example 3.1 How many ways are there to arrange the letters in the word OMEGA? Solution 3.1 This is just like arranging 5 distinct books on a shelf. Since all the letters are different, there are just 5! = 120 ways to arrange the 5 letters. Example 3.2 How many ways are there to arrange the letters in the word SUNNY? Solution 3.2 This looks similar to the previous example. Can we use the same factorial formula again? If that were the case, then our answer would just be 5! = 120. Unfortunately, this prob- lem is more complicated because now there are 2 N’s. Therefore, some arrangements will be overcounted. Let us call the two N’s N1 and N2 For example, N1 U SN2 Y and N2 U SN1 Y are the same arrangement, but our factorial formula will count them as different arrangements. How can we account for this overcouting? The valid arrangement N U SN Y is counted twice. Notice that we count each arrangement twice where the position of two N’s is swapped. Is this the case for all rearrangements? Yes, indeed. For any arrangement of the letters in the word SUNNY, we get 2 different arrangements of the word: N1 on the left and N2 on the right, N2 on the left and N1 on the right. 41  Chapter 3. Word Rearrangements 1 Therefore, the number of valid arrangements is just 2 the original 5! arrangements, which gives 5! = 60 2 Remark 3.1.1 Remember that the factorial formula only works if all the letters are different. Example 3.1 How many ways are there to arrange the letters of the word APPLE? Video Solution Theorem 3.1.2 (Word Rearrangements) The number of ways to order a word is n! d1 ! × d2 ! × d3 ! ×... where n is the number of letters and d1 , d2 , d3 ,... are the number of times each of the duplicate letters that appear in the word. Remark 3.1.3 This may seem complicated, but it essentially means the number of rearrangements of an n-letter word is n!. However, since some letters may appear multiple times (let’s say d times), we must divide by d! for all such letters because there are d! ways to arrange the duplicate letters that we are overcounting. 42  Chapter 3. Word Rearrangements 3.2 Word Rearrangements with Constraints Example 3.2 How many ways are there to arrange the letters of the word OPOSSUM if the arrange- ment must end in an M? Video Solution Remark 3.2.1 This formula is not only true for words! This formula can also work for the number of ways of arranging objects where some objects are of same type. In fact, we will use this later in geometric counting. Example 3.3 How many ways are there to rearrange the letters in COMPUTER such that the C, O, M, and P stay together (not necessarily in the same order)? Solution 3.3 This problem is slightly different from the standard word rearrangement problems because we now have a constraint. How should we deal with the condition that the COMP must stay together? Let’s treat COMP as 1 block. Since the letters anyways have to stay together, let call this block a COM P. Now, instead, we can find the number of arrangments of COM P UTER. How many ways are there to arrange COM P UTER? Notice that this is just 5! since all the letters (or symbols) are different. Now, are we done, or is there something we forgot to account for? Remember that letters in the word COMP can appear in any order inside the box, so we have to also account for rearrangements of these letters within the COM P. For each unique arrangement of COM P UTER, how many ways are there to 43  Chapter 3. Word Rearrangements arrange the letters in the word COM P ? There are 4! ways to arrange the 4 letters C O M P. Therefore, in total, there are 5! × 4! = 120 × 24 = 2880 ways to rearrange COMPUTER such that the letters COMP remain together. Example 3.3 (Omega Learn) How many ways are there to arrange the letters in LOLLIPOP if the I must be next to both an L and O? Video Solution 44  Chapter 3. Word Rearrangements 3.3 Practice Problems Problem 3.3.1 How many ways are there to arrange the letters of the word MATH? Video Solution Problem 3.3.2 How many ways are there to arrange the letters of the word MISSISSIPPI? Video Solution Problem 3.3.3 Find the number of ways to order the letters in PINEAPPLE. Video Solution Problem 3.3.4 How many ways are there to misspell the word MISSPELLED? Video Solution Problem 3.3.5 How many arrangements of the word BOTTLE are there such that the 2 T’s and O remain together? Video Solution 45  Chapter 3. Word Rearrangements Problem 3.3.6 (AMC 10) A child builds towers using identically shaped cubes of different color. How many differ- ent towers with a height 8 cubes can the child build with 2 red cubes, 3 blue cubes, and 4 green cubes? (One cube will be left out.) Video Solution Additional Problems Problem 3.3.7 You have 6 apples, 3 pears, and 2 oranges. Assuming the same type of fruits are in- distinguishable, how many distinct ways are there to place the fruits in a line if the 2 oranges must be next to each other? Problem 3.3.8 (AMC 10) How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are indistin- guishable.) Video Solution Additional Problems Problem 3.3.9 (MATHCOUNTS) How many distinct four-letter permutations are possible using four of the ten letters in MATHCOUNTS? 46  Chapter 3. Word Rearrangements Problem 3.3.10 (AMC 8) In how many ways can the letters in BEEKEEPER be rearranged so that two or more Es do not appear together? Problem 3.3.11 (AHSME) How many distinguishable rearrangements of the letters in CON T EST have both the vowels first? (For instance, OET CN ST is one such arrangement but OT ET SN C is not.) Problem 3.3.12 (Omega Learn) If the letters of the word SMILE are rearranged in all possible ways, and arranged in alphabetical order like in a dictionary, then what will be the rank of the word SLIME? Answers 3.1 60 3.2 180 3.3.1 24 3.3.2 34650 3.3.3 30240 3.3.4 453599 3.3.5 72 3.3.6 1260 3.3.7 840 47  Chapter 3. Word Rearrangements 3.3.8 420 3.3.9 3360 3.3.10 24 3.3.11 120 3.3.12 112 48 Chapter 4 Probability Video Lecture 49  Chapter 4. Probability 4.1 Probability Fundamentals Definition 4.1.1. Probability is the likelihood of something happening. To calculate prob- ability, you need to know how many possible options or outcomes there are and how many right combinations there are. Theorem 4.1.2 (Probability) Total number of desired outcomes probability = Total number of possible outcomes Example 4.1 What is the probability of rolling a prime number on a 6 sided dice? Solution 4.1 To calculate probability, we need to find the number of successful and total outcomes. How many successful outcomes are there? We can see that there are 3 prime numbers from 1 to 6 (2, 3 and 5). Next, how many total outcomes are there? Well this is just 6 because it can be any number from 1 to 6. Therefore, since the probability is just the number of successful outcomes divided by the total number of outcomes, the probability is 3 1 = 6 2 50  Chapter 4. Probability 4.2 Distinguishability Example 4.2 I have cards numbered from 1 to 10. What is the probability I pick a pair of 2 different cards that have an odd product? Solution 4.2 This is a rather simple example however it demonstrates an important point about distin- guishability in probability problems. What must happen for the cards to have an odd product? Both cards must be odd. How many pairs of cards have both cards odd?   If order does not matter, then there are 52 = 10 combinations. However, if the order does matter, then there are 5 × 4 = 20 permutations. How many total pairs of cards can be chosen?   If order does not matter, then there are 10 2 = 45 combinations. However, if the order does matter, then there are 10 × 9 = 90 permutations. So does the order matter of the cards in the pair matter or not? 20 2 If the order of the cards in the pair does matter, then the probability is 90 =. If the order 9 10 2 of the cards in the pair does not matter, then the probability is 45 =. 9 Why are the probabilities are the same? When dealing with ordered pairs, the number of successful and total pairs were multiplied by 2! so they would cancel out when dividing! Remark 4.2.1 In probability problems, whether you decide to multiply for order or not is up to you as both will give the same probability. 51  Chapter 4. Probability Example 4.3 The sum of 2 positive integers is 4. Find the probability that one of the integers is a 2. Solution 4.3 There are 2 cases: 1. Both integers are 2 2. One integer is a 3 and the other is a 1 So is the probability just 12 ? No! While there are only 2 cases, they both have different chances of happening. How many ways are there for each case to happen? There is only 1 way where both integers can be 2 however there are 2 ways one of the integers is a 1 and the other is a 3 as we can flip them. The 2nd case is more likely. What is the probability with this knowledge? 1 There are a total of 3 cases of which 1 satisfies the condition so the probability is. 3 Remark 4.2.2 If you decide not to account for order when doing probability problems, make sure the number of orderings is consistent across all cases. In the first problem, every pair had 2 orderings so it was okay to neglect order. However, in the 2nd problem, the 2 cases had different number of orderings so this didn’t work. 4.3 Casework in Probability Concept 4.3.1 Often, when a problem asks for the probability of an event happening, we may have to do casework to find the number of successful outcomes and divide that by the total number of outcomes which is usually easy to find. 52  Chapter 4. Probability Example 4.1 What is the probability that the product of 4 dice rolls is a multiple of 648? Video Solution 4.4 Probability of Independent Events Example 4.4 Sohil randomly picks a number from 1 to 10. Sejal randomly picks a number from 1 to 25. What is the probability that the product of the numbers they choose is odd? Solution 4.4 For this problem, although it is possible to find the number of successful and total outcomes amongst both picks of numbers, there is an easier way to solve the problem. To start, what do we know about 2 numbers whose product is odd? For the product of 2 numbers to be odd, both numbers must be odd because if any of the numbers are even, then the product will also have a factor of 2 in it. Next, how can find the probability that Sohil and Sejal pick odd numbers? We could find find the number of successful and total outcomes amongst both picks of numbers as mentioned earlier, but instead, we can simply find the probabilities of each of them picking an odd number. 5 The probability of Sohil picking an odd number is 10 = 12. 13 The probability of Sejal picking an odd number is 25 since there are 13 odd numbers from 1 to 25. Now, how do we find the overall probability of both of them picking an odd number? We must multiply the probabilities. 53  Chapter 4. Probability Therefore, the overall probability is 1 13 13 × = 2 25 50. Remark 4.4.1 Whenever we need to find the probabilities of 2 independent events happening (the results of the events don’t depend on each other), we can simply find the probability of each event individually and multiply them together. Example 4.2 (Omega Learn) Person A rolls a dice with the numbers 1, 1, 2, 6, 15, 30 and Person B rolls a dice with the numbers 1, 2, 4, 18, 28, 44. What is the probability that the product of the 2 numbers is a multiple of 24? Video Solution 4.5 Probability of Dependent Events Example 4.5 Alex, Betty, Chase, Derek, Emma, Fiona, and George are racing in a marathon. If they finish in a random order, what is the probability that Chase is 1st and George is 6th? Solution 4.5 Let’s see how to solve this problem with dependent events. Can we just use the technique above to solve this problem? That won’t work because this time, Chase’ rank affects George’s rank, such as in the case where Chase is 6th which would make it impossible for George to be 6th, so the events affect each other. Then, how do we approach this question? To do this, let’s first consider the probability Chase is 1st and then find the probability 54  Chapter 4. Probability George is 6th given that Chase is 1st. What is the probability that Chase is selected first? Because there are 7 people who can be first and Chase is one of those persons, the probability is simply 17 since they finish in a random order. Next, what is the probability that George is selected 6th if Chase is first? Notice that now out of the 7 original positions, only 6 are left. Therefore, since all posi- tions are equally likely for George, the probability he is 6th is 16. Now, how do we find the overall probability? Notice that we only need to find the probability that both Chase is first and George is 6th. Therefore, we can just find the probability of Chase being first and multiply that by the probability that George is 6th. Therefore, our answer is just 1 1 1 × = 7 6 42. Remark 4.5.1 When the events are dependent like in the example above, the probability of both events happening (say A and B) is the probability of event A happening times the probability that event B happens given that event A already happened. Example 4.3 On Saturday, there is a 20% chance of rain. On Sunday, there is a 30% chance of rain if it rained on Saturday, but only a 10% chance of rain if it didn’t rain on Saturday. What is the probability that it will rain on both days or neither day? Video Solution 55  Chapter 4. Probability Example 4.4 (AIME) There is a 40% chance of rain on Saturday and a 30% chance of rain on Sunday. However, it is twice as likely to rain on Sunday if it rains on Saturday than if it does not rain on Saturday. The probability that it rains at least one day this weekend is ab , where a and b are relatively prime positive integers. Find a + b. Video Solution 4.6 Dependent or Independent? Example 4.5 (Omega Learn) Mark must choose a seat from 5 x 5 grid of chairs in the classroom. His enemy Steve does not like Mark so wants to choose a seat that is not in the same row or column as Mark. However, to his dismay, the teacher randomly assigns seats. What is the probability that Steve is not sitting in the same row or column as Mark? Video Solution 56  Chapter 4. Probability 4.7 Practice Problems Problem 4.7.1 Two 6-sided dice are rolled. What is the probability that the sum of the numbers rolled is 2? Video Solution Problem 4.7.2 Two 6-sided dice are rolled. What is the probability that the sum of the numbers rolled is 4? Video Solution Problem 4.7.3 Two dice are rolled. What is the probability that the sum of the numbers rolled is 6? Video Solution Problem 4.7.4 (AMC 8) A fair coin is tossed 3 times. What is the probability of at least two consecutive heads? Video Solution Problem 4.7.5 (AMC 8 Modified) A fair 6 sided die is rolled twice. What is the probability that the first number that comes up is greater than the second number? 57  Chapter 4. Probability Video Solution Problem 4.7.6 (AMC 8) A box contains five cards, numbered 1, 2, 3, 4, and 5. Three cards are selected ran- domly without replacement from the box. What is the probability that 4 is the largest value selected? Video Solution Problem 4.7.7 (AMC 8) The arrows on the two spinners shown below are spun. Let the number N equal 10 times the number on Spinner A, added to the number on Spinner B. What is the probability that N is a perfect square number? 5 6 1 2 8 7 4 3 Spinner A Spinner B Problem 4.7.8 (AMC 8) A top hat contains 3 red chips and 2 green chips. Chips are drawn randomly, one at a time without replacement, until all 3 of the reds are drawn or until both green chips are drawn. What is the probability that the 3 reds are drawn? Video Solution Problem 4.7.9 (AMC 8) Two cards are dealt from a deck of four red cards labeled A, B, C, D and four green 58  Chapter 4. Probability cards labeled A, B, C, D. A winning pair is two of the same color or two of the same letter. What is the probability of drawing a winning pair? Video Solution Problem 4.7.10 (AMC 10) Three fair six-sided dice are rolled. What is the probability that the values shown on two of the dice sum to the value shown on the remaining die? Video Solution Problem 4.7.11 (AMC 8) From a regular octagon, a triangle is formed by connecting three randomly chosen ver- tices of the octagon. What is the probability that at least one of the sides of the triangle is also a side of the octagon? Video Solution Problem 4.7.12 (AMC 10) When 7 fair standard 6-sided dice are thrown, the probability that the sum of the numbers on the top faces is 10 can be written as n , 67 where n is a positive integer. What is n? 59  Chapter 4. Probability Video Solution Problem 4.7.13 (AMC 10) Bob and Alice each have a bag that contains one ball of each of the colors blue, green, orange, red, and violet. Alice randomly selects one ball from her bag and puts it into Bob’s bag. Bob then randomly selects one ball from his bag and puts it into Alice’s bag. What is the probability that after this process the contents of the two bags are the same? Video Solution Problem 4.7.14 (AMC 8) On a beach 50 people are wearing sunglasses and 35 people are wearing caps. Some people are wearing both sunglasses and caps. If one of the people wearing a cap is se- lected at random, the probability that this person is is also wearing sunglasses is 25. If instead, someone wearing sunglasses is selected at random, what is the probability that this person is also wearing a cap? Video Solution Problem 4.7.15 (Omega Learn Math Contest) John has 9 red apples and 3 green apples. He randomly selects and eats an apple. Then, 3 of the red apples get rotten and are thrown away. From the remaining apples he randomly selects and eats another apple. What the probability that both of the selected apples were red is ab , what is the value of a + b? Video Solution Problem 4.7.16 (AMC 10) Two different numbers are selected at random from {1, 2, 3, 4, 5} and multiplied together. What is the probability that the product is even? 60  Chapter 4. Probability Video Solution Problem 4.7.17 (MATHCOUNTS) A fair tetrahedral die, whose faces are numbered 1, 2, 3, and 4 is rolled three times. What is the probability that the sum of the numbers rolled is 7? Express your answer as a common fraction. Video Solution Problem 4.7.18 (AMC 8) Two different numbers are randomly selected from the set {−2, −1, 0, 3, 4, 5} and multi- plied together. What is the probability that the product is 0? Video Solution Problem 4.7.19 (Omega Learn Math Competition) Joe is standing at the point (0,0) in the infinite coordinate plane. On any given move, there is a 13 chance of him moving up, 13 chance of him moving right, 61 chance of him moving down, and 16 chance of him moving left. If the probability he will reach the point (3,3) in less than or equal to 8 moves can be described as 3ab , then what is the value of a + b? Video Solution Problem 4.7.20 (Omega Learn Math Competition) The Blazers and Cortzans are playing a series of 7 games. A team wins the series when they have won 4 games. Both teams have an equal likelihood of winning a game. If the probability the Cortzans win the series and lose less than 3 games can be expressed as mn , find the value of m + n? 61  Chapter 4. Probability Video Solution Problem 4.7.21 (AMC 8) On the dart board shown in the figure below, the outer circle has radius 6 and the inner circle has radius 3. Three radii divide each circle into three congruent regions, with point values shown. The probability that a dart will hit a given region is propor- tional to the area of the region. When two darts hit this board, the score is the sum of the point values of the regions hit. What is the probability that the score is odd? 2 1 1 2 2 1 Video Solution 62  Chapter 4. Probability Problem 4.7.22 (Omega Learn Math Competition) Eric is stacking twenty six Jenga Blocks. For n ≥ 1, the probability that placing the 1 nth block causes the whole tower to topple is 26−n assuming the tower still stands after placing n − 1 blocks. What is the expected number of blocks placed before the block that causes the tower to topple? Video Solution Additional Problems Problem 4.7.23 (AMC 8) Jamal has a drawer containing 6 green socks, 18 purple socks, and 12 orange socks. After adding more purple socks, Jamal noticed that there is now a 60% chance that a sock randomly selected from the drawer is purple. How many purple socks did Jamal add? Problem 4.7.24 (MATHCOUNTS) A positive integer divisor of 11! is chosen at random. What is the probability that this divisor is prime? Express your answer as a common fraction. Problem 4.7.25 (MATHCOUNTS) Consider the regular octahedron as shown. Each edge of the octahedron has a length of 1. An ant starts at the vertex A and crawls a total distance of 3 units along the edges of the octahedron. Any time the ant reaches a vertex of the octahedron, it randomly chooses an edge to next crawl on that is different from the edge it just left. One such path the ant may take is shown. What is the probability that the ant will end up a distance greater than 1 from its starting point A ? Express your answer as a common fraction. 63  Chapter 4. Probability Answers 5 4.1 1296 1 4.2 6 4.3 78% 4.4 107 2 4.5 3 1 4.7.1 36 1 4.7.2 12 5 4.7.3 36 3 4.7.4 8 5 4.7.5 12 64  Chapter 4. Probability 3 4.7.6 10 1 4.7.7 8 2 4.7.8 5 4 4.7.9 7 5 4.7.10 24 5 4.7.11 7 4.7.12 84 1 4.7.13 3 7 4.7.14 25 4.7.15 47 4.7.16 0.7 3 4.7.17 16 1 4.7.18 3 4.7.19 468 4.7.20 43 35 4.7.21 72 4.7.22 12 4.7.23 9 1 4.7.24 108 2 4.7.25 9 65 Chapter 5 Casework Video Lecture 66  Chapter 5. Casework 5.1 Casework Fundamentals Concept 5.1.1 Casework is solving counting or probability problems by considering the different cases and adding them together. Many counting or probability problems can be solved by dividing a problem into several cases and calculating arrangements and probabilities for each case before summing them together. You should try casework when there are no other obvious approaches as it is one of the most common techniques on the AMC 8. Example 5.1 Two dice are rolled. What is the number of the ways that the sum of the numbers rolled is 3? Solution 5.1 To do this, let’s take cases based on the first roll. How many ways are there for two dice to sum to 3? Case 1: First roll is a 1 If the first roll is a 1, then the second roll must be 2. Case 2: First roll is a 2 If the first roll is a 2, then the second roll must be 1. Case 3: First roll is a 3 or more If the first roll is anything 3 or more, then the sum will always be at least 4 (since the 2nd roll is at least 1), so this is not possible. Therefore, in total, there are 2 ways. 67  Chapter 5. Casework Example 5.2 Two cards are dealt from a deck of four red cards labeled A, B, C, D and four green cards labeled A, B, C, D. Winning pair is two of the same color or two of the same letter. How many ways are there to draw a winning pair? Solution 5.2 This is a another casework problems. The first step is to identify the different cases. What are the different ways to draw a winning pair? We can either have the same color or the same letter. Note that having the same color and having the same letter are not possible as that would mean drawing the same card twice which is not possible. We consider the cases separately. Case 1: The 2 cards are the same color. For this case, we have 2 choices for which color both cards will be. How many ways are there to select 2 cards from 4 cards of a given color?   4 Since there are 4 cards of each color, and we must select 2 of them, there are just 2 ways to select 2 cards. Therefore, the number of ways to pick 2 cards of the same color will just be the number of colors times the number of ways to select 2 cards from that color, which is ! 4 4×3 2× = 2× = 12 2 2 Case 2: The 2 cards are the same letter. For this case, we have 4 choices for which letter both cards will have. Now, how many color choices are possible for the 2 cards? Remember that order does not matter in our winning pair. For each letter, there are only 2 cards available to draw (red or green). Because we need to draw 2 cards for a winning pair, we need to draw both of the 2 cards available to form a winning   pair, so there is only 1 way to do this. Another way to think about this is that there are 22 = 1 way to pick the colors. 68  Chapter 5. Casework Therefore, the number of ways to pick 2 cards of the same letter is just 4 × 1 = 4. In total, the total number of winning pairs is the number of pairs of cards with the same color plus the number of pairs of cards with the same letter which is 12 + 4 = 16 Example 5.1 (Omega Learn) Sohil has 10 boxes. Each box has a green, orange, red, and blue ball. He randomly chooses one of the boxes and then uniformly at random picks a ball from that box. He repeats this process of randomly choosing any box (allowed to choose same box again) and randomly choosing a ball in that box. What is the probability that the balls are the same color? Video Solution 5.2 Harder Casework Examples Example 5.3 (Omega Learn) There are 3 identical blue boxes, 6 identical green boxes, and 5 distinct items. Each of the items must be placed into either a green or blue box, and each box can contain a maximum of 1 item. Assuming all of the boxes are different, how many ways are there to do this? Solution 5.3 There are 5 items to be put in some of the 9 green and blue boxes, so we must choose 5 of these 9 boxes to put the items into. How can we divide this problem into cases? We can choose our cases based on the number of green and blue boxes we are selecting. The cases are 1. 3 blue boxes, 2 green boxes 2. 2 blue boxes, 3 green boxes 69  Chapter 5. Casework 3. 1 blue box, 4 green boxes 4. 0 blue boxes, 5 green boxes Notice that this covers all the cases because it covers all possible number of blue boxes. Clearly, 6 green boxes is impossible since we only have to select 5 of them to put items into. Also, make sure to keep in mind that the boxes of the same color are identical. Case 1: 3 blue boxes, 2 green boxes For this case, how many ways are there to put 5 items into 3 blue and 2 green boxes? We can count this be seeing that we simply have to choose 3 of the items to place into the blue boxes, and the other items will be put in green boxes. We don’t have to worry about order of the items in the blue boxes(or the green boxes) because the boxes of the 5 same color are identical. We can do this in 3 ways. Case 2: 2 blue boxes, 3 green boxes Again, we do this by choosing 2 of the items to put into  blue boxes, and the remaining 3 items will be put into green boxes. We can do this 5 in 2 ways. Case 3: 1 blue boxes, 4 green boxes Out of the 5 items, we must choose   1 of them for a blue box and the remaining 4 will go in green boxes. We can do this in 51 ways. Case 4: 0 blue boxes, 5 green boxes Because all of the items must go in green boxes, there is only 1 way to do this. In total among all the cases, there are ! ! ! 5 5 5 5×4×3 5×4 5 60 20 5 + + +1 = + + +1 = + + + 1 = 10 + 10 + 5 + 1 = 26 3 2 1 3! 2! 1! 6 2 1 Remark 5.2.1 For casework problems, pick one attribute to change and find the number of ways in each of the cases. In the previous problem, this was the number of blue boxes. Sometimes, the problem may require subcases. 70  Chapter 5. Casework Example 5.2 (AMC 8) A △ or ⃝ is placed in each of the nine squares in a 3-by-3 grid. Shown below is a sample configuration with three △s in a line. How many configurations will have three △s in a line and three ⃝s in a line? Video Solution 71  Chapter 5. Casework 5.3 Practice Problems Problem 5.3.1 (AMC 8) How many different combinations of 5 dollar bills and 2 dollar bills can be used to make a total of 17 dollars if the order of the bills does not matter? Video Solution Problem 5.3.2 (AMC 8) The ”Middle School Eight” basketball conference has 8 teams. Every season, each team plays every other conference team twice (home and away), and each team also plays 4 games against non-conference opponents. What is the total number of games in a season involving the ”Middle School Eight” teams? Video Solution Problem 5.3.3 How many 3-digit even numbers are there with distinct digits? Video Solution Problem 5.3.4 (AMC 8) Paul owes Paula 35 cents and has a pocket full of 5-cent coins, 10-cent coins, and 25-cent coins that he can use to pay her. What is the difference between the largest and the smallest number of coins he can use to pay her? Video Solution 72  Chapter 5. Casework Problem 5.3.5 (AMC 8) How many pairs of parallel edges does a cube have? Video Solution Problem 5.3.6 (AMC 8) A fair coin is tossed 3 times. What is the probability there will be at least 2 consecutive heads? Video Solution Problem 5.3.7 (AMC 8) How many 4-digit positive integers have four different digits, where the leading digit is not zero, the integer is a multiple of 5, and 5 is the largest digit? Video Solution Problem 5.3.8 (AMC 10) Three fair six-sided dice are rolled. What is the probability that the values shown on two of the dice sum to the value shown on the remaining die? 73  Chapter 5. Casework Video Solution Problem 5.3.9 (AMC 10) How many rearrangements of abcd are there in which no two adjacent letters are also adjacent letters in the alphabet? For example, no such rearrangements could include either ab or ba. Video Solution Problem 5.3.10 (AMC 10) A license plate in a certain state consists of 4 digits, not necessarily distinct, and 2 letters, also not necessarily distinct. These six characters may appear in any order, ex- cept that the two letters must appear next to each other. How many distinct license plates are possible? Video Solution Problem 5.3.11 (Omega Learn Math Contest) Given the set 1, 2, 3, 4, 5, 6, 7, how many non-empty subsets of this set are there such that the sum of the elements are even? Video Solution Problem 5.3.12 (MATHCOUNTS) The Beavers, Ducks, Platypuses, and Narwhals are the only four basketball teams re- maining in a single-elimination tournament. Each round consists of the teams playing in pairs with the winner of each game continuing to the next round. If the teams are randomly paired and each has an equal probability of winning any game, what is the probability that the Ducks and the Beavers will play each other in one of the two rounds? Express your answer as a common fraction. 74  Chapter 5. Casework Video Solution Problem 5.3.13 (AMC 10) A farmer’s rectangular field is partitioned into 2 by 2 grid of 4 rectangular sections as shown in the figure. In each section the farmer will plant one crop: corn, wheat, soybeans, or potatoes. The farmer does not want to grow corn and wheat in any two sections that share a border, and the farmer does not want to grow soybeans and pota- toes in any two sections that share a border. Given these restrictions, in how many ways can the farmer choose crops to plant in each of the four sections of the field? Video Solution Problem 5.3.14 (AMC 10) How many ways are there to place 3 indistinguishable red chips, 3 indistinguishable blue chips, and 3 indistinguishable green chips in the squares of a 3 × 3 grid so that no two chips of the same color are directly adjacent to each other, either vertically or horizontally? Video Solution 75  Chapter 5. Casework Additional Problems Problem 5.3.15 (AMC 8) Abby, Bridget, and four of their classmates will be seated in two rows of three for a group picture, as shown. XXX XXX If the seating positions are assigned randomly, what is the probability that Abby and Bridget are adjacent to each other in the same row or the same column? Problem 5.3.16 (AMC 8) When three positive integers a, b, and c are multiplied together, their product is 100. Suppose a < b < c. In how many ways can the numbers be chosen? Problem 5.3.17 (AMC 8) A palindrome is a number that has the same value when read from left to right or from right to left. (For example, 12321 is a palindrome.) Let N be the least three- digit integer which is not a palindrome but which is the sum of three distinct two-digit palindromes. What is the sum of the digits of N ? Problem 5.3.18 (EMCC) Fred and George have a fair 8-sided die with the numbers 0,1,2,9,2,0,1,1 written on the sides. If Fred and George each roll the die once, what is the probability that Fred rolls a larger number than George? Problem 5.3.19 (AMC 12) On a standard die one of the dots is removed at random with each dot equally likely to 76  Chapter 5. Casework be chosen. The die is then rolled. What is the probability that the top face has an odd number of dots? Problem 5.3.20 Three unique fair tetrahedral die, whose faces are numbered 1, 2, 3, and 4 are rolled. How many ways can the sum of the numbers rolled be 7? Problem 5.3.21 (EMCC) Chad and Jordan independently choose two-digit positive integers. The two numbers are then multiplied together. What is the probability that the result has a units digit of zero? Problem 5.3.22 (BMMT) At the Berkeley Sandwich Parlor, the famous BMT sandwich consists of up to five ingredients between the bread slices. These ingredients can be either bacon, mayo, or tomato, and ingredients of the same type are indistiguishable. If there must be at least one of each ingredient in the sandwich, and the order in which the ingredients are placed in the sandwich matters, how many possible ways are there to prepare a BMT sandwich? Problem 5.3.23 (Omega Learn) How many 4-digit numbers exist such that the 2nd digit is even, the 3rd digit is a multiple of 3 that is not a multiple of 2, and the 4th digit is a multiple of 4 if all of the digits are greater than 0 and different? Problem 5.3.24 (MATHCOUNTS) The number 40,231 is a five-digit positive integer that uses five consecutive digits, al- though not necessarily in order. How many such five-digit numbers are there? 77  Chapter 5. Casework Problem 5.3.25 (MATHCOUNTS) In the grid shown, how many ways are there to spell the word “QUEUE” by mov- ing one square at a time either horizontally or vertically, and provided squares may be revisited? Problem 5.3.26 (AMC 8) In a tournament there are six teams that play each other twice. A team earns 3 points for a win, 1 point for a draw, and 0 points for a loss. After all the games have been played it turns out that the top three teams earned the same number of total points. What is the greatest possible number of total points for each of the top three teams? Problem 5.3.27 (EMCC) Jasmine rolls a fair 6-sided die, with faces labeled from 1 to 6, and a fair 20-sided die, with faces labeled from 1 to 20. What is the probability that the product of these two rolls, added to the sum of these two rolls, is a multiple of 3? Answers 9 5.1 40 5.2 84 5.3.1 2 78  Chapter 5. Casework 5.3.2 88 5.3.3 328 5.3.4 5 5.3.5 18 3 5.3.6 8 5.3.7 84 5 5.3.8 24 5.3.9 2 5.3.10 5 × 104 × 262 5.3.11 63 1 5.3.12 2 5.3.13 84 5.3.14 36 7 5.3.15 15 5.3.16 4 5.3.17 2 23 5.3.18 64 11 5.3.19 21 5.3.20 12 27 5.3.21 100 5.3.22 192 5.3.23 72 5.3.24 696 5.3.25 132 5.3.26 24 13 5.3.27 60 ”? 79 Chapter 6 Complementary Counting Video Lecture 80  Chapter 6. Complementary Counting 6.1 Complementary Counting Fundamentals Complementary counting is the problem solving technique of counting the opposite of the problem constraint and subtracting that from the total number of cases. In combinatorics problems, the keyword “at least” generally indicates that complementary counting may be helpful. Example 6.1 I roll 2 fair 6-sided dice. How many ways are there for the sum of the numbers to be 11 or less? Solution 6.1 We could do this problem by casework by considering the number of ways to roll all of the numbers from 1 to 11. However, this will take a lot of time and is very tedious. Instead, let’s try finding the opposite of what we are trying to count. What is the opposite of rolling a sum of numbers 11 or less? Notice that the sum of 2 numbers on 2 dice is at most 12 because the maximum roll on each dice is 6. Therefore, the only possibility for the sum of numbers on 2 dice that results in it not being 11 or less is for the sum to be 12. How many ways are there to have a sum of 12 on 2 dice? The only possibility for this is if both dice roll a 6, so there is only 1 way. Next, we must find the total number of ways to roll 2 dice. This is just 6 × 6 = 36. Then, how many rolls of 2 dice result in a sum that is 11 or less? This is just the number of total possible rolls minus the number of rolls that sum to a number more than 11, which is 36 − 1 = 35 81  Chapter 6. Complementary Counting Example 6.1 (Omega Learn) You have 7 slips of paper numbered 1 to 7. How many ways are there to choose any subset of them so that you have at least 2 odd numbers and 1 even number? Video Solution Example 6.2 (AMC 10) When a certain unfair die is rolled, an even number is 3 times as likely to appear as an odd number. The die is rolled twice. What is the probability that the sum of the numbers rolled is even? Video Solution Remark 6.1.1 Often we might also have to use the fact that the number of ways to choose any number of items from n items is 2n in conjunction with complementary counting. Example 6.2 (AIME) A positive integer is called ascending if, in its decimal representation, there are at least two digits and each digit is less than any digit to its right. How many ascending positive integers are there? Video Solution 6.2 Complementary Counting with Casework Example 6.3 I roll 2 fair 6-sided dice. What is the probability that the sum of the numbers is 5 or more? 82  Chapter 6. Complementary Counting Solution 6.2 In this problem, we will first find the number of ways to have a sum of 5 or more. We could do casework, but there is a much faster solution with complementary counting. What is the opposite of rolling a sum of numbers 5 or more? Because the minimum sum of 2 dice is 2 (since each dice must roll at least a 1), the dice rolls must sum to 2, 3, or 4 for the sum to not be 5 or more. We divide this into cases. Case 1: The 2 dice sum to 2 There is only 1 way for this to happen (both dice are 1). Case 2: The 2 dice sum to 3 If the first dice roll is a 1, then the 2nd dice roll must be a 2. If the first dice roll is a 2, then the 2nd dice roll must be a 1. If the first dice roll is 3 or more, then the sum will be at least 4 or more, so this case doesn’t count. So, in total there are 2 ways for the sum to be 3. Case 3: The 2 dice sum to 4 If the first dice roll is a 1, then the 2nd dice roll must be a 3. If the first dice roll is a 2, then the 2nd dice roll must be a 2. If the first dice roll is a 3, then the 2nd dice roll must be a 1. If the first dice roll is 4 or more, then the sum will be at least 5 or more, so this case doesn’t count. So in total there are 3 ways for this case. Therefore, amongst all 3 cases, there are a total of 1 + 2 + 3 = 6 ways to not have a sum of 5 or more. Next, the total number of dice rolls is 6 × 6 = 36. Therefore, the number of rolls result- ing in a sum of 5 or more is just 36 − 6 = 30. Therefore, the probability of this happening is 30 5 = 36 6 83  Chapter 6. Complementary Counting Remark 6.2.1 Often times, we have to use complementary counting in conjunction with other concepts like casework and probability. Example 6.4 How many subsets of the set {1, 2, 3, 4, 5, 6, 7, 8 , 9, 10} have at least 1 even number and do not contain all of the elements? Solution 6.3 How can we use complementary counting? We can find the total number of subsets and subtract the subsets which have no even num- bers and contain all of the elements. Note that