Solutions 1 - Probability and Counting

Entry | Notes

Counting

Question 1

$(1 11) (4 10) (4 6) (2 2) = 34650$

Question 2

(a) $8 * 1 0^{6} = 8000000$

(b) $8 * 1 0^{6} - (1) * 1 0^{4} = 7990000$

Question 3

(a) $10 * 9 * 8 * 7 * 6 = 30240$

(b) $10 * 9 * 9 * 9 * 9 = 65610$

Question 4

(a) $2^{(2 n)}$

(b) $(2 n)$

Question 5

(a) For $2^{n}$ players there are $n$ rounds.

(b) $\sum_{i = 0}^{n - 1} 2^{i} = 2^{n} - 1$

(c) Every team except the champion needs to lose a game, so there should be $2^{n} - 1$ games, for this to happen.

Question 6

$\frac{20 !}{10 !} = 670442572800$

Question 7

(a) $(3 7) (2 4) (2 2) = 35 * 6 * 1 = 210$

(b) The possible combinations for $4 - 3$ are: ${4 W, 3 L}, {3 W, 2 D, 2 L}, {2 W, 4 D, 1 L}, {1 W, 6 D}$ $(4 7) (3 3) + (3 7) (2 4) (2 2) + (2 7) (4 5) (1 1) + (1 7) (6 6) = 35 + 35 * 6 + 21 * 5 + 7 = 357$

(c) The valid outcomes until 6th round are $3.5 - 2.5$ and $3 - 3$ so the game ends on the 7th round, therefore the possible combinations are: For $3.5 - 2.5$ : ${3 W, 3 L}, {2 W, 2 D, 2 L}, {1 W, 4 D, 1 L}, {6 D}$ For $3 - 3$ : ${3 W, 1 D, 2 L}, {2 W, 3 D, 1 L}, {1 W, 5 D}$ Therefore: $(3 6) (3 3) + (2 6) (2 4) (2 2) + (1 6) (4 5) (1 1) + (6 6) + (3 6) (1 3) (2 2) + (2 6) (3 4) (1 1) + (1 6) (5 5) = 267$

Question 8

(a) $\frac{( 2 12 ) ( 5 10 ) ( 5 5 )}{2 !} = 8316$

(b) $\frac{( 4 12 ) ( 4 8 ) ( 4 4 )}{3 !} = 5775$

Question 9

(a) $(110 110 + 111) (111 111) = (110 221)$

(b) $(110 221) . (210 - 110 ( 211 - 111 ) + ( 210 - 110 )) = (110 221) . (100 200)$

Question 10

(a) $(7 20) - (7 15) = 71085$

(b) Overcounting

Question 11

(a) $m^{n}$

(b) $\frac{m !}{( m - n )!}$ if $m \geq n$ and $0$ if $m < n$

Question 12

(a) $(13 52)$

(b) $(13 52) (13 39) (13 26) (13 13)$

(c) Because each player’s hand is dependent on the on the other players’.

Question 13

$(10 52 + 10 - 1) = (10 61)$

Question 14

$(2 ( 4 * 2 ^{8} ) + 2 - 1) = (2 1025) = 1025 * 512 = 524800$

Story proofs

Question 15

Suppose a pizza can have $n$ kinds of toppings (getting no toppings is allowed, as is getting all $n$ ) therefore for each topping there are two possibilities (on or off), by multiplication rule we have $2^{n}$ possibilities. Alternatively each pizza can have $0 \leq k \leq n$ toppings, therefore for each $k$ there is $(k n)$ topping possibilities. Summing over all possible values of $k$ gives:

k = 0 \sum n (k n) = 2^{n}

As desired.

Question 16

(a)

(k n) + (k - 1 n) = \frac{n !}{( n - k )! k !} + \frac{n !}{( n - k + 1 )! ( k - 1 )!} = \frac{n !}{( k - 1 )! ( n - k )!} (\frac{1}{k} + \frac{1}{n - k + 1}) = \frac{n !}{( k - 1 )! ( n - k )!} \frac{n + 1}{k ( n + 1 - k )} = \frac{( n + 1 )!}{k ! ( n + 1 - k )!} = (k n + 1)

(b) Suppose a committee of $k$ people is chosen from a group of $n$ people plus Dave. The total number of committees is $(k n + 1)$ . Alternatively the committees can be chosen by either including or excluding Dave:

First, if Dave is included, the remaining $k - 1$ people must be chosen from the remaining $n$ people, which can be done in $(k - 1 n)$ ways.
Second, if Dave is excluded, then all the $k$ people must be chosen from the remaining $n$ people, which can be done in $(k n)$ ways.

Since these cases are disjoint and exhaustive, the total is the sum of the two:

(k - 1 n) + (k n) = (k n + 1)

As desired.

Question 17

Suppose there are two groups of $n$ people. a committee of $n$ people is chosen from these groups, the total number of committees is $(n 2 n)$ . Alternatively the committees can be chosen by focusing on:

The number of people included from the first group, $k$ .
And the number of people included from the second group $n - k$ , resulting in $(n - k n)$ possibilities; By the symmetry of the binomial coefficient, choosing $n - k$ people is equivalent to choosing $k$ people.

These result to $(k n)^{2}$ committees for each $k$ . Summing over all possible values of $k$ gives:

k = 0 \sum n (k n)^{2} = (n 2 n)

As desired.

Question 18

Suppose there are two groups of $n$ people. A committee of $n$ people is chosen from these groups, additionally a president is chosen from the first group. There are $n$ ways to choose a president from the first group, and $(n - 1 2 n - 1)$ ways to choose the remaining $n - 1$ members from the remaining $2 n - 1$ people: $n (n - 1 2 n - 1)$ . Alternatively these committees can be chosen by focusing on:

The people included from the first group, $k$ , which must be greater than $0$ because there must be a president, resulting in $(k n)$ possibilities, additionally by choosing the president the possibilities are multiplied by $k$ , resulting in $k (k n)$ possibilities.
And the people included from the second group, $n - k$ , resulting in $(n - k n)$ possibilities, which is equivalent to the number of people excluded from the second group, $k$ , resulting in $(k n)$ possibilities.

These result to $k (k n)^{2}$ committees for each fixed $k$ . Summing over all possible values of $k$ gives:

k = 1 \sum n k (k n)^{2} = n (n - 1 2 n - 1)

As desired.

Question 19

Suppose there is a set of $n + 3$ elements, ${1, 2, \dots, n + 3}$ . Choosing a subset of $5$ elements would have $(5 n + 3)$ possibilities. Alternatively each subset can be chosen by focusing on the middle element in the subset. Let the elements be ordered ${1, 2, \dots, n + 3}$ , and $(k + 1)$ th element to be the middle (3rd) element of the subset, there are $k$ elements to its left and $(n + 3) - (k + 1)$ elements to its right. then:

$2$ elements from the left side of the middle element must be chosen: $(2 k)$
And 2 elements from the right side of the middle element as well: $(2 n + 3 - k - 1) = (2 n - k + 2)$

Resulting in $(2 k) (2 n - k + 2)$ subsets. Summing over all possible values of $k$ , ( $2 \leq k \leq n$ ) gives:

k = 2 \sum n (2 k) (2 n - k + 2) = (5 n + 3)

As desired.

Question 20

(a) Suppose we have a list of $n + 1$ people ordered by age, the number $1$ being the youngest and the number $n + 1$ being the oldest; Choosing a committee of $k + 1$ people would have $(k + 1 n + 1)$ possibilities. Alternatively each committee can be chosen by focusing on the oldest member, let $i$ , $(i \geq k + 1)$ be the number of the oldest person in the committee, then we have to choose the remaining $k$ people from the $i - 1$ younger people: $(k i - 1)$ Summing over all the valid $i$ values would give:

i = k + 1 \sum n + 1 (k i - 1) = (k k) + (k k + 1) + \dots + (k n) = (k + 1 n + 1)

As desired.

(b) There are $21$ possibilities for the amount of the gummy bears inside a bag, ( ${30, 31, \dots, 50}$ ), and 5 possibilities for each flavor. Each case of amount can be modeled as Stars and Bars, $5$ bins and $n$ gummies, $(k - 1 n + k - 1) = (5 - 1 5 + n - 1) = (4 n + 4)$ possibilities for each $n$ ; giving the total possibilities of:

(4 34) + (4 35) + \dots (4 54)

by using (a):

(4 34) + (4 35) + \dots + (4 54) = (5 55) - [(4 4) + (4 5) + \dots + (4 33)]

by using (a) again:

(5 55) - [(4 4) + (4 5) + \dots + (4 33)] = (5 55) - (5 34)

Question 21

(a) Partitioning $n$ people plus Dave into $k$ groups can be noted as ${k n + 1}$ . Alternatively it can be broken into two disjoint case:

Dave is a group by itself, so there will be $n$ remaining people to be partitioned into $k - 1$ groups, therefore there are ${k - 1 n}$ possibilities.
Dave is a part of a group, there will be $k$ groups for Dave to join, therefore there are $k {k n}$ possibilities.

Therefore we have:

{k - 1 n} + k {k n} = {k n + 1}

As desired.

(b) Partitioning $n$ people plus Dave into $k$ groups and Dave’s group can be noted as ${k + 1 n + 1}$ . Alternatively each partitioning can be done by focusing on how many people are going to be in Dave’s group. Let $j$ be the number of the people not in Dave’s group, there would be $(n - j n)$ possibilities for the Dave’s group, additionally the remaining people can partitioned in ${k j}$ ways. Resulting in $(n - j n) {k j}$ ways for each $j$ , $k \leq j \leq n$ . Summing over all possible values of $j$ results in:

j = k \sum n (n - j n) {k j} = j = k \sum n (j n) {k j} = {k + 1 n + 1}

As desired.

Question 22

(a) Suppose $n + 1$ people are playing in round-robin tournament, where each player plays with any other player exactly once. To find the number of matches, we simply find all the combinations to form a match, which is $(2 n + 1)$ Alternatively the number of games can be counted by focusing on players, the first player will has to face $n$ players, the second player has to face $n - 1$ remaining players and so on. This results to:

n + (n - 1) + (n - 2) + \dots + 1 = (2 n + 1)

As desired.

(b) Consider a set of integers ${0, 1, 2, \dots, n}$ where we want to choose a number $k$ such that $k \in {1, 2, \dots, n}$ and three numbers $x, y, z$ such that $x, y, z \in {0, 1, 2, \dots, k - 1}$ . For a fixed $k$ , there are $k$ choices for $x, y$ and $z$ , summing over all possible $k$ values gives:

1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = k = 1 \sum n k^{3}

Alternatively, these numbers can be picked by focusing on how many distinct values $k$ , $x$ , $y$ and $z$ have:

4 Distinct values; Choose 4 numbers from $n + 1$ . The largest is $k$ . There are $3! = 6$ ways to assign the remaining 3 values to $x, y$ and $z$ : $6 (4 n + 1)$
3 Distinct Values; Choose 3 numbers from $n + 1$ . The largest is $k$ . One value among $x, y, z$ is repeated, or one matches $x, y, z$ in a specific pattern. There are 6 ways to arrange these: $6 (3 n + 1)$
2 Distinct Values; Choose 2 numbers from $n + 1$ . The larger is $k$ . All three of $x, y, z$ must be the smaller number. There is only 1 way to do this: $(2 n + 1)$

Therefore:

k = 1 \sum n k^{3} = 6 (4 n + 1) + 6 (3 n + 1) + (2 n + 1)

As desired.

Naive definition of probability

Question 23

Desired sets of buttons: ${2, 3, 4}, {3, 4, 5}, \dots, {8, 9, 10}$ , ( $7$ sets)

Desired combinations: $7 * 3! = 42$

All combinations: $9^{3} = 729$

Probability: $P = \frac{42}{729} = \frac{14}{243}$

Question 24

Desired combinations: $[G_{1}, G_{2}, G_{3}, M_{1}, M_{2}, M_{3}], [G_{1}, G_{3}, G_{2}, M_{1}, M_{2}, M_{3}], \dots$ resulting in $3! * 3! = 36$ combinations.

All combinations: $6! = 720$

Probability: $P = \frac{36}{720} = \frac{1}{20}$

Question 25

Undesired combinations: Where each district gets exactly one robbery, therefore there are $6! = 720$ combinations.

All combinations: $6 \times 6 \times 6 \times 6 \times 6 \times 6 = 6^{6} = 46656$

Probability: $P = 1 - (\frac{720}{46656}) = 0.0.015$

Question 26

(a) Picking one person more than once is equivalent to at least two people sharing the same birthday.

(b)

Undesired combinations: the combinations where different people are chosen each time. $1000000 \times 999999 \times \dots \times 999001 = \frac{1000000 !}{999000 !}$

All combinations: $(1000000)^{1000}$

Probability: $P = 1 - \frac{\frac{1000000 !}{999000 !}}{( 1000000 ) ^{1000}}$

Question 27

Undesired combinations: choosing $k$ locations from $n$ locations to store phone numbers without replacing: $n \times (n - 1) \times (n - 2) \times (n - k + 1) = \frac{n !}{( n - k )!}$

All combinations: $n^{k}$

Probability: $P = 1 - \frac{n !}{( n - k )! n ^{k}}$

Question 28

Undesired combinations: choosing $3$ slots from $10$ slots for statistics course without replacing: $10 \times (10 - 1) \times (10 - 2) = 720$

All combinations: $1 0^{3} = 1000$

Probability: $P = 1 - \frac{720}{1000} = 0.28$

Question 29

(a) Since the maximum total of dices is 24, this problem can be modeled as Stars and Bins, where stars are negative ones and bins are the dices with 6 on them:

21: Three negative ones and four dices: $(3 ( 4 - 1 ) + 3) = (3 6) = 20$
22: Two negative ones and four dices: $(2 ( 4 - 1 ) + 2) = (2 5) = 10$

Total number of 21 is more likely.

(b)

2-letter: $P = \frac{26}{2 6 ^{2}} = \frac{1}{26}$
3-letter: $P = \frac{26 * 26}{2 6 ^{3}} = \frac{1}{26}$

Both are equally likely.

Question 30

$n = 7$ :

Permutations: $L_{1} L_{2} L_{3} L_{4} L_{3} L_{2} L_{1}$
Desired combinations: $2 6^{4}$
All combinations: $2 6^{7}$
Probability: $P = \frac{2 6 ^{4}}{2 6 ^{7}} = \frac{1}{2 6 ^{3}}$

$n = 8$ :

Permutations: $L_{1} L_{2} L_{3} L_{4} L_{4} L_{3} L_{2} L_{1}$
Desired combinations: $2 6^{4}$
All combinations: $2 6^{8}$
Probability: $P = \frac{2 6 ^{4}}{2 6 ^{8}} = \frac{1}{2 6 ^{4}}$

Question 31

Desired combinations: $(k n) (m - k N - n)$

All combinations: $(m N)$

Probability: $P = \frac{( k n ) ( m - k N - n )}{( m N )}$

Question 32

Since guessing red cards would implicitly guess the black cards as well, it’s impossible to have 1 or 3 correct guesses (imagine guessing one red card correct and one incorrect, then the other two remaining black and red cards would be guessed as black and one of them would be a correct guess, the same goes for three).

For $j = 0$ both guesses must be wrong, resulting in one combination.
For $j = 2$ only one red card guess must be correct, leaving two red cards to choose for the correct answer and two black cards for the wrong answer, resulting in $4$ combinations.
For $j = 4$ both guesses must be correct, resulting in one combination.

The total combinations would be $(2 4) = 6$ , therefore:

$P (j = 0) = \frac{1}{6}$
$P (j = 1) = 0$
$P (j = 2) = \frac{4}{6} = \frac{2}{3}$
$P (j = 3) = 0$
$P (j = 4) = \frac{1}{6}$

Question 33

(a) Since no new information is added to the experiment by removing one ball, therefore the probability remains the same.

(b) $S = {RG, GG}$

P = P (RG) + P (GG) = (\frac{r}{r + g}) (\frac{g}{r + g - 1}) + (\frac{g}{r + g}) (\frac{g - 1}{r + g - 1}) = = \frac{r g + g ( g - 1 )}{( r + g ) ( r + g - 1 )} = \frac{g ( r + g - 1 )}{( r + g ) ( r + g - 1 )} = \frac{g}{r + g} = P (G)

Question 34

(a) $P = \frac{4 ( ( 5 13 ) - 1 )}{( 5 52 )}$

(b) $P = \frac{( 2 13 ) ( 2 4 ) ( 2 4 ) ( 1 11 ) ( 1 4 )}{( 5 52 )}$

Question 35

Desirable combinations: $4 (3 13)^{3} (4 13)$

Probability: $P = \frac{4 ( 3 13 ) ^{3} ( 4 13 )}{( 13 52 )}$

Question 36

Desirable combinations: $(5 30) (5 25) (5 20) (5 15) (5 10) (5 5)$

All combinations: $6^{30}$

Probability: $P = \frac{( 5 30 ) ( 5 25 ) ( 5 20 ) ( 5 15 ) ( 5 10 ) ( 5 5 )}{6 ^{30}}$

Question 37

(a)

Desirable combinations: Divide the deck into three parts, before-ace, the-ace, after-ace.

The first part can’t have Jack, Queen, King or Ace, leaving with 36 cards to choose from, let $i$ be the number of cards chosen.
The-ace has 4 possibilities.
The after-ace has 15 (Jack, Queen, King and 3 Aces) plus $36 - i$ cards.

These result to $i! (i 36) \times 4 \times (36 - i + 15)!$ for each $i$ , summing over all possible $i$ values gives:

4 \times i = 0 \sum 36 i! (i 36) (51 - i)! = 4 \times 36! \times i = 0 \sum 36 \frac{( 51 - i )!}{( 36 - i )!}

Probability:

\frac{4 \times 36 ! \times \sum _{i = 0}^{36} \frac{( 51 - i )!}{( 36 - i )!}}{52 !} = \frac{1}{4}

Note

This can be solved by just looking at the subset of Jacks, Queens, Kings and Aces, since only the relative order of these cards matter, therefore the probability would be the same as the probability of Ace being the first card in this subset:
$P = \frac{( 1 4 )}{( 1 16 )} = \frac{1}{4}$

(b)

Desirable combinations: Same as the note, the subset should be order as ${K Q J} {A ce} {remaining cards}$ , therefore:

3! (1 4)^{3} \times (1 4) \times 12! = 12! \times 3! \times 4^{4}

Probability:

\frac{12 ! \times 3 ! \times 4 ^{4}}{16 !} = \frac{6 \times 256}{16 \times 15 \times 14 \times 13} = \frac{16}{455}

Question 38

(a) Let’s assume Tyrion seats first, which gives $12$ combinations, then Cersei would have two desirable seats and others would be arranged in $10!$ different combinations:

P = \frac{12 \times 2 \times 10 !}{12 !} = \frac{2}{11}

(b) Let’s assume Tytion is seated, then the sample space for Cersei’s seat would be of size $11$ , there are only $2$ desirable seats, giving:

P = \frac{2}{11}

Question 39

selecting $j$ couples gives $(j n)$ combinations, now the remaining $k - 2 j$ must be selected. For that $k - 2 j$ couples are selected from the $n - j$ remaining couples, and for each couple there would be $2$ possibilities, resulting in:

P = \frac{( j n ) ( k - 2 j n - j ) 2 ^{k - 2 j}}{( k 2 n )}

Question 40

(a) For this sequence to be strictly increasing, all $k$ values must be distinct, there would be only one way to arrange them:

P = \frac{( k n )}{n ^{k}}

(b) This can be modeled as Stars and Bars, where bins are the numbers and stars are how many times they are chosen:

P = \frac{( k k + n - 1 )}{n ^{k}}

Question 41

To have exactly one empty box, the balls must be distributed such that one box has $2$ balls, one box has $0$ , and the remaining $n - 2$ boxes have $1$ ball each; There are $2 n$ ways to select the pair of balls that will share a box. We now have $n - 1$ distinct “items” to place (the $1$ pair and the $n - 2$ single balls). There are $n$ ways to choose a box for the pair, and $n - 1$ ways to choose an empty box from the remaining. The remaining $n - 2$ balls can be arranged in the remaining $n - 2$ boxes in $(n - 2)!$ ways.

(2 n) (1 n) (1 n - 1) (n - 2)! = (2 n) n!

Therefore for the sample sample space of size $n^{n}$ :

P = \frac{( 2 n ) n !}{n ^{n}}

Question 42

The probability is defined as the number of permutations of $26$ letters divided by the total sum of all possible permutations of length $i$ , where $i$ ranges from $1$ to $26$ :

P = \frac{26 ! ( 26 26 )}{\sum _{i = 1}^{26} i ! ( i 26 )} = \frac{1}{\sum _{i = 1}^{26} \frac{1}{( 26 - i )!}} = \frac{1}{\sum _{k = 0}^{25} \frac{1}{k !}} \approx \frac{1}{e}

Axioms of probability

Question 43

(a) $P (A) + P (B) - 1 \leq P (A \cap B)$ : From the properties of probability we have:

P (A \cup B) = P (A) + P (B) - P (A \cap B)

Additionally we know $0 \leq P \leq 1$ , therefore $P (A \cup B) \leq 1$ , thus:

P (A) + P (B) - P (A \cap B) \leq 1 ⟹ P (A) + P (B) - 1 \leq P (A \cap B)

As desired.

Equality: suppose $A \cup B = S$ , then $P (A \cup B) = 1$ , therefore, from the property:

1 = P (A) + P (B) - P (A \cap B) ⟹ P (A \cap B) = P (A) + P (B) - 1

(b) $P (A \cap B) \leq P (A \cup B)$ : From the properties of probability we have:

if A \subseteq B, then P (A) \leq P (B)

Since $(A \cap B) \subseteq (A \cup B)$ , therefore:

P (A \cap B) \leq P (A \cup B)

As desired.

Equality: if $A = B$ then $A \cap B = A \cup B$ , therefor:

P (A \cap B) = P (A \cup B)

(c) $P (A \cup B) \leq P (A) + P (B)$ : From the properties of probability we have:

P (A \cup B) = P (A) + P (B) - P (A \cap B) ⟹ P (A \cap B) = P (A) + P (B) - P (A \cup B)

Additionally we know $0 \leq P \leq 1$ , therefore $0 \leq P (A \cap B)$ , thus:

0 \leq P (A) + P (B) - P (A \cup B) ⟹ P (A \cup B) \leq P (A) + P (B)

As desired.

Equality: If $A \cap B = ϕ$ from the axioms we have:

P (A \cup B) = P (A) + P (B)

Question 44

Since $B - A$ and $A$ are disjoint sets, from the axiom of additivity we have:

P ((B - A) \cup A) = P (B - A) + P (A)

Since $A \subseteq B$ , therefore $(B - A) \cup A = B$ , thus:

P (B) = P (B - A) + P (A) ⟹ P (B - A) = P (B) - P (A)

As desired.

Question 45

Since $(A Δ B) = (A \cup B) - (A \cap B)$ , therefore $(A Δ B) \cup (A \cap B) = (A \cup B)$ . Since $(A Δ B)$ and $(A \cap B)$ are disjoint sets, from the axiom of additivity we have:

P ((A Δ B) \cup (A \cap B)) = P (A Δ B) + P (A \cap B)

Thus from the first equation:

P (A \cup B) = P (A Δ B) + P (A \cap B) ⟹ P (A Δ B) = P (A \cup B) - P (A \cap B)

From the properties we have $P (A \cup B) = P (A) + P (B) - P (A \cap B)$ , therefore:

P (A Δ B) = P (A) + P (B) - 2 P (A \cap B)

As desired.

Question 46

By definition we have:

$C_{k}$ : The event that $k, k + 1, k + 2, \dots,$ or $n$ events occur.
$C_{k + 1}$ : The event that $k + 1, k + 2, \dots,$ or $n$ events occur.
$B_{k}$ : The event that exactly $k$ events occur.

And since $B_{k}$ and $C_{k + 1}$ are disjoint events we have:

C_{k} = C_{k + 1} \cup B_{k} ⟹ P (C_{k}) = P (C_{k + 1} \cup B_{k}) = P (C_{k + 1}) + P (B_{k})

Which can be rewritten as:

P (B_{k}) = P (C_{k}) - P (C_{k + 1})

Question 47

(a) Probability of number 6 appearing after rolling a dice ( $P (A) = \frac{1}{6}$ ) and probability of number 5 appearing after rolling a second dice ( $P (B) = \frac{1}{6}$ ); $P (A \cap B)$ is the probability of the first one being 6 and second one being 5 ( $[6, 5]$ ) which is $\frac{1}{36}$ , thus:

P (A \cap B) = \frac{1}{36} = P (A) P (B) = \frac{1}{36}

(b) Whenever the common area between $A_{1}$ and $B_{1}$ is equal to $A_{1} B_{1}$ then $A$ and $B$ would be independent, an example:

Common area of A_{1} and B_{1} = \frac{1}{4} and A_{1} = B_{1} = \frac{1}{2} ⟹ P (A \cap B) = P (A) P (B)

An example of $A$ and $B$ not being independent:

Common area of A_{1} and B_{1} = 0 and A_{1} = B_{1} = \frac{1}{2} ⟹ P (A \cap B) \neq = P (A) P (B)

(c)

P (A \cup B) = P (A) + P (B) - P (A \cap B)

Since $A$ and $B$ are independent, therefore $P (A \cap B) = P (A) P (B)$ , thus:

P (A \cup B) = P (A) + P (B) - P (A) P (B) = P (A) [1 - P (B)] + P (B) = P (A) P (B^{c}) + (1 - P (B^{c})) = 1 + P (B^{c}) (P (A) - 1) = 1 - P (A^{c}) P (B^{c})

Question 48

Since for Arby $P_{A r b y} (A \cup B) \neq = P_{A r b y} (A) + P_{A r b y} (B)$ , for any disjoint events $A$ and $B$ , therefore we have two cases:

1. P_{A r b y} (A \cup B) > P_{A r b y} (A) + P_{A r b y} (B)

In this case we can do these series of actions repetitively until Arby goes bankrupt:

Sell $A$ and $B$ certificates for $1000 (P_{A r b y} (A) + P_{A r b y} (B))$
Buy $A \cup B$ certificate for $1000 (P_{A r b y} (A \cup B))$

Since $P_{A r b y} (A \cup B) > P_{A r b y} (A) + P_{A r b y} (B)$ , Arby loses money.

2. P_{A r b y} (A \cap B) > P_{A r b y} (A) + P_{A r b y} (B)

In this case we can do these series of actions repetitively until Arby goes bankrupt:

Buy $A \cup B$ certificate for $1000 (P_{A r b y} (A \cup B))$
Sell $A$ and $B$ certificates for $1000 (P_{A r b y} (A) + P_{A r b u} (B))$

Since $P_{A r b y} (A \cup B) < P_{A r b y} (A) + P_{A r b y} (B)$ , Arby loses money.

Inclusion-exclusion

Question 49

Let $A_{i}$ be the event where the number $i$ never appears, therefore for events $A_{1}, A_{2}, \dots, A_{n}$ we have:

P (i = 1 ⋃ 6 A_{i}) = i = 1 \sum 6 (- 1)^{i + 1} (i 6) (\frac{6 - i}{6})^{n}

Thus:

P (i = 1 ⋃ 6 A_{i}) = (1 6) (\frac{5}{6})^{n} - (2 6) (\frac{4}{6})^{n} + (3 6) (\frac{3}{6})^{n} - (4 6) (\frac{2}{6})^{n} + (5 6) (\frac{1}{6})^{n} = 6 (\frac{5}{6})^{n} - 15 (\frac{4}{6})^{n} + 20 (\frac{3}{6})^{n} - 15 (\frac{2}{6})^{n} + 6 (\frac{1}{6})^{n}

Question 50

Let $D_{i}$ be the events where a hand is void in the respective suit ( $i$ being Hearts, Clubs, Spades or Diamonds), therefore:

P (i = 1 ⋃ 4 D_{i}) = i = 1 \sum 4 (- 1)^{i + 1} (i 4) (\frac{( 13 52 - 13 i )}{( 13 52 )})

Thus:

P (i = 1 ⋃ 4 D_{i}) = \frac{4 ( 13 39 )}{( 13 52 )} - \frac{6 ( 13 26 )}{( 13 52 )} + \frac{4 ( 13 13 )}{( 13 52 )} \approx 0.051

Question 51

Let $A_{i}$ be the event that season $i$ occurs at least once each among birthdays, so the probability of all seasons occurring at least once each among birthdays would be:

P (i = 1 ⋂ 4 A_{i})

By using De-Morgan’s law we have:

P (i ⋂ 4 A_{i}) = 1 - P (i = 1 ⋃ 4 A_{i}^{c})

Where $A_{i}^{c}$ is the event of season $i$ not occurring at all among birthdays, which:

P (intersection of i events) = (\frac{4 - i}{4})^{7}

By using Inclusion-Exclusion we have:

1 - P (i = 1 ⋃ 4 A_{i}^{c}) = 1 - [i = 1 \sum 4 (- 1)^{i + 1} (i 4) (\frac{4 - i}{4})^{7}] = 1 - 4 (\frac{3}{4})^{7} + 6 (\frac{2}{4})^{7} - 4 (\frac{1}{4})^{7} \approx 0.513

Question 52

Let $A_{i}$ be the event that student $i$ doesn’t sit in the same place, therefore the probability of no student sitting in the same place would be:

P (i = 1 ⋂ 20 A_{i})

By De-Morgan’s law we have:

P (i = 1 ⋂ 20 A_{i}) = 1 - P (i = 1 ⋃ 20 A_{i}^{c})

Where $A_{i}^{c}$ is the event that student $i$ sits in the same place, which gives:

P (intersection of i events) = \frac{20 !}{( 20 - i )!} ​

By inclusion-exclusion we have:

1 - P (i = 1 ⋃ 20 A_{i}^{c}) = 1 - [i = 1 \sum 20 (- 1)^{i + 1} (i 20) \frac{( 20 - i )!}{20 !}] = 1 - [i = 1 \sum 20 (- 1)^{i + 1} \frac{1}{i !}] = 1 - [\frac{1}{1 !} - \frac{1}{2 !} + \frac{1}{3 !} - \dots - \frac{1}{20 !}] \approx \frac{1}{e} \approx 0.3679

Question 53

Let:

S be the set of all passwords.
$L$ be the set of passwords that have at least one lower case character.
$U$ be the set of passwords that have at least one upper case character.
$N$ be the set of passwords that have at least one number.

Therefore:

$L^{c}$ is the set of passwords that have no lower case characters.
$U^{c}$ be the set of passwords that have no upper case characters.
$N^{c}$ be the set of passwords that have no numbers.

(a)

∣ L ∣ = ∣ S - L^{c} ∣

since $L^{c} \subseteq S$ , therefore:

∣ S - L^{c} ∣ = ∣ S ∣ - ∣ L^{c} ∣ = 6 2^{8} - 3 6^{8}

(b)

∣ L \cap U ∣ = ∣ S - (L^{c} \cup U^{c}) ∣

since $L^{c} \cup U^{c} \subseteq S$ , therefore:

∣ S - (L^{c} \cup U^{c}) ∣ = ∣ S ∣ - ∣ (L^{c} \cup U^{c}) ∣

By inclusion-exclusion:

∣ S ∣ - ∣ (L^{c} \cup U^{c}) ∣ = ∣ S ∣ - [∣ L^{c}] + ∣ U^{c} ∣ - ∣ L^{c} \cap U^{c} ∣] = 6 2^{8} - [3 6^{8} + 3 6^{8} - 1 0^{8}]

(c)

∣ L \cap U \cap N ∣ = ∣ S - (L^{c} \cup U^{c} \cup N^{c}) ∣

since $L^{c} \cup U^{c} \cup N^{c} \subseteq S$ , therefore:

∣ S - (L^{c} \cup U^{c} \cup N^{c}) ∣ = ∣ S ∣ - ∣ (L^{c} \cup U^{c} \cup N^{c}) ∣

By inclusion-exclusion:

∣ S ∣ - ∣ (L^{c} \cup U^{c} \cup N^{c}) ∣ = ∣ S ∣ - [∣ L^{c}] + ∣ U^{c} ∣ + ∣ N^{c} ∣ - ∣ L^{c} \cap U^{c} ∣ - ∣ L^{c} \cap N^{c} ∣] - ∣ U^{c} \cap N^{c} ∣ + ∣ L^{c} \cap U^{c} \cap N^{c} ∣] = 6 2^{8} - [3 6^{8} + 3 6^{8} + 5 2^{8} - 1 0^{8} - 2 6^{8} - 2 6^{8} + 0]

Question 54

Let $A_{i}$ be the event that day $i$ has at least one class, therefore the probability of having classes everyday would be:

P (i = 1 ⋂ 5 A_{i})

By De-Morgan’s law we have:

P (i = 1 ⋂ 5 A_{i}) = 1 - P (i = 1 ⋃ 5 A_{i}^{c})

Where $A_{i}^{c}$ is the event that day $i$ has no class at all, which gives:

P (intersection of j events) = \frac{( 7 30 - 6 j )}{( 7 30 )} ​

By inclusion-exclusion we have:

1 - P (i = 1 ⋃ 5 A_{i}^{c}) = 1 - [i = 1 \sum 5 (- 1)^{i + 1} (i 5) \frac{( 7 30 - 6 i )}{( 7 30 )}] = 1 - \frac{1}{( 7 30 )} [5 (7 24) - 10 (7 18) + 10 (7 12)]

Question 55

(a)

P = \frac{( 3 15 ) ( 2 22 )}{( 5 37 )}

(b) Let:

$A$ be the event that at least one senior is in the group.
$B$ be the event that at least one junior is in the group.
$C$ be the event that at least one sophomore is in the group.

Therefore, the probability that the committee has at least one representative from each of the senior, junior, and sophomore classes would be:

P (A \cap B \cap C)

By De-Morgan’s law:

P (A \cap B \cap C) = 1 - P (A^{c} \cup B^{c} \cup C^{c})

Where $A^{c}$ , $B^{c}$ and $C^{c}$ are the events that no senior, junior and sophomore is in the group respectively. By inclusion-exclusion we have:

1 - P (A^{c} \cup B^{c} \cup C^{c}) = 1 - [P (A^{c}) + P (B^{c}) + P (C^{c}) - P (A^{c} \cap B^{c}) - P (A^{c} \cap C^{c}) - P (B^{c} \cap C^{c}) + P (A^{c} \cap B^{c} \cap C^{c})] = 1 - \frac{1}{( 5 37 )} [(5 27) + (5 25) + (5 22) - (5 15) - (5 12) - (5 10)]

Mixed practice

Question 56

(a)

(5 10) > (6 10)

(b)

\frac{( 5 10 ) ( 5 5 )}{2 !} < (6 10) (4 4)

(c)

(\frac{1}{365})^{3} < \frac{1}{365} \times \frac{2}{365} \times \frac{3}{365}

(d) Martin can only win only if the games starts with $HH$ , probability of $\frac{1}{4}$ . If anywhere in the a game $T$ appears, he loses.

(probability that Martin wins) = \frac{1}{4} < \frac{1}{2}

Question 57

Let $A$ be the event where no Caesar molecule is inhaled, therefore the probability that at least one molecule in the breath was shared with Caesar’s last breath would be:

P (A^{c}) = 1 - P (A)

Since our breath is sampled with replacement the probability would be:

1 - P (A) = 1 - (\frac{1 0 ^{44} - 1 0 ^{22}}{1 0 ^{44}})^{1 0^{22}} = 1 - (1 + \frac{- 1}{1 0 ^{22}})^{1 0^{22}} \approx 1 - e^{- 1} \approx 0.632

Question 58

(a) Let $A$ be the event that the third defective widget is in the $n \geq 9$ position; this is the same as the event that the inspector has to test at least 9 widgets to find the defective widgets. The complement, $A^{c}$ , is the event that all defective widgets are in $n \leq 8$ position, which gives:

P (A) = 1 - P (A^{c}) = 1 - \frac{( 3 8 )}{( 3 12 )}

(b) Same as (a):

P (A) = 1 - P (A^{c}) = 1 - \frac{( 3 10 )}{( 3 12 )}

Question 59

(a) It can be modeled as Stars and Bins, with bins being kids and stars being the chocolates:

(10 - 1 15 + 10 - 1) = (9 24)

(b) Again, same as the previous, but with 5 chocolates this time:

(10 - 1 5 + 10 - 1) = (9 14)

(c) Each chocolate has 15 choices:

1 0^{15}

(d) Let $S$ be the sample space and $A_{i}$ be the event where person $i$ receives at least one chocolate, therefore the event where every child gets one chocolate would be:

i = 1 ⋂ 10 A_{i}

since $A = S - A^{c}$ , by De-Morgan’s law we have:

i = 1 ⋂ 10 A_{i} = S - i = 1 ⋃ 10 A_{i}^{c}

where $A_{i}^{c}$ is the event that person $i$ gets no chocolate, which gives:

∣ intersection of j events ∣ = (10 - j)^{15}

Since $⋃_{i = 1}^{10} A_{i}^{c} \subseteq S$ , therefore:

∣ S - i = 1 ⋃ 10 A_{i}^{c} ∣ = ∣ S ∣ - ∣ i = 1 ⋃ 10 A_{i}^{c} ∣

By inclusion-exclusion we have:

∣ S ∣ - ∣ i = 1 ⋃ 10 A_{i}^{c} ∣ = ∣ S ∣ - [i = 1 \sum 10 (- 1)^{i + 1} (i 10) (10 - i)^{15}] = 1 0^{15} - (1 10) 9^{15} + (2 10) 8^{15} - (3 10) 7^{15} + \dots - (9 10) 1^{15}

Question 60

(a)

n^{n}

(b) This can be modeled as Stars and Bins, where bins are the $a_{i}$ ‘s and stars are the times a number was chosen.

(n - 1 n + n - 1) = (n - 1 2 n - 1)

(c) Let $n_{i}$ be the number of times $a_{i}$ is chosen, $\sum n_{i} = n$ . imagine an unordered bootstrap example:

(a_{1}, a_{1}, a_{1}, a_{2}, a_{2}, a_{2}, a_{3}, a_{3}, a_{3}, a_{4}, a_{4}, a_{4}, a_{5}, a_{5}, a_{5})

where:

n_{1} = n_{2} = n_{3} = n_{4} = n_{5} = 3

Let $∣ S ∣$ be the number of all possibilities, this particular unordered bootstrap would have the probability of:

P = \frac{1}{∣ S ∣} \times \frac{15 !}{Π _{i = 1}^{15} n _{i} !}

Where $∣ S ∣ = n^{n}$ , now this can be further generalized to:

P = \frac{1}{n ^{n}} \times \frac{n !}{Π _{i = 1}^{n} n _{i} !}

This results to:

\frac{p _{1}}{p _{2}} = \frac{Π _{i = 1}^{n} n _{2_{i}} !}{Π _{i = 1}^{n} n _{1_{i}} !}

example: Let $b_{1}$ be the unordered bootstrap $(a_{1}, a_{1}, \dots, a_{1})$ and $b_{2}$ be the unordered bootstrap $(a_{1}, a_{2}, \dots, a_{n})$ , and let $p_{1}$ and $p_{2}$ be the probability of getting $b_{1}$ and $b_{2}$ , therefore:

\frac{p _{1}}{p _{2}} = \frac{Π _{i = 1}^{n} n _{2_{i}} !}{Π _{i = 1}^{n} n _{1_{i}} !} = \frac{1 ! \times 1 ! \times \dots \times 1 !}{n ! \times 1 ! \times 1 ! \times \dots \times 1 !} = \frac{1}{n !}

Question 61

Note

The probability is 1/2. This is because, for the last passenger, only two seats truly matter: their own assigned seat (Seat 100) and the first passenger’s assigned seat (Seat 1). Any passenger who finds their seat taken will eventually choose one of these two seats with equal probability. If Seat 1 is chosen first, the “chain” of displaced passengers ends and the last passenger gets their seat; if Seat 100 is chosen first, they do not. Since the process is perfectly symmetric regarding these two seats, the chance of the last passenger finding their seat available is exactly 50%.

Question 62

(a)

P = 1 - 1 \leq j_{1} < j_{2} < \cdot\cdot\cdot < j_{k} \leq 365 \sum k! \times p_{j_{1}} p_{j_{2}} \dots p_{j_{k}} = 1 - k! \times e_{k} (p_{1}, p_{2}, \dots p_{365})

(b) Suppose there are only two people and there only two days to choose from, the probability of these two people sharing birthday would be:

P = p_{1}^{2} + p_{2}^{2} = p_{1}^{2} + (1 - p_{1})^{2} = 2 p_{1}^{2} + 1 - 2 p_{1}

$P$ would have the minimum amount where $\frac{d P}{d p _{1}} = 0$ , Thus:

\frac{d P}{d p _{1}} = 4 p_{1} - 2 = 0 ⟹ p_{1} = \frac{1}{2} ⟹ p_{2} = \frac{1}{2}

Showing that the probability is minimized when the probability of days are uniform.

(c) This question is essentially asking if averaging two probabilities would decrease the probability of birthdays matching, a more general form for (b). Verifying the equation:

e_{k} (x_{1}, ..., x_{n}) = x_{1} x_{2} e_{k - 2} (x_{3}, ..., x_{n}) + (x_{1} + x_{2}) e_{k - 1} (x_{3}, ..., x_{n}) + e_{k} (x_{3}, ..., x_{n})

Terms containing both $x_{1}$ and $x_{2}$ : $x_{1} x_{2} e_{k - 2} (x_{3}, ..., x_{n})$
Terms containing exactly one of $x_{1}$ or $x_{2}$ : $(x_{1} + x_{2}) e_{k - 1} (x_{3}, ..., x_{n})$
Terms containing neither $x_{1}$ nor $x_{2}$ : $e_{k} (x_{3}, ..., x_{n})$

from (a) we have:

P (match ∣ p) \geq P (match ∣ r) ⟹ 1 - k! e_{k} (p) \geq 1 - k! e_{k} (r) ⟹ e_{k} (r) \geq e_{k} (p)

Thus, to show $P (match ∣ p) \geq P (match ∣ r)$ we must show $e_{k} (r) \geq e_{k} (p)$ . Let $E_{k} = e_{k} (p_{3}, \dots, p_{365})$ , by using the equation we just verified we have:

r_{1} r_{2} \times E_{k - 2} + (r_{1} + r_{2}) \times E_{k - 1} \geq p_{1} p_{2} \times E_{k - 2} + (p_{1} + p_{2}) \times E_{k - 1}

since $r_{1} = r_{2} = \frac{p _{1} + p _{2}}{2}$ , therefore:

(\frac{p _{1} + p _{2}}{2})^{2} \times E_{k - 2} \geq p_{1} p_{2} \times E_{k - 2} ⟹ \frac{p _{1} + p _{2}}{2} \geq p_{1} p_{2}

Which is always correct for any $p_{1}, p_{2} \geq 0$ by arithmetic mean-geometric mean inequality, thus proving $P (match ∣ p) \geq P (match ∣ r)$ .

Study Archive

Solutions 1 - Probability and Counting

Counting

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

Question 14

Story proofs

Question 15

Question 16

Question 17

Question 18

Question 19

Question 20

Question 21

Question 22

Naive definition of probability

Question 23

Question 24

Question 25

Question 26

Question 27

Question 28

Question 29

Question 30

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40

Question 41

Question 42

Axioms of probability

Question 43

Question 44

Question 45

Question 46

Question 47

Question 48

Inclusion-exclusion

Question 49

Question 50

Question 51

Question 52

Question 53

Question 54

Question 55

Mixed practice

Question 56

Question 57

Question 58

Question 59

Question 60

Question 61

Question 62