0% found this document useful (0 votes)
386 views400 pagesInt C&P
Uploaded by
pingpong playerCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
386 views400 pagesInt C&P
Uploaded by
pingpong playerCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 400
Intermediate
Counting and Probability
David Patrick
Art of Problem Solving
Art of Problem Solving
Books e Online Classes e Videos ¢ Interactive Resources
wwwaartofproblemsolving.com eS © 2007,2012,2015,2018 AoPS Incorporated. All Rights Reserved
Reproduction of any portion of this book without the written permission of AoPS Incorporated is strictly
1 other noncommercial uses as defined in Sections 107 and 108 of the
prohibited, except for “fair use
US. Copyright Act
Published by: AoPS Incorporated
10865 Rancho Bernardo Rd Ste 100
San Diego, CA 92127
(858) 675-4555
books@artofproblemsolving.com
ISBN-13: 978-1-934124-06-2
Visit the Art of Problem Solving website at http: //www.artofproblemsolving.com
to view
Scan this code with your mobile device to visit the Art of Problem Solving websi
our other books, our free videos and interactive resources, our online community, and our
‘online school
Cover image designed by Vanessa Rusczyk using KaleidoTile software.
Printed in the United States of America
Printed! in 2018, HOW TO USE THIS BOOK
How to Use This Book
Learn by Solving Problems
We believe that the best way to learn mathematics is by solving problems. Lots and lots of problems.
In fact, we believe that the best way to learn mathematics is to try to solve problems that you don’t
know how to do. When you discover something on your own, you'll understand it much better than if
someone had just told you.
Most of the sections of this book begin with several problems. The solutions to these problems will
be covered in the text, but try to solve the problems before reading the section. If you can’t solve some
of the problems, that’s OK, because they will all be fully solved as you read the section. Even if you can
solve all of the problems, it's still important to read the section, both to make sure that your solutions
are correct, and also because you may find that the book's solutions are simpler or easier to understand
than your own.
Explanation of Icons
Throughout the book, you will see various shaded boxes and icons
Concept: This will be a general problem-solving technique or strategy. These are
Q=se the “keys” to becoming a better problem solver!
Important: This will be something important that you should learn. It might be a)
J formula,a solution technique, ora caution
WARNING! Beware if you see this box! This will point out a common mistake or
a pitfall.
iil HOW TO USE THIS BOOK
This box will contain material which, although interesting, is not part of
the main material of the text. It’s OK to skip over these boxes, but if you
read them, you might learn something interesting!
Sidenot
Bogus Solution: Just like the impossible cube shown to the left, there’s something
wrong with any “solution” that appears in this box.
Exercises, Review Problems, and Challenge Problems
Most sections end with several Exercises. These will test your understanding of the material that was
covered in the section. You should try to solve all of the exercises. Exercises marked with a * are more
difficult
Most chapters conclude with several Review Problems. These are problems that test your basic
understanding of the material covered in the chapter. Your goal should be to solve most or all of the
Review Problems for every chapter—if you're unable to do this, it means that you haven't yet mastered
the material, and you should probably go back and read the chapter again.
All of the chapters (except for Chapter 1) end with Challenge Problems. These problems are
generally more difficult than the other problems in the book, and will really test your mastery of the
material. Some of them are very, very hard—the hardest ones are marked with a *. Don’t expect to
be able to solve all of the Challenge Problems on your first try—these are difficult problems even for
experienced problem solvers. If you are able to Solve a large number of Challenge Problems, then
congratulations, you are on your way to becoming an expert problem solver!
Hints
Many problems come with one or more hints. You can look up the hints in the Hints section in the
back of the book. The hints are numbered in random order, so that when you're looking up a hint to a
problem you don’t accidentally glance at the hint to the next problem at the same time
It is very important that you first try to solve each problem without resorting to the hints. Only after
you've seriously thought about a problem and are stuck should you seek a hint. Also, for problems
which have multiple hints, use the hints one at a time; don’t go to the second hint until you've thought
about the first one.
Solutions
The solutions to all of the Exercises, Review Problems, and Challenge Problems are in the separate
solutions book. If you are using this textbook in a regular school class, then your teacher may decide
not to make this solutions book available to you, and instead present the solutions himyherself. However, HOW TO USE THIS BOOK
if you are using this book to learn on your own, then you probably have a copy of the solutions book,
in which case there are some very important things to keep in mind
1. Make a serious attempt to solve each problem before looking at the solution. Don’t use the
solutions book as a crutch to avoid really thinking about the problem first. You should think hard
about a problem before deciding to look at the solution. On the other hand, after you've thought
hard about a problem, don’t feel bad about looking at the solution if you're really stuck.
2. After you solve a problem, it's usually a good idea to read the solution, even if you think you
know how to solve the problem. The solutions book might show you a quicker or more concise
way to solve the problem, or it might have a completely different solution method than yours.
3. If you have to look at the solution in order to solve a problem, make a note of that problem. Come
back toit ina week or two to make sure that you are able to solve iton your own, without resorting,
to the solution
Resources
Here are some other good resources for you to further pursue your study of mathematics
© The Art of Problem Solving books, by Sandor Lehoczky and Richard Rusczyk. Whereas the book
that you're reading right now will go into great detail of one specific subject area—counting and
probability—the Art of Problem Solving books cover a wide range of problem solving topics across
many different areas of mathematics.
‘© The www. artofproblemsol ving. com website. The publishers of this book are also the webmasters
of the Art of Problem Solving website, which contains many resources for students:
= a discussion forum
— ontine classes
= resource lists of books, contests, and other websites
a BTgX tutorial
a math and problem solving Wiki
and much more!
# You can hone your problem solving skills (and perhaps win prizes!) by participating in various
math contests. For middle school students in the United States, the major contests are MOEMS,
MATHCOUNTS, and the AMC 8. For U.S. high school students, some of the best-known contests
are the AMC/AIME/USAMO series of contests (which are used to choose the U.S. team for the
International Mathematical Olympiad), the American Regions Math League (ARML), the Mandel-
brot Competition, the Harvard-MIT Mathematics Tournament, and the USA Mathematical Talent
Search. More details about these contests are on page vii, and links to these and many other
contests are available on the Art of Problem Solving website. HOW TO USE THIS BOOK
A Note to Teachers
We believe students learn best when they are challenged with hard problems that at first they may not
ng philosophy behind this book
know how to do, This is the motivat
Rather than first introducing new material and then giving students exercises, we present problems
at the start of each section that students should try to solve before new material is presented. The goal
is to get students to discover the new material on their own. Often, complicated problems are broken
into smaller parts, so that students can discover new techniques one piece at a time. After the problems,
new material is formally presented in the text, and full solutions to each problem are explained, along
with problem-solving strategies.
We hope that teachers will find that their stronger students will discover most of the material in this
book on their own by working through the problems. Other students may learn better from a more
traditional approach of first seeing the new material, then working the problems. Teachers have the
flexibility to use either approach when teaching from this book.
‘The book is linear in coverage. Generally, students and teachers should progress straight through
the book in order, without skipping chapters. Sections marked with a * contain supplementary material
that may be safely skipped. In general, chapters are not equal in length, so different chapters may take
different amounts of classroom time.
Links
The Art of Problem Solving website has a page containing links to websites with content relating to
material in this book, as well as an errata list for the book. This page can be found at:
http: //www.artofproblemsolving.com/bookl inks/intermediate-counting
——
Extra! Occasionally, you'll see a box like this at the bottom of a page. This is an “Extra!” and
might be a quote, some biographical or historical background, or perhaps an interesting,
idea to think about.
vi ACKNOWLEDGEMENTS
Acknowledgements
Contests
We would like to thank the following contests for allowing us to use a selection of their problems in this
book:
« The American Mathematics Competitions, a series of contests for U.S. middle and high school
students. The AMC 8, AMC 10, and AMC 12 contests are multiple-choice tests that are taken
by over 300,000 students every year. Top scorers on the AMC 10 and AMC 12 are invited to
take the American Invitational Mathematics Examination (AIME), which is a more difficult
short-answer contest. Approximately 10,000 students every year participate in the AIME. Then
based on the results of the AMC and AIME contests, about 500 students are invited to participate
in the USA Mathematical Olympiad (USAMO) and the USA Junior Mathematical Olympiad
(USAJMO), a 2-day, 9-hour examination in which each student must show all of his or her work
Results from the USAMO are used to choose the U.S. team for the International Mathematical
Olympiad (IMO). More information about the AMC contests can be found on the AMC website
at http://www maa.org/math-competi tions.
© The Mandelbrot Competition, which was founded in 1990 by Sandor Lehoczky, Richard Rusezyk,
and Sam Vandervelde. The aim of the Mandelbrot Competition is to provide a challenging,
engaging mathematical experience that is both competitive and educational. Students compete
both as individuals and in teams. More information can be found at www.mandelbrot . org
‘+ The USA Mathematical Talent Search (USAMTS), which was founded in 1989 by Professor
George Berzsenyi. The USAMTS is a free mathematics competition open to all United States
middle and high school students. As opposed to most mathematics competitions, the USAMTS
allows students a full month to work out their solutions. Carefully written justifications are
required for each problem. More information is available at www .usamts..org
* The American Regions Math League (ARML), which was founded in 1976. The annual ARML
competition brings together nearly 2,000 of the nation’s finest students. They meet, compete
against, and socialize with one another, forming friendships and sharpening their mathematical
Vii ACKNOWLEDGEMENTS:
skills, The contest is written for high school students, although some exceptional junior high
students attend each year. The competition consists of several events, which include a team
round, a power question (in which a team solves proof-oriented questions), an individual round,
and two relay rounds. More information is available at www. arm] .com,
© The Harvard-MIT Mathematics Tournament, which is an annual math tournament for high
school students, held at MIT and at Harvard in alternating years. It is run exclusively by MIT and
Harvard students, most of whom themselves participated in math contests in high school, More
information is available at hmmt .mit . edu.
Some other sources for problems in the book are listed below.
MATHCOUNTS MATHCOUNTS, the premier national math contest for U.S. middle school students,
Putnam The William Lowell Putnam Competition, an annual math competition for undergraduate
students in North America.
PSS Problem-Solving Strategies by Arthur Engel. (See the references on page 366 for the complete
citation.)
ToT The International Mathematics Tournament of Towns, a mathematical problem solving competition
for students throughout the world.
We have also included problems from various countries’ national math Olympiad contests. These
problems are cited by country name in the text.
How We Wrote This Book
This book was written using the [ATX document processing system. We thank the authors of the various
IsTRX packages that we used while preparing this book, and also the authors of The BTEX Companion for
writing a reference book that is not only thorough but also very readable. The diagrams were prepared
using METAPOST.
About Us
This book is a collaborative effort of the staff of the Art of Problem Solving. Richard Rusczyk wrote
the original lecture notes for the online course that was the inspiration for this book; he also read
several drafts of this book and made many, many helpful suggestions. Extensive proofreading of the
manuscript was done by Greg Brockman, Chris Chang, Larry Evans, Sean Markan, Jeff Nanney, Adrian
Sanborn, Nathan Savir, and Valentin Vornicu. Special thanks to Hyun Soo Kim for his assistance with
selecting many of the problems, and to Ravi Boppana, Vahe Hagopian, Deven Ware, Laura Zehender,
and many members of the APS online community for reporting errors in previous printings of the
book. Vanessa Rusczyk designed the cover.
vil CONTENTS
Contents
How to Use This Book
Acknowledgements vii
1 Review of Counting & Probability Basics 1
1.1 Introduction 1
1.2 Basic Counting Techniques 2
1.3. Basic Probability Techniques 1
14 Expected Value 24 7
1.5. Pascal’s Triangle and the Binomial Theorem.
1.6 Summation Notation
17 Summary
Q sets and Logic ae
21 Introduction
22 © Sets
23. Operations on Sets a3
24 Truth and Logic 37
25° Quantifiers i
26 Summary 6 CONTENTS.
3 A Piece of PIE
49
3.1 Introduction 49
3.2. PIE With 2 Properties 49
3.3. PIE With 3 Properties 4
34 Counting Problems With PIE 58
3.5 PIE With Many Properties 65
3.6 Counting Items With More Than 1 of Something 68
3.7 Some Harder PIE Problems. 73
38 Summary 79
4 Constructive Counting and 1-1 Correspondences 83
41 Introduction 83
42 Some Basic Problems 84
4.3 Harder Constructive Counting Problems 86
44 1-1 Correspondence Basics 94
4.5 More Complicated 1-1 Correspondences 99
4.6 Clever 1-1 Correspondences 105
4.7 Summary 14
5 the Pigeonhole Principle 118
5.1 Introduction 18
5.2 It’s Just Common Ser . 118
5.3 Basic Pigeonhole Problems 2.0... 000. v ee eee eevee eee 19
54 More Advanced Pigeonhole Problems 122
55 Summary WwW
6 Constructive Expectation 130
6.1 Introduction - _ 130
6.2 Basic Examples 131
63 Summing Expectations Constructively 135
64x A Coat With Many Patches (Reprise) 140
65 Summary 142 CONTENTS.
7 Distributions 145
7.1 Introduction . . . . 145
7.2. Basic Distributions eer 146
73 Distributions With Extra Conditions 149
74 — More Complicated Distribution Problems e959 154
75 Summary 2 5 158
8 Mathematical Induction 161
9 Fibonacci Numbers 172
8.1 Introduction 5 72
9.2 A Motivating Problem ‘ avege 172
9.3 Some Fibonacci Problems vee 175
94 A Formula for the Fibonacci Numbers con 183
95 Summary ee . 189
1 0 Recursion 192
10.1 Introduction 192
102 Examples of Recursions . 193
103 Linear Recurrences 3 200
104A Hard Recursion Problem - . 204
105 Problems Involving Catalan Numbers 206
106 Formulas for the Catalan Numbers Q 216
107 Summary 222
1 1 Conditional Probability
11.1 Introduction
11.2 _ Basic Examples of Conditional Probability
11.3 Some Definitions and Notation
114 Harder Examples
115 _Let’s Make a Deal!
116 Summary CONTENTS:
1 2 Combinatorial Identities
243
12.1 Introduction 243,
12.2 Basic Identities 243
12. More Identities 254
124 Summary 261
1 3 Events With States 265
13.1 Introduction 265
13.2 State Diagrams and Random Walks 266
13.3 Events With Infinite States 277
134 Two-player Strategy G 284
13.5 Summary 294
1 4 Generating Functions 298
141 Introduction = 298
142 Basic Examples of Generating Functions 299
143. The Binomial Theorem (as a Generating Function) 305
144 Distributions (as Generating Functions) 307
145 The Generating Function for Partitions 314
14.6% The Generating Function for the Fibonacci Numbers 325
14.7 Summary 327
15 Graph Theory esi
15.1 Introduction 331
15.2 Definitions 332
153 Basic Properties of Graphs 334
154 Cycles and Paths 32
155 Planar Graphs 349
15.6 Eulerian and Hamiltonian Paths . 354
15.7 Summary . 360
1 6 Challenge Problems 363
xi CONTENTS
References 366
Hints to Selected Problems 367
Index 383
Xi —
Extra! Erné Rubik (1944-present) and his Magic Cube
The diagrams at the start of each chapter depict a Rubik's Cube
Erné Rubik was an inventor, sculptor, and architecture professor living in Budapest,
Hungary, when in 1974 he invented a nifty little puzzle that would go on to sell hundreds
‘of millions of copies. It was originally called the “Magic Cube,” but when it became
available worldwide in 1980, it was known simply as “Rubik’s Cube.”
‘The Cube itself is about 2 inches long on each side and is divided into a 3 x3 x 3.array
of 27 smaller cubes. Each of the 6 faces can rotate independently of each other, which
changes the configuration of the colors on the outside of the Cube. Initially, the Cube
starts with a solid color on each of its 6 faces, but rotating the sides will cause the colors
to become mixed,
‘There are exactly 43,252,003,274,489,856,000 different configurations of Rubik’s Cube!
This is a very difficult number to count: for those of you keeping score at home, it
is 8! x 12! x 3° x 2°. The goal of the puzzle is to first put the Cube into a random
configuration, and then to try to return it to its original configuration, with each side a
solid color.
Rubik's Cube became incredibly popular worldwide in the early 1980s. According to
the official Rubik's Cube website at www rubiks..com, over 100,000,000 cubes were sold
in the period from 1980 to 1982 alone. In 1983, the immense popularity of the Cube even.
led toa Saturday-morning cartoon called Rubik, The Amazing Cube,
As if solving the Cube is not challenging enough, many people enjoy the further chal-
lenge of trying to solve it as fast as possible, in some cases while blindfolded! The
World Cube Association is the official keeper of Rubik’s Cube speed-solving records.
The current world record (as of November 2018) is held by Yusheng Du, who solved a
randomly-configured Cube in 3.47 seconds. A detailed list of records is on the WCA’s
website, which is on the links page referenced on page vi
If you don’t have a Rubik's Cube at home, there’s a Java applet allowing you to play
with a virtual Cube; this applet is also available via our links page.
xv A bad review is like baking a cake with all the best ingredients and having someone sit on it, ~ Danielle Steele
CHAPTER
re of Counting & Probability Basics
1.1 Introduction
Before beginning with new material, we'll spend this chapter making sure that you have a good grasp
of the basics of counting and probability. This chapter is basically a one-chapter review of the contents
of Introduction fo Counting & Probability. Ifa lot of the material in this chapter is unfamiliar to you, then
you should probably start with the Introduction book, before tackling this book
Thechapter will consist of some problems selected from Introduction to Counting & Probability together
with their solutions.
Important: You should feel confident that you are able to solve most or all of the
Y)__ Problems in this chapter before continuing on to the rest ofthe book,
Itis important that basic counting and probability computations of the type that we do in this chapter
are as natural and familiar to you as arithmetic and basic algebra are. Asa child, you wouldn't try to
learn how to multiply three-digit numbers together without having absolutely mastered multiplication
of I-digit numbers. In the same way, you shouldn't plunge into the more advanced counting techniques
in this book without having the basics mastered
Also, there is one brief section at the end of this chapter (namely, Section 1.6) that includes new
material that is not in the Introduction book. This section discusses summation notation, an example of
which is the left side of the equation below:
Sry atlas)
If you are not familiar with this notation, please make sure that you read this section before continuing
on with the book. CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
1.2 Basic Counting Techniques
ae
Problem 1.4: My city is running a lottery. In the lottery, 25 balls numbered 1 through 25 are placed in’
abin, Four balls are drawn one at a time and their numbers are recorded, The winning combination
consists of the four selected numbers in the order they are selected. How many winning combinations
are there, if.
(a)_ each ball is discarded after it is removed?
(b)_each ball is replaced in the bin after it is removed and before the next ball is drawn?
Problem 1.2: On the island of Mumble, the Mumblian alphabet has only 5 letters, and every word in’
the Mumblian language has no more than 3 letters in it. How many words are possible? (A word can.
use a letter more than once, but 0 letters does not count as a word.)
Problem 1.3: The Smith family has 4 sons and 3 daughters. In how many ways can they be seated in
[a row of 7 chairs, such that at least 2 boys are next to each other?
Problem 1.4: How many 3-digit numbers have exactly one zero?
Problem 1.5: Our math club has 20 members and 3 officers: President, Vice President, and Treasurer.
However, one member, Ali, hates another member, Brenda. In how many ways can we fill the offices
if Ali refuses to serve as an officer if Brenda is also an officer?
Problem 1.6: How many possible distinct arrangements are there of the letters in the word BALL?
Problem 1.7: In how many different ways can 6 people be seated at a round table? Two seating
arrangements are considered the same if, for each person, the person to his or her left is the same in
both arrangements.
Problem 1.8: Consider a club that has people. What is the number of ways to form an r-person
committee from the total of 1 people?
Problem 19: Each block on the grid shown at right is 1 unit by 1 unit 2
‘Suppose we wish to walk from A to B via a 7 unit path, but we have to stay on
the grid—no cutting across blocks. How many different paths can we take?
Problem 1.10: In how many ways can a dog breeder separate his 10 puppies into a group of 4 and a
group of 6 if he has to keep Biter and Nipper, two of the puppies, in separate groups? 1.2, BASIC COUNTING TECHNIQUES
Problem 1.1: My city is running a lottery. In the lottery, 25 balls numbered 1 through 25 are
placed in a bin. Four balls are drawn one at a time and their numbers are recorded. The winning
combination consists of the four selected numbers in the order they are selected. How many winning
combinations are there, if:
(a) each ball is discarded after it is removed?
(b) each ball is replaced in the bin after it is removed and before the next ball is drawn?
Solution for Problem 1.1: (a) We have 25 choices for the first ball. After the first ball is drawn and
discarded, there are 24 balls left in the bin, so there are 24 choices for the second ball, Similarly, there
are 23 choices for the third ball and 22 choices for the fourth ball. Hence the number of winning
combinations is 25 x 24 x 23 x 22 = 303,600.
(b) We have 25 choices for each of the four ballls, since when each ball is drawn, all 25 balls are in the
bin. Hence there are 25 x 25 x 25 x 25 = 25* = 390,625 winning combinations. 0
Concept: Inanevent with multiple stages, we multiply the number of choices at each|
stage to get the total number of choices. |
Concept: It is important to distinguish selecting without replacement from selecting
with replacement. When choosing k items, in order, from a group of 1,
with replacement, we have nt choices. When choosing k items, in order,
from a group of 1, without replacement, we have
| n(n ~ 1) = 2)---(9—k +1)
choices. Selecting k items from a group of 1 items, without replacement,
‘where order matters, is called a permutation. The number of permutations
of k items from a group of 1 items is sometimes denoted P(1,k) or yPs.
Problem 1.2: On the island of Mumble, the Mumblian alphabet has only 5 letters, and every word
in the Mumblian language has no more than 3 letters in it. How many words are possible? (A word
can use a letter more than once, but 0 letters does not count asa word.)
Solution for Problem 1.2: For this problem, it makes sense to divide the words into cases, based on the
number of letters in each word,
Case 1: 1-letter words
There are 5 1-letter words (each of the 5 letters is itself a 1-letter word).
Case 2: 2-letter words
To form a 2-letter word, we have 5 choices for our first letter, and 5 choices for our second letter. Thus
there are 5 x 5 = 25 2-letter words possible.
Case 3: 3-letter words
To form a 3-letter word, we have 5 choices for our first letter, 5 choices for our second letter, and 5
choices for our third letter. Thus there are 5 x 5 x 5 = 125 3-letter words possible. CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
To get the total number of words in the language, we add the number of words from each of our
cases. (We need to make sure that the cases are exclusive, meaning they don’t overlap. But that's clear
in this solution, since, for example, a word can’t be both a 2-letter word and a 3-letter word at the same
time.)
Therefore, there are 5 + 25 + 125 = 155 words possible on Mumble. ©
Concept: Casework is the general technique of breaking up the possibilities into’
CQ=s8 two or more categories. We can then add the possibilities of the various
| cases to get the total number of possibilities.
Concept: When using casework, itis important that the cases be exclusive, meaning,
O=ABLy,
and so on for every possible arrangement of BALL. We can see this in Figure 1.1
BALiL2,BALoL: > BALL BLoAL; ,BLAL? > BLAL
BLiLoA,BlaL,A = BLLA ABLiLy,ABLoL, = ABLL
LiBAL2,L2BAL, = LBAL LiBLA,L2BLiA > LBLA
ALBLy, AL:BL; = ALBL L/ABL:,L2ABL, > LABL
LiL2BA,L2LiBA = LLBA /ALaLiB = ALLB
LiAL2B,L2AL,B = LALB 1,AB = LLAB
Figure 1.1: BALL's with different L’s 1.2. BASIC COUNTING TECHNIQUES
‘Thus, the number of arrangements of BAL; L» is exactly twice the number of arrangements of BALL
So to get the number of arrangements of BALL, we have to divide the number of arrangements of
BALjLa by 2
Therefore, the number of arrangements of BALL is 41/2 = 12.0
Concept: Often we can count outcomes by strategically overcounting the number
©=se of outcomes, and then correcting for the overcounting. One common use
of this is in counting permutations with repeated items.
Problem 1.7: In how many different ways can 6 people be seated at a round table? Two seating
arrangements are considered the same if, for each person, the person to his or her left is the same in
both arrangements.
Solution for Problem 1.7: If the 6 people were sitting in a row, rather than around a table, there would be 6!
arrangements. But this is clearly an overcounting, since several different row arrangements correspond
to the same round table arrangement. For example, suppose we take a row of 6 people and sit them at
the round table by putting the first person in the “top” seat and proceeding counterclockwise. Six row
arrangements and their corresponding circular arrangements are shown in Figure 1.2 below.
A
B F c A D B
ABCDEF : BCDEFA : CDEFAB
c E D F E A
D
D E FE
E ( 5 D A E
DEFABC EFABCD : FABCDE
F B A Ie B D
A ©
Figure 1.2: Row and Circular Seatings
All six arrangements of the people A through F shown in the diagram correspond to the same
arrangement of the people seated around a round table
The reason for this is that our problem has symmetry: each arrangement can be rotated 6 ways (one
of them being no rotation) to make other arrangements. Hence, when we put our 6! arrangements of
ABCDEF in a circle, we count each circular arrangement 6 times, once for each rotation.
Therefore, we must divide our initial overcount of 6! by 6, to account for the fact that there are
6 row arrangements corresponding to each circular arrangement. So our answer is that there are
— 7 CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
61/6 =
= 120 ways to arrange the 6 people around the table. 0
Concept: Counting outcomes with symmetry usually means some sort of strategic
CO sa overcounting,
Problem 1.8: Consider a club that has people. What is the number of ways to form an r-person
| committee from the total of peop!
Solution for Problem 1.8: We start by counting the number of ways to choose r people if order matters.
There are 1 choices for the first person, n ~ 1 choices for the second person, 1 ~ 2 choices for the third
person, and so on, up ton ~r + 1 choices for ther!" person.
So there are
nx (n=1)x (n= 2) xs x(n +1) qa)
ways to choose r people from a total of 1 people if order matters. (Recall that this is the quantity that is
often denoted by P(n,7),)
But we know that there are r! ways to order r people. Therefore, each unordered committee of r
people will correspond to r! ordered choices of r people. So we need to divide our count in equation (1.1)
by r! to correct for the overcounting.
‘Therefore our answer is
("\- nx (n=1)x(n=2)X-x(n=r +1) _ nt
r 7 inn
{Concept: If we don’t care about the order when choosing r items from a set of m)
CQ=s2 _ items—for example, when choosing a committee—we have a combina-
tion, The number of ways to choose r items from a set of n items, without
ee (tl
regard to order, is (") pronounced “nt choose r.” (Note: some sources
denote this as C(1,r) or as ,C,.) |
Important: The formula for combinations is: 71
(' nh _ nln =1Y(n
1) > =H
‘The first formula is more typically used in algebraic proofs involving
combinations, whereas the latter formula is the one that we most often
use to actually compute combinations. For example:
r+)
1) _x10x9 |
(3)- Bx2x1 7 165 1.2. BASIC COUNTING TECHNIQUES
Problem 1.9: Each block on the grid shown below is 1 unit by 1 unit. Suppose we wish to walk
from A to B via a7 unit path, but we have to stay on the grid—no cutting across blocks. How many
different paths can we take?
B
Solution for Problem 1.9: We know that we must take a7 unit path. If we look at the grid a little more.
carefully, we can see that our path must consist of 4 steps to the right and 3 steps up, and we can take
those steps in any order. So in order to specify a path, we must choose 3 of our 7 steps to be “up” (and
the other 4 steps will thus be “right”). Hence the number of paths is
7) _7x6x5 _ 4.
3)" 3x2x1
If you are not convinced, we can describe a path by writing “r” for a right step and “u" for an up
step. For every arrangement of 4 r’s and 3 u’s, we get a path from A to B, as shown in Figure 1.3.
B
A Path ruruurr is shown
Figure 1.3: Example path from A to B
Therefore, to count the number of paths from A to B, we need only to count the number of arrange-
ments of “rrrruuu.” The number of arrangements is
7 (7)
a () =
Remember how we get the above expression: there are 7! arrangements of “1yrryrsuy uss,” where we
think of each r and each u as different. However, we want to count the number of arrangements of
“rerruuu,” where the r’s and u's are all the same, so we must divide by the 4! possible arrangements of
the r’s and the 3! possible arrangements of the u's. © CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
Concept: Counting paths on a grid is one application of combinations.
ways can a dog breeder puppies into a group of 4 and
|a group of 6 if he has to keep Biter and Nipper, two of the puppies, in separate groups?
Solution for Problem 1.10: Let's first do the problem by complementary counting.
If we have no restrictions on the groups, then we simply need to choose 4 of the 10 dogs to be in the
smaller group, and the rest of the dogs will make up the larger group. There are (')) ways to do this,
But we can’t have Biter and Nipper in the same group. So we have to subtract the number of ways
that we can form the two groups with Biter and Nipper in the same group. This calls for a little bit of
casework.
Case 1: Biter and Nipper are both in the smaller group.
If they are both in the smaller group, then we have to choo:
complete the smaller group, and we can do this in (5) ways,
2 more dogs from the 8 remaining to
WARNING! Don’t mistakenly count the possibilities in Case 1 as (5)(§), by reason-|
. ing that we must choose 2 out of § dogs for the smaller group, and 6,
out of 8 dogs for the larger group. These choices are not independent!
Once we pick the 2 dogs for the smaller group, then we have no choice |
but to put the remaining 6 dogs into the larger group.
Case 2; Biter and Nipper are both in the larger group.
If they are both in the larger group, then we have to choose 4 dogs from the 8 remaining to compose the
smaller group, and we can do this in (3) ways.
So to get the number of ways to form groups such that Biter and Nipper are both in the same group,
we add the counts from our two cases, to get (5) + (5).
But remember that these are the cases that we don’t want, so to solve the problem, we subtract this
count from the number of ways to form the two groups without restrictions. Thus, our answer is
(0) 2m-m oon
The other way that we could solve this problem is by direct casework. There are two cases of possible
groupings.
Case 1: Biter is in the snualler group, Nipper is in the larger group.
To complete the smaller group, we need to choose 3 more dogs from the 8 remaining dogs. We can do
this in (°) ways.
Case 2: Nipper is in the smaller group, Biter isin the larger group.
Again, to complete the smaller group, we need to choose 3 more dogs from the 8 remaining. We can do
this in (5) ways.
0 1.3. BASIC PROBABILITY TECHNIQUES
‘To count the total number of groupings, we add the counts from our two cases, to get (5) + (°) =
56 +56 = 112 as our final answer. 2
Concept: Many counting problems can be solved in more than one way. If it’s easy
| ©=se todo, solving problems in more than one way is both good practice and a
| good way to check your answer.
1.3. Basic Probability Techniques
| cam
Problem 1.11: What is the probability that when a fair 6-sided die is rolled, a prime number faces up?
| Problem 1.12: A standard deck of cards has 52 cards divided into 4 suits, each of which has 13 cards
| Two of the suits (° and 6, called “hearts” and “diamonds”) are red, the other two (@ and 4, called
|"spades” and “clubs’) are black. The cards in the deck are placed in random order (usually by al
Process called “shuffling”). What is the probability that the first two cards are both red?
[Problem 1.13: We have a standard deck of 52 cards, with 4 cards in each of 13 ranks. We call a 5-card
|poker hand a full house if the hand has 3 cards of one rank and 2 cards of another rank (such as 33355
| or AAAKK). What is the Probability that five cards chosen at random form a fall house?
{Problem 1.14: A bag has 3 red and k white marbles, where kis an (unknown) positive integer. Two of
|the marbles are chosen at random (rom the bag. Given that the probability that the two marbles are
[the same color is}, find k
Problem 1.15: Mary and James each sit in a row of 7 chairs. They choose their seats at random. What
|is the probability that they don’t sit next to each other? _ |
Exo ——
Problem 1.16: The Grunters play the Screamers 4 times. The Grunters are the much better team, and
are 75% likely to win any given game. What is the probability that the Grunters will win all 4 games?
Problem 1.17: A bag has 4 red and 6 blue marbles. A marble is selected and not replaced, then a)
second is seleéted. What is the probability that both are the same color?
[Problem 1.18: Point C is chosen at random atop a 5 foot by 5 foot square table. A circular disk w
radius of 1 foot is placed on the table with its center directly on point C. What isthe probability that
the entire disk is on top of the table (in other words, none of the clisk hangs over an edge ofthe table)”,
oa ee
i CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
Solution for Problem 1.11: ‘There are 6 equally likely outcomes. Three of those outcomes are successful:
CLE) or fl Therefore, the probability is
Concept: If all outcomes are equally likely, then the probability of success is
= rouccess) = Number of succesful outcomes
(success) = “Number of possible outcomes
Problem 1.12: A standard deck of cards has 52 cards divided into 4 suits, each of which has 13
cards. Two of the suits (9 and 6, called “hearts” and “diamonds”) are red, the other two (#and 4,
called “spades” and “clubs”) are black. The cards in the deck are placed in random order (usually
_by a process called “shuffling”). What is the probability that the first two cards are both red?
Solution for Problem 1.12:
‘Method 1: For the total number of possibilities, there are 52 ways to pick the first card, then 51 ways to
pick the second card, for a total of 52 x 51 possibilities.
For the number of successful possibilities, there are 26 ways to pick a red card first (since there are 26
total red cards), then there are 25 ways to pick a second red card (since there are 25 red cards remaining
after we've chosen the first card). Thus, there are a total of 26 x 25 successful possibilities.
Therefore, the probability is
Number of successful outcomes _ 26x25 _ 25
PAfirst two cards are red) =“ rsber of possible outcomes ~ 52X51 ~ 102"
Method 2: For the total number of possibilities, there are () = 1326 ways to pick two cards (without
regard to order)
For the number of successful possibilities, there are ("$) = 325 ways to pick two red cards (without
regard to order).
‘Therefore, the probability is
Biliret two cas are red) = Number of moneaahal outcomiés: 325. _ 25
Number of possible outcomes 1326 102
Method 3: The probability that the first card is red is = }. If the first card is red, then the probability
that the second card is red is 3. Therefore:
x3
51
Pifirst two cards are red) = P(first card red) x P(second card red) = i
Concept: There are often many ways to approach the counting within probability
@=se problems. However you choose to approach a problem, make sure that
you are consistent! For example, if you count possible outcomes without
regard to order, don’t count successful outcomes with regard to order. In
other words, don’t compare apples and oranges!
12 1.3. BASIC PROBABILITY TECHNIQUES.
Problem 1.13: We have a standard deck of 52 cards, with 4 cards in each of 13 ranks. We call a
5-card poker hand a full house if the hand has 3 cards of one rank and 2 cards of another rank (such
as 33355 or AAAKK). What is the probability that five cards chosen at random form a full house?
Solution for Problem 1.13: The total number of outcomes is just the number of ways to choose 5 cards
from a set of 52, which is (72) = 2,598,960. Notice that in this count, we don’t care about the order in
which the cards are chosen. (Remember—apples and oranges!)
To count the number of successful outcomes, we turn to constructive counting, thinking about how
we'd construct a full house.
To form a full house, we have to choose:
(a) A rank for the 3 cards. This can be done in 13 ways.
(b) 3 of the 4 cards of that rank. This can be done in (4) = 4 ways.
(c) A rank for the other 2 cards. This can be done in 12 ways (since we can’t choose the rank that we
chose in (a)),
(d) 2 of the 4 cards of that rank. This can be done in (3) = 6 ways.
Again, note that in each of the steps in our constructive count, we don’t care about the order in
which the cards are chosen,
So there are 13 x 4x 12 x 6 = 3,744 full houses. Thus, the probability is
37446
2,598,960 ~ 4165
o
Concept: You will often have to use your toolbox of counting techniques (in this
@=ze «ase, constructive counting) to solve probability problems.
Problem 1.14: A bag has 3 red and k white marbles, where k is an (unknown) positive integer. Two
of the marbles are chosen at random from the bag. Given that the probability that the two marbles
are the same color is 3, find k.
Solution for Problem 1.14: Here we compute the probability in terms of k that the two marbles are the
same color, and then set that probability equal to $
To calculate the probability, we simply use our usual method of counting both the total number
of outcomes and the number of successful outcomes. There are k +3 total marbles in the bag, so the
number of ways to choose 2 of them, without regard to order, is (*5°).
One type of successful outcome is to choose two red marbles. This can be done in (3) = 3 ways. The
other successful outcome is to choose two white marbles. This can be done in (3) ways. Since these two CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS
cases are mutually exclusive, we can add our counts. So
3+@)
2)
We set this equal to the given probability of 3, and then solve for k. Our equation is
P(voth marbles are the same color) =
In order to solve this, we'll need to first write out the combinations:
44
Serre
reer ies
a
We can get rid of the 2’s in the denominators by multiplying the numerator and denominator of the left
side by 2:
2
6+Kk-1) 1
(k + 3k +2) 2
and then we cross-multiply to get rid of the fractions:
12 + 2k(k - 1) = (k+ 3k +2).
Multiplying out, we get
22 -2k412 =P + 5k+6,
so ~7k-+ 6 = 0. This factors as (k ~ 6)(k ~ 1) = 0, so either k = 6 or k = 1. Both solutions work. 5
Concept: Many probability problems will require some algebraic manipulation in
Q=s2 order to solve them. Don't be afraid to use algebra (in particular, to use
variables) if you need to!
in a row of 7 chairs. They choose their seats at random.
that they don’t sit next to each other?
Problem 1.15: Mary and James each
What is the probabil
Solution for Problem 1.15: There are (3) = 21 ways in which Mary and James can choose 2 chairs, if we
don’t worry about the order in which they sit.
Although we can use casework to count the number of ways they can choose chairs that are not
next to each other, it is easier to use complementary counting. If we number the chairs #1, #2, ..., #7
in order, then there are 6 ways Mary and James can choose chairs next to each other: they can sit in the
first two chairs, or chairs #2 and #3, or chairs #3 and #4, etc., up to chairs #6 and #7. Therefore
Pthey sit next to each other) =
and therefore
P(they don’t sit next to each other)
4 1.3. BASIC PROBABILITY TECHNIQUES,
Concept: Just as with counting, sometimes it’s easier to calculate the probability of
an event not occurring than it is to calculate the probability of the event
occurring.
Problem 1.16: The Grunters play the Screamers 4 times. The Grunters are the much better team,
and are 75% likely to win any given game. What is the probability that the Grunters will win all 4
games?
Solution for Problem 1.16: ‘The following solution is incorrect
Solution: Since each game has 2 possible outcomes, there are 24 = 16 possible
oo ‘outcomes for the series. Only 1 of these outcomes is what we want,
namely the Grunters winning all 4 games. Therefore the probability
is &.
‘One clue that this is an incorrect solution is that we never used the "75%" information that was
presented in the problem. The reason this solution is incorrect is that the outcomes described in the
bogus solution are not all equally likely! We can only use this counting approach to probability when
we have equally likely outcomes.
So instead, we'll use multiplication of probabilities of independent events. (The games are inde-
pendent, because the outcome of each game does not depend on what happened in the earlier games.)
Each of the 4 games is independent of the others, and in each game, the Grunters have probability +
of winning, Therefore, to get the probability that the Grunters will win all 4 games, we multiply the
probabilities that the Grunters win each individual game. This gives:
P(Granters win all 4 games) = P(Grunters win Game 1) x +. x P(Grunters win Game 4)
Soe
aaa
1
(8
Using the same logic, we can show that P(Screamers win all 4 games) = ( y =
= ox
"4
| Concept: When computing probability by counting outcomes and using,
| ome Number of successful outcom:
| P(wscoese) = “Fogiber of possible outcomes”
this approach will work only if the outcomes are equally likely.
Concept: In an event that is made up of multiple, independent, sequential sub-
O=se _ events, we multiply the probabilities of the sub-events to get the probabil-
ity of the overall event.
15 OF COUNTING & PROBABILITY BASICS,
CHAPTER 1. REVI
Problem 1.17: A bag has 4 red and 6 blue marbles. A marble is selected and not replaced, then a
second is selected. What is the probability that both are the same color
Solution for Problem 1.17: We could solve this problem by counting the outcomes, but let's instead solve
it by multiplying probabilities
The probability that both marbles are red is given by.
P(both red) = P(first red) x P(second red after first red is drawn)
The probability that the first marble is red is ;f. After drawing a red marble, there are 3 red marbles
S19
and 9 marbles total left in the bag, so the probability that the second marble is also red is 3. Therefore
43_2
Pboth red) = 75% 5 = 75
Similarly, the probability that both marbles are blue is given by
P(both blue) = P(first blue) x P(second blue after first blue is drawn).
The probability that the first marble is blue is 4. After drawing a blue marble, there are 5 blue marbles
and 9 marbles total left in the bag, so the probability that the second marble is also blue is
3. Therefore
6
P(both blue) = +
Since drawing two red marbles and drawing two blue marbles are exclusive events, we add the
individual probabilities to get the probability of one or the other occurring. Therefore:
Zz
2
3° B
|
both same color) = Ptboth red) + Ptboth blue) = 7
a
Concept: When multiplying probabilities of dependent events, be sure to take the
Q=52 _priorevents into account when computing the probabilities of later events.
Problem 1.18: Point C is chosen at random atop a 5 foot by 5 foot square table. A circular disk with
radius of | foot is placed on the table with its center directly on point C. What is the probability
that the entire disk is on top of the table (in other words, none of the disk hangs over an edge of the|
table)?
Solution for Problem 1.18: The “total outcomes” region is easy: it’s just the surface of the table, so it’s a
square region with side length 5.
The “successful outcomes” region is trickier. We can draw a diagram as in Figure 14.
16 1.4, EXPECTED VALUE
‘Unsuccessful Region
Tos cies cer
ver outlethe
Figure 1.4: Table and some disks
We can see that the disk will be entirely on the table if and only if C is at least 1 foot away from
each edge of the table. Therefore, C must be within a central square region of side length 3, as shown
in Figure 1.4.
So, now we can compute the probability:
Area of successful outcomes region 3x3 _ 9
P(success)
‘Area of possible outcomes region 5x5 25
Concept: In geometry problems, or in other problems in which the possible out-
@Q=se comes are continuous (as opposed to discrete, meaning that they can be
counted), we need to use geometry to compute the probability:
Size of successful outcomes region
Pleucceee) = ea of posible oulcomesreginv
1.4 Expected Value
i Proviems
Problem 1.19: Suppose you have a weighted coin in which heads comes up with probability } and
tails with probability 4. If you flip heads, you win $2, but if you flip tails, you lose $1. What is the
expected value of a coin flip? CHAPTER 1. REVIEW OF COUNTING & PROBABILITY BASICS.
[Problem 1.20: In an urn, I have 20 marbles: 2 red, 3 yellow, 4 blue, 5 green, and 6 black. | select one
marble at random from the umn, and I win money based on the following chart:
[ Color [| Red | Yeliow | Blue | Green | Black |
[Amountwon |] sio[ $5 | $2 | si | $0 |
What is the expected value of my winnings?
Problem 1.21: Suppose I have a bag with 12 slips of paper in it. Some of the slips have a 2 on them,
and the rest have a7 on them. If the expected value of the number shown on a slip randomly drawn
from the bag is 3.25, then how many slips have a 2?
J
Recall that expected value is the notion of a “weighted average,” where the possible outcomes of
an event are weighted by their respective probabilities. We can state this more precisely:
Concept: Suppose that we have an event with a list of possible values of the out-
CQ=s8 comes: x1,%9,...,%). Value x occurs with probability py, value x; occurs
with probability p2, and so on. Note that
Pit prt + Pa =I, |
since the probabilities must total to 1, Then the expected value of the,
‘outcome is defined as the sum of the probabilities of the outcomes times
the value of the outcomes:
E= pity + Patz +00" + Pade
Problem 1.19: Suppose you have a weighted coin in which heads comes up with probability } and
tails with probability 4. If you flip heads, you win $2, but if you lip tails, you lose $1. What is the
expected value of a coin flip?
Solution for Problem 1.19: We multiply the outcomes by their respective probabilities, and add them up:
3482) + 1-81) = =
(+82) + (SI) = $1.50 ~ $0.25 = $1.25.
(Concept: Another way to think of the expected value in Problem 1.19 is to imagine
@=