Chapter One Answers
Question 1
How many ways are there to permute the letters in the word MISSISSIPPI?Question
$${11 \choose 4,4,2} = 34,650 $$Answer
For this problem, we use multinomial theorem.
We have 4 Ss, 4 Is, and 2 Ps, this leaves us with
$${11 \choose 4,4,2} = 34,650$$ permutations of the word MISSISSIPPI.Details
Question 2
(a) How many 7-digit phone numbers are possible, assuming that the first digit can’t
be a 0 or a 1?
(b) Re-solve (a), except now assume also that the phone number is not allowed to start
with 911 (since this is reserved for emergency use, and it would not be desirable for the
system to wait to see whether more digits were going to be dialed after someone has
dialed 911).Question
A) $$ 8 \cdot 10^6 = 8,000,000$$
b)
$$ 8 \cdot 10^6 - 10^4 = 7,990,000$$Answer
a) first digit can be 2-9, other 6 digits can be 0-10
b) there are 1,000 4 digit numbers (including numbers that start with 0), subtract those from part aExplaination
Question 3
Fred is planning to go out to dinner each night of a certain week, Monday through
Friday, with each dinner being at one of his ten favorite restaurants.
(a) How many possibilities are there for Fred’s schedule of dinners for that Monday
through Friday, if Fred is not willing to eat at the same restaurant more than once?
(b) How many possibilities are there for Fred’s schedule of dinners for that Monday
through Friday, if Fred is willing to eat at the same restaurant more than once, but is
not willing to eat at the same place twice in a row (or more)?Question
a) $$ {}^{10}P_5 = 30,240 $$ b) $$ 10 \cdot 9^4 = 65,610$$Answer
a) think of each day of the week as a position, and each restaurant as different letter
b) he can choose any restaurant the first day, then for the next four days, he may choose any restaurant excluding the one he went to the previous day.Explaination
Question 4
A round-robin tournament is being held with n tennis players; this means that every player will play against every other player exactly once.
(a) How many possible outcomes are there for the tournament (the outcome lists out who won and who lost for each game)?
(b) How many games are played in total?Question
a)$$ 2 \cdot {n \choose 2} $$ b) $$ {n \choose 2} $$ Answer
a) We are counting ordered pairs
b) We are couting the number of pairs of playersExplaination
Question 5
A knock-out tournament is being held with \(2^n\) tennis players. This means that for each
round, the winners move on to the next round and the losers are eliminated, until only
one person remains. For example, if initially there are \(2^4 = 16) players, then there are
8 games in the first round, then the 8 winners move on to round 2, then the 4 winners
move on to round 3, then the 2 winners move on to round 4, the winner of which is
declared the winner of the tournament. (There are various systems for determining who
plays whom within a round, but these do not matter for this problem.)
(a) How many rounds are there?
(b) Count how many games in total are played, by adding up the numbers of games
played in each round.
(c) Count how many games in total are played, this time by directly thinking about it
without doing almost any calculation.
Question
A)
$$
n
$$
B)
$$
\sum_{i=0}^{n-1} 2^i
$$
C)
$$
2^n - 1
$$
Answer
A) Draw the bracket to gain an intuition.
B) Each round has half the number of games as the previous round, starting with \(2^{n-1}\) games because each game requires \(2\) players.
C) There are \(2^{n}\) players and each game eliminates one player until one final winner is left, this means we must play \(2^{n} -1 \) games.
Explaination
Question 6
There are 20 people at a chess club on a certain day. They each find opponents and
start playing. How many possibilities are there for how they are matched up, assuming
that in each game it does matter who has the white pieces (in a chess game, one player
has the white pieces and the other player has the black pieces)?
Question
$$
2 {20 \choose 2}
$$
Answer
There are 20 players and we are counting pairs of players, that is how we got \({20 \choose 2}\), then we need to count the possibility that each player is either black or white, that gives us the \(2\).
Explaination
Question 7
Two chess players, A and B, are going to play 7 games. Each game has three possible
outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is
a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0
points.
(a) How many possible outcomes for the individual games are there, such that overall
player A ends up with 3 wins, 2 draws, and 2 losses?
(b) How many possible outcomes for the individual games are there, such that A ends
up with 4 points and B ends up with 3 points?
(c) Now assume that they are playing a best-of-7 match, where the match will end as
soon as either player has 4 points. For example, if after 6 games the score is 4 to 2 in
favor of A, then A wins the match and they don’t play a 7th game. How many possible
outcomes for the individual games are there, such that the match lasts for 7 games and
A wins by a score of 4 to 3?
Question
A)
$$
{7 \choose 3, 2, 2} = 210
$$
B)
$$
{7 \choose 4}
$$
C)
$$
{6 \choose 3}
$$
Answer
A) Use multinomial coefficient because we have 3 different outcomes, 3 wins, 2 loses and 2 ties.
B) We count all the ways player a gets 4 wins and player b gets 3 wins out of 7 games. Because there are no ties, this is just 7 choose 4 (or 7 choose 3)
C) Because we must play 7 games and player a must win 4 to 3, the 7th game must be won by player a. There are 6 choose 3 ways for her to win the other games.
Explaination
Question 8
(a) How many ways are there to split a dozen people into 3 teams, where one team
has 2 people, and the other two teams have 5 people each?
(b) How many ways are there to split a dozen people into 3 teams, where each team has
4 people?
Question
A)
$$
\dfrac{{12 \choose 2,5,5}}{2}
$$
B)
$$
\dfrac{ {12 \choose 4,4,4} }{3!}
$$
Answer
A)
There are 12 people and we want to place them into 3 teams of sizes 2,5, and 5. Because two of these teams are the same size, we must then divide by 2!
B) There are 12 people and 2 teams of 4. Because all 3 teams are the same size, we must divide by \(3!\).
Explaination
Question 9
(a) How many paths are there from the point (0, 0) to the point (110, 111) in the
plane such that each step either consists of going one unit up or one unit to the right?
(b) How many paths are there from (0, 0) to (210, 211), where each step consists of going
one unit up or one unit to the right, and the path has to go through (110, 111)?
Question
A)
$$
{110 + 111 \choose 110}
$$
B)
$$
{110 + 111 \choose 110} \cdot {200 \choose 100}
$$
Answer
A)
To find the number of paths from \( (x_1,y_1) \) to \( (x_2, y_2) \) on a grid, you count the ways you can use:
$$
{x_2 - x_1 + y_2 - y_1 \choose x_2 - x_1}
$$
because you need to sideways \(x_2 - x_1\) times and up or down \( y_2 - y_1 \) times.
You must go up and right an additional 100, but still need to cross (110, 111), so multiply part a by:
$$
{200 \choose 100}
$$
Explaination
Question 10
To fulfill the requirements for a certain degree, a student can choose to take any 7 out
of a list of 20 courses, with the constraint that at least 1 of the 7 courses must be a
statistics course. Suppose that 5 of the 20 courses are statistics courses.
(a) How many choices are there for which 7 courses to take?
(b) Explain intuitively why the answer to (a) is not \({5 \choose 1} \cdot {19 \choose 6}\).
Question
A)
$$
\sum_{i=1}^{5} {5 \choose i} \cdot {15 \choose 7-i}
$$
OR
$$
{20 \choose 7} - {15 \choose 7}
$$
B) The provided solution is wrong because when we choose 6 from 19, we might choose the same one we selected from the stats class. In other words, this approach chooses one class twice.
Answer
A) We can either do case work, selected 1 of the 5 stats courses then 6 of the remaining courses. Then 2 of the stats courses and 5 of the remaining 15 courses and so on, but a simpler approach is to just subtract all the combinations including no stats courses from all possible combinations.
Explaination
Question 11
Let A and B be sets with |A| = n, |B| = m.
(a) How many functions are there from A to B (i.e., functions with domain A, assigning
an element of B to each element of A)?
(b) How many one-to-one functions are there from A to B (see Section A.2.1 of the
math appendix for information about one-to-one functions)?
Question
A)
$$
m^n
$$
B)
$$
{}^mP_n
$$
Answer
for part A, we just need to map each value in set A to any value in set B. This is the same question as "You have a password of length n and an alphabet of m characters, how many unique passwords can be created"
For part B, we must map each value of set A to a different value in set B, this is the same as "there are a total of m people, how many unique orderings of length n can they form".
Explaination
Question 12
Four players, named A, B, C, and D, are playing a card game. A standard, well-shuffled
deck of cards is dealt to the players (so each player receives a 13-card hand).
(a) How many possibilities are there for the hand that player A will get? (Within a
hand, the order in which cards were received doesn’t matter.)
(b) How many possibilities are there overall for what hands everyone will get, assuming
that it matters which player gets which hand, but not the order of cards within a hand?
(c) Explain intuitively why the answer to Part (b) is not the fourth power of the answer
to Part (a).
Question
A)
$${52 \choose 13}$$
B)
$$
{52 \choose 13,13,13,13}
$$
C) \({52 \choose 13}^4\) counts the number of overall hands if everyone pulled from a different deck of 52 cards.
Answer
A) we choose 13 of 52 cards, this is just the definition of \({52 \choose 13}\)y
B) If the deck is split 4 ways and each person gets 13 cards, we use multinomial theorem.
C) Each time a person picks their \(13\) cards, there are \(13\) fewer cards left.
Explaination
Question 13
A certain casino uses 10 standard decks of cards mixed together into one big deck, which
we will call a superdeck. Thus, the superdeck has 52 · 10 = 520 cards, with 10 copies
of each card. How many different 10-card hands can be dealt from the superdeck? The
order of the cards does not matter, nor does it matter which of the original 10 decks
the cards came from. Express your answer as a binomial coefficient.
Question
$$
{52 + 10 - 1 \choose 10}
$$
Answer
This is the same question as "How many ways can you distribute 10 identical balls into 52 unique buckets?"
Explaination
Question 14
$$
(4 \cdot (2^8))^2
$$
Answer
You are ordering 2 pizzas. Each pizza comes in 4 sizes and may have 1 to 7 toppings. The \(2^8\) part might not seem to make sense at first, but question 15 will show us how this works.
Explaination
Question 21
$$
\dfrac{3! \cdot 6}{3^8}
$$
Explaination
We divide the number of successes by the total number of outcomes, where a success is defined as all three people chosing adjacent floors. There are \(3!\) ways of arranging 3 people and there are 6 places to put each ordering. To calculate the total number of outcomes, we need to consider that each person can go to one of 8 floors, leaving us with \(3^8\)
Explaination
Question 22
$$
\dfrac{3!3!}{6!}
$$
Answer
There are 6! birth orders total. There are 3! ways for the girls to be last and 3! ways for the boys to be first
Explaination
Question 23
$$
1-\dfrac{6!}{6^6}
$$
Answers
There are \(6^6\) possible ways for the crimes to be distributed. There are 6! ways for 1 crime to happen in each district. We calculate the compliment to make calculations managable.
Explaination
Question 24
A) This relates to the birthday problem if we sample without replacement, we use the same eqation as the birthday problem except with the number 1,000,00 instead of 365.
B)
$$
1-\sum_{i=1}^{999} \dfrac{1,000,000 - i}{1,000,000}
$$
Answer
Question 25
$$
1-\prod_{i=1}{n-1} \dfrac{k-i}{k}
$$
Answer
This is the generic formula for problems like the birthday problem.
Explaination
Question 26
$$
1-\sum_{i=1}{2} \dfrac{10-i}{10}
$$
Answer
This is just another birthday problem in disguise
Explaination
Question 27
A)
$$
\gt
$$
B)
$$
=
$$
Answer
A) We could answer this question in several ways, some of which may involve tedious math.
If we have some insights about the distribution of the sums of numbers dice faces we can solve this problem with only trivial math.
We know that if there are 4 dice each with 6 faces, the minimum value is 4 and the max is 24. The most common values are closer to the middle of the distribution, in this case 14, is most common. 20 is closer to the middle than 21, so 20 is more likely to occure.
B) The ratio of palindromes to non-palindromes is
$$
\dfrac{26^{ceil(n/2)}}{26^{n}}
$$
where ceil mean round up if there is a remainder
Explaination
Question 28
With definitions as in the previous problem, find the probability that a random n-letter
word is a palindrome for n = 7 and for n = 8.
Question
\(n=7\))
$$
\dfrac{26^4}{26^7}
$$
\(n=8\))
$$
\dfrac{26^4}{26^8}
$$
Answer
See part B of previous question.
Explanation
Question 29
$$
\dfrac{{n \choose k} \cdot {N-n \choose m-k}}{{N \choose m}}
$$
Answer
The denominator is straight forward. There are \({N \choose m}\) ways to captur m of N elk.
For the numerator, we count the number of ways to select k from the n elk originially caught, then we multiply that by the number of ways to choose m-k new elk.
Explaination
Question 30
The following sentence "find the probability that exactly j of your guesses are correct" is ambiguous because it does not specify how many guesses we had total. For this question, we will assume you have exactly j guesses.
Clarification
$$
\dfrac{1}{{4 \choose 2}}^j = \dfrac{1}{6}^j
$$
Answer
We have 4 cards and we must choose the correct 2 cards, this means we will be corret \(\dfrac{1}{6}\)th of the time.
Question 31
A) Intuitivly, we know that the probability of the second ball being green is the same as the first because we can pretend that we selected the balls at the same time and the question is the same.
B) The probability that we choose a green ball first is
$$
\dfrac{g}{g+r}
$$
and the probability that we choose a red ball first is
$$
\dfrac{r}{r+g}
$$
If the first ball was green, the probability we select another green ball is
$$
\dfrac{g-1}{g+r-1}
$$
and if the first ball was red, the probability we select a green ball is
$$
\dfrac{g}{g+r-1}
$$
Put it all together and we see that
$$
\dfrac{g}{g+r} \cdot \dfrac{g-1}{g+r-1} + \dfrac{r}{g+r} \cdot \dfrac{g}{g+r-1} = \dfrac{g}{g+r}
$$
C)
$$
P(gg) = \dfrac{g}{g+r} \cdot \dfrac{g-1}{g+r-1}
$$
$$
P(rr) = \dfrac{r}{r+g} \cdot \dfrac{r-1}{r+g-1}
$$
$$
P(rg) = \dfrac{r}{r+g} \cdot \dfrac{g}{r+g-1}
$$
$$
P(gr) = \dfrac{r}{r+g} \cdot \dfrac{g}{r+g-1}
$$
Now find the constants where P(gg) + P(rr) = P(rg) + P(gr)
r=6, g=10
g=6, r=10
Answer
Question 32
A random 5-card poker hand is dealt from a standard deck of cards. Find the prob-
ability of each of the following possibilities (in terms of binomial coefficients).
(a) A flush (all 5 cards being of the same suit; do not count a royal flush, which is a
flush with an ace, king, queen, jack, and 10).
(b) Two pair (e.g., two 3’s, two 7’s, and an ace).
Question
A)
$$
\dfrac{{ 13 \choose 5} \cdot {4 \choose 1} - 4}{{52 \choose 5}}= \dfrac{5,144}{2,598,960} \approx 0.00197925323
$$
B)
$$
\dfrac{{13 \choose 2} \cdot {4 \choose 2}^2 \cdot {11 \choose 1} \cdot {4 \choose 1}}{{52 \choose 5}} = \dfrac{123,552}{{52 \choose 5}} \approx 0.048
$$
Answer
A) there are 13 cards of each suite and we want to choose 5 from each suite. There are 4 suites. There are 4 royal flushes.
B) We want to choose 2 cards from any two of the 13 ranks. then we choose 1 card from the other 11 ranks and we have 4 suites to choose from.
Explanation
Question 33
A random 13-card hand is dealt from a standard deck of cards. What is the probability
that the hand contains at least 3 cards of every suit?
Question
A)
$$
{13 \choose 3}^3 \cdot {13 \choose 4} \cdot 4
$$
Answer
If we have at least 3 of each suite and 13 cards total, that means we have 3 of 3 suites and 4 of one suite.
Because we can choose any of the 4 suites to have 4 of, we multiply by 4.
Explaination
Question 34
A group of 30 dice are thrown. What is the probability that 5 of each of the values
1, 2, 3, 4, 5, 6 appear?
Question
$$
\dfrac{{30 \choose 5,5,5,5,5,5}}{ 6^{30} }
$$
Answer
Each number must appear 5 times and there are 6 numbers, so we can use the multinomial coefficient for that.
The denominator is \(6^{30}\) because there are 30 dice total and 6 faces on a die.
Explanation
Question 35
A deck of cards is shuffled well. The cards are dealt one by one, until the first time an
Ace appears.
(a) Find the probability that no kings, queens, or jacks appear before the first ace.
(b) Find the probability that exactly one king, exactly one queen, and exactly one kack
appear (in any order) before the first ace.
Question
Question 36
Tyrion, Cersei, and ten other people are sitting at a round table, with their seating
arrangement having been randomly assigned. What is the probability that Tyrion and
Cersei are sitting next to each other? Find this in two ways:
(a) using a sample space of size 12!, where an outcome is fully detailed about the seating;
(b) using a much smaller sample space, which focuses on Tyrion and Cersei.
Question
Answer
Explanation
Question 37
An organization with 2n people consists of n married couples. A committee of size k is
selected, with all possibilities equally likely. Find the probability that there are exactly
j married couples within the committee
Question
$$
\dfrac{ {n \choose j} {n-j \choose k - 2j} 2^{k-2j} }{ {2n \choose k} }
$$
Answer
There are \(j\) ways to choose from the \(n\) couples, giving us \({n \choose j}\)
There are \(n-j\) remaining couples and we choose \(k-2j\) of them, giving us \({n-j \choose k-2j}\)
For each remaining couple, there are \(2\) people we can choose, giving us \(2^{k-2j}\)
The denominator is just the number of ways you can choose \(k\) from \(2n\).
Explanation
Question 38
There are n balls in a jar, labeled with the numbers 1, 2, . . . , n. A total of k balls are
drawn, one by one with replacement, to obtain a sequence of numbers.
(a) What is the probability that the sequence obtained is strictly increasing?
(b) What is the probability that the sequence obtained is increasing? (Note: In this
book, “increasing” means “nondecreasing”.)
Question
Answer
Explanation