Counting and Probability

Toolkit

Counting

• Product Rule: Consider two independent tasks. If there are $a$ ways of completing one task and $b$ ways of completing another task, then there are $ab$ ways of completing both tasks.

• Sum Rule: If a task can be completed in $a$ ways or $b$ ways where there is no overlap between these two ways, then the number of ways to complete the task is $a+b$.

• Principle of Inclusion-Exclusion (Subtraction Rule): If a task can be completed in $a$ ways or $b$ ways and there are $c$ ways that are common to both, then the number of ways to complete the task is $a+b-c$.

• Complementary Counting: If there are $a$ items in a set satisfying a given property, then $$a=(\text{total number of items in the set})-(\text{number of items which do not satisfy the given property})$$

• The number of ways to arrange $n$ distinct objects is $n!=n(n-1)(n-1)\cdots (3)(2)(1)$. Note that $0!=1$.

• The number of ways to select $k$ objects from $n$ distinct objects is ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})={\displaystyle \frac{n!}{(n-k)!k!}}}$.

• Pigeonhole Principle: Let $k$ be a positive integer. If $k+1$ objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

Probability

Let $A$ be the set of possible outcomes satisfying a given condition. We write $\bar{A}$ to represent the set of possible outcomes which are not in set $A$. Let $B$ be the set of possible outcomes satisfying another condition.

• If all outcomes are equally likely, then the probability of event $A$ is $$P(A)={\displaystyle \frac{\text{number of outcomes in }A}{\text{total number of possible outcomes}}}$$

• $P(A)=1-P(\bar{A})$

• If $A$ and $B$ are independent events (the occurrence of one event has no effect on the other event), then $P(A\text{ and }B)=P(A)P(B)$.

• $P(A\text{ or }B)=P(A)+P(B)-P(A\text{ and }B)$

Sample Problems

1. How many positive $4$-digit numbers begin with an odd digit or are divisible by $5$?

   Solution

   We start by determining the number of $4$-digit numbers that begin with an odd digit. There are $5$ choices for the first digit and $10$ choices for each of the remaining $3$ digits. Therefore, there are $5(10)(10)(10)=5000$ $4$-digit numbers that begin with an odd digit.

   Next, we determine the number of $4$-digit numbers that are divisible by $5$. An integer is divisible by $5$ exactly when its final digit is $0$ or $5$. Therefore, there are $9$ choices for the first digit since we can’t use the digit $0$, $10$ choices for the second and third digits, and $2$ choices for the final digit. Thus, there are $9(10)(10)(2)=1800$ $4$-digit numbers that are divisible by $5$.

   However, there is some overlap between these two sets. The number of $4$-digit numbers that begin with an odd digit and are divisible by $5$ are $5(10)(10)(2)=1000$.

   Therefore, the total number of positive $4$-digit numbers that begin with an odd digit or are divisible by $5$ is $5000+1800-1000=5800$.

2. How many $5$-person committees can be selected from six teachers and eight students if there must be at least two students included?

   Solution 1

   The number of committees with no restrictions is $(\genfrac{}{}{0ex}{}{14}{5})=2002.$

   The number of committees with no students is $(\genfrac{}{}{0ex}{}{6}{5})(\genfrac{}{}{0ex}{}{8}{0})=6(1)=6$.

   The number of committees with one student is $(\genfrac{}{}{0ex}{}{6}{4})(\genfrac{}{}{0ex}{}{8}{1})=15(8)=120$.

   Therefore, the number of committees with at least two students is $2002-6-120=1876$.

   Solution 2

   The number of committees with $r$ students is $(\genfrac{}{}{0ex}{}{6}{5-r})(\genfrac{}{}{0ex}{}{8}{r})$. Therefore, the number of committees with at least two students is $$(\genfrac{}{}{0ex}{}{6}{3})(\genfrac{}{}{0ex}{}{8}{2})+(\genfrac{}{}{0ex}{}{6}{2})(\genfrac{}{}{0ex}{}{8}{3})+(\genfrac{}{}{0ex}{}{6}{1})(\genfrac{}{}{0ex}{}{8}{4})+(\genfrac{}{}{0ex}{}{6}{0})(\genfrac{}{}{0ex}{}{8}{5})=(20)(28)+15(56)+6(70)+1(56)=1876$$

3. If you put $15$ different pairs of socks into a drawer and then randomly choose one sock at a time, how many socks must you choose before you are guaranteed to have a matching pair of socks?

   Solution

   You must choose $16$ socks. The first $15$ socks you choose could all be different. But the pigeonhole principle guarantees that with $16$ socks and $15$ types, there must be two socks of the same type. Therefore, you are guaranteed a matching pair.

4. A die with the numbers $1$, $2$, $3$, $4$, $6$ and $8$ on its six faces is rolled. If an odd number is rolled, then all odd numbers on the die are doubled. If an even number is rolled, all even numbers on the die are halved. If the given die changes in this way, what is the probability that a $2$ will be rolled on the second roll of the die?

   Solution

   There are two possibilities for the first roll. It could be even or odd.

   Case 1: first roll is odd

   The probability of an odd roll is ${\displaystyle \frac{2}{6}}={\displaystyle \frac{1}{3}}.$

   After doubling all the odd numbers, the faces on the die are $2$, $2$, $6$, $4$, $6$, $8$. Therefore, the probability of rolling a $2$ with these faces is ${\displaystyle \frac{2}{6}}={\displaystyle \frac{1}{3}}.$ Thus, the probability of rolling an odd number on the first roll and a $2$ on the second roll is ${\displaystyle \frac{1}{3}}\times {\displaystyle \frac{1}{3}}={\displaystyle \frac{1}{9}}$.

   Case 2: first roll is even

   The probability of an even roll is ${\displaystyle \frac{4}{6}}={\displaystyle \frac{2}{3}}.$

   After halving all the even numbers, the faces on the die are $1$, $1$, $3$, $2$, $3$, $4$. Therefore, the probability of rolling a $2$ with these faces is ${\displaystyle \frac{1}{6}}.$ Thus, the probability of rolling an even number on the first roll and a $2$ on the second roll is ${\displaystyle \frac{2}{3}}\times {\displaystyle \frac{1}{6}}={\displaystyle \frac{1}{9}}$.

   These cases have no overlap and so we can just add their probabilities. Therefore, the probability of rolling a $2$ on the second roll is ${\displaystyle \frac{1}{9}}+{\displaystyle \frac{1}{9}}={\displaystyle \frac{2}{9}}$.

5. The integers $1$, $2$, $3$, $4$, $5$, $6$, $7$ are arranged at random to form a $7$-digit number. What is the probability that the number formed is less than $3200000$?

   Solution:

   The number formed is less than $3200000$ if one of two cases occurs: (i) the first digit is $1$ or $2$ or (ii) the first digit is $3$ and the second digit is $1$. The probability that the first digit is $1$ or $2$ is ${\displaystyle \frac{2}{7}}$. The probability that the first digit is $3$ is ${\displaystyle \frac{1}{7}}$. The probability that the second digit is $1$ given that the first digit is $3$ is ${\displaystyle \frac{1}{6}}$. Therefore, the probability that the first digit is $3$ and the second digit is $1$ is ${\displaystyle \frac{1}{7}}\times {\displaystyle \frac{1}{6}}={\displaystyle \frac{1}{42}}$.

   These cases have no overlap and so we can just add their probabilities. Therefore, the probability that the number formed is less than $3200000$ is ${\displaystyle \frac{2}{7}}+{\displaystyle \frac{1}{42}}={\displaystyle \frac{13}{42}}$.

6. If $5$ fair coins are tossed, what is the probability that at least two of them are heads?

   Solution:

   Since there are five coins and each coin has two options, there are $2^5=32$ outcomes. It is easier to count the number of outcomes that do not have at least two heads and then subtract this from the total number of outcomes. These outcomes will have no heads or exactly one head. There is only one outcome with no head. There are five outcomes with exactly one head, as the head could be any of the five coins. Therefore, the probability that at least two of the coins are heads is ${\displaystyle \frac{32-(1+5)}{32}}={\displaystyle \frac{13}{16}}$.

Problem Set

1. Let $a$, $b$, $c$, $d$, $e$ be five distinct positive integers. Show that we can choose three of these integers such that their sum is divisible by $3$.

2. A permutation of a list of numbers is an ordered arrangement of the numbers in that list. For example, $3$, $2$, $4$, $1$, $6$, $5$ is a permutation of $1$, $2$, $3$, $4$, $5$, $6$. We can write this permutation as $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, where $a_1=3$, $a_2=2$, $a_3=4$, $a_4=1$, $a_5=6$, and $a_6=5$. Determine the average value of $$a_1-a_2+a_3-a_4+a_5-a_6+a_7$$ over all permutations $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$ of $1$, $2$, $3$, $4$, $5$, $6$, $7$.

3. Three different numbers are chosen at random from the set $\{1,2,3,4,5\}$. The numbers are arranged in increasing order. What is the probability that the resulting sequence is an arithmetic sequence?

4. How many positive integers less than $1000$ have only odd digits?

5. Tanner has two identical dice. Each die has six faces which are numbered $2$, $3$, $5$, $7$, $11$, $13$. When Tanner rolls the two dice, what is the probability that the sum of the numbers on the top faces is a prime number?

6. Blaise and Pierre will play $6$ games of squash. Since they are equally skilled, each is equally likely to win any given game. (In squash, there are no ties.) The probability that each of them will win $3$ of the $6$ games is $\frac{5}{16}$ . What is the probability that Blaise will win more games than Pierre?

7. A bag contains $40$ balls, each of which is black or gold. Feridun reaches into the bag and randomly removes two balls. Each ball in the bag is equally likely to be removed. If the probability that two gold balls are removed is $\frac{5}{12}$ , how many of the $40$ balls are gold?

8. An integer $n$, with $100\le n\le 999$, is chosen at random. What is the probability that the sum of the digits of $n$ is $24$?

9. Billy and Crystal each have a bag of $9$ balls. The balls in each bag are numbered from $1$ to $9$. Billy and Crystal each remove one ball from their own bag. Let $b$ be the sum of the numbers on the balls remaining in Billy’s bag. Let $c$ be the sum of the numbers on the balls remaining in Crystal’s bag. Determine the probability that $b$ and $c$ differ by a multiple of $4$.

10. Oi-Lam tosses three fair coins and removes all of the coins that come up heads. Then she tosses the coins that remain, if any. Determine the probability that she tosses exactly one head on the second toss.

11. Two bags each contain $10$ balls, labelled with the positive integers from $1$ to $10$. Pierre removes one ball from each bag. (In each bag, each ball is equally likely to be chosen.) Determine the probability that the product of the numbers on the two balls that he chooses is divisible by $10$.

12. The string $AAABBBAABB$ is a string of ten letters, each of which is $A$ or $B$, that does not include the consecutive letters $ABBA$.

    The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$.

    Determine, with justification, the total number of strings of ten letters, each of which is $A$ or $B$, that do not include the consecutive letters $ABBA$.

13. For each positive integer $N$, an Eden sequence from $\{1,2,3,\dots ,N\}$ is defined to be a sequence that satisfies the following conditions:

    • each of its terms is an element of the set of consecutive integers $\{1,2,3,\dots ,N\}$,

    • the sequence is increasing, and

    • the terms in odd numbered positions are odd and the terms in even numbered positions are even.

    For example, the four Eden sequences from $\{1,2,3\}$ are

    • $1$

    • $3$

    • $1$,$2$

    • $1$,$2$,$3$

    Determine the number of Eden sequences from $\{1,2,3,4,5\}$.

14. Suppose there are $n$ plates equally spaced around a circular table. Ross wishes to place an identical gift on each of $k$ plates, so that no two neighbouring plates have gifts. Let $f(n,k)$ represent the number of ways in which he can place the gifts. For example $f(6,3)=2$, as shown below.

    

    1. Determine the value of $f(7,3)$.

    2. Prove that $f(n,k)=f(n-1,k)+f(n-2,k-1)$ for all integers $n\ge 3$ and $k\ge 2$.