Chapter 1 Basic Counting
Exercises Practice Problems
1. Elvis at the Diner.
Elvis is going to have lunch at this favorite diner. Here is the menu.
For lunch, Elvis wants something to eat and something to drink. How many different options does he have? (Ignore the hot tog toppings for now.) Solution.
There are 5 burgers options , 2 hot dog options, and 5 wrap options. So there are a total of \(5 + 2 + 5 = 12\) food options. There are five kinds of shakes, so there are a total of \(12 \times 5 = 60\) ways to order lunch (ignoring the hot dog toppings).
If Elvis orders a hot dog, he has the option to add extra toppings. So how many ways are there to order footlong hot dog? Solution.
There are four extra toppings. Elvis can choose any combination of them, or none at all. So the number of ways to order a foot long hot dog is \(2^4=16\text{.}\)
2. Minnesota License Plates.
A Minnesota license plate consists of three numbers followed by three letters.
How many possible license plates are there? Solution.
\begin{equation*} 10^3 \cdot 26^3 \end{equation*}Decorum dictates that some three-letter combinations be outlawed. For each outlawed three-letter combination, how many possible license plates are removed from circulation? Solution.
\begin{equation*} 10^3 \end{equation*}
3. Arithmetic Problems.
How many arithmetic problems of the following form are possible. You must use each of the digits 1 through 9, in numerical order from left to right. You can use any combination of \(+\) and \(\times\) symbols, as long as the expression makes sense. For example, \(1234+56789\) and \(12 \times 3 + 4 \times 5678 \times 9\) and \(123456789\) are valid, but \(123 \times \times 4567 + 89\) is not. Solution.
There are eight spaces between the digits. For each space we have three choices: nothing, \(+\) or \(\times\text{.}\) Therefore, the total number of arithmetic problems is \(3^8\text{.}\)
4. Subsets of Numbers.
How many numbers from \(1000\) to \(9999\) are odd? Solution.
\begin{equation*} \underbrace{5}_{\mbox{choose 4th digit}} \times \underbrace{9}_{\mbox{choose 1st digit}} \times \underbrace{10}_{\mbox{choose 2nd digit}} \times \underbrace{10}_{\mbox{choose 3rd digit}} \end{equation*}How many odd numbers from \(1000\) to \(9999\) have distinct digits? Solution.
\begin{equation*} \underbrace{5}_{\mbox{choose 4th digit}} \times \underbrace{8}_{\mbox{choose 1st digit}} \times \underbrace{8}_{\mbox{choose 2nd digit}} \times \underbrace{7}_{\mbox{choose 3rd digit}} \end{equation*}Note: it is important to choose the digits in this order to get the right answer. For example, if we choose the 3rd digit before choosing the 1st digit, then we must consider 2 cases, depending on whether we chose 0 for the 3rd digit. You will still get the right answer, but you must deal with more cases.
How many numbers from \(0\) to \(1000\) contain exactly one 3? Solution.
We consider all possible 3 digit numbers, where we can have a 0 in the first digit (so we write \(003\) instead of \(3\)). There are three cases, depending on the location of the 3. In each case, we have 9 choices for each of the other two digits, so the answer is
\begin{equation*} (9 \times 9) + (9 \times 9) + (9 \times 9) = 243 \end{equation*}
5. Sitting at a Circular Table.
In how many ways can \(k\) men and \(k\) women be seated around a circular table? Before anyone sits down, all chairs are identical. Solution.
\begin{equation*} \frac{(2k)!}{2k} = (2k-1)! \end{equation*}We place people into seats, starting at the top of the table and continuing clockwise. There are \((2k)!\) ways to do this. However, by the symmetry of the table, we can shift everyone over by one seat (or two seats, or three seats...) and get the same configuration. Therefore we must divide by \(2k\text{,}\) which is the number of possible rotations.
In how many ways can this be done if the men and women must sit in alternate seats? Solution.
\begin{equation*} \frac{k! k!}{k} = k! (k-1)! \end{equation*}Here is one proof of this result.
Start off with a line containing \(2k\) spots.
Case 1: people line up MFMF...MF. Number of ways:\(k! k!\)
Case 2: people line up FMFM...FM. Number of ways: \(k! k!\)
Total number of ways to line up: \(2 ( k! k!)\)
Turn the line into a circle. Each circular arrangement is created 2k times.
Final answer is \(\frac{2 (k! k!)}{2k} = \frac{k! k! }{ k} = k! (k-1)!\)
Here is another way to argue this that is quicker, but more subtle:
Pick any chair (it doesn't matter). Starting at that chair, place all the men in every other chair, going clockwise. Number of ways: \(k!\)
Now place the women going clockwise, starting at the empty chair to the right of the first man. Number of ways: \(k!\)
Accounting for the circular symmetry, each configuration is created \(k\) times.
Final answer is \(\frac{k! k!}{ k} = k! (k-1)!\text{.}\)
In how many ways can this be done if there are two women (and maybe more) sitting next to one another? Solution.
We just subtract our answer in part (b) from our answer in part (a) to get
\begin{equation*} (2k-1)! - k! (k-1)! \end{equation*}
6. Couples Sitting in a Row.
Four sisters and their spouses have been invited to a reception where these 8 people will be sitting in a row of 8 chairs. Each married couple must be seated together.
How many ways can this be done? Solution.
\begin{equation*} 4! \times 2^4 \end{equation*}There are \(4!\) ways to arrange the couples, and then 2 ways to seat each couple next to one another
How many ways can this be done if no sister sits next to any other sister? Solution.
\begin{equation*} 4! \times 5 \end{equation*}There are \(4!\) ways to arrange the couples. Let us start seating the couples from left to right, in chairs labeled by [8]. As soon as one sister sits in an even chair, this forces the remaining sisters to sit in an even chair. There is 1 way for the sisters to all sit in odd chairs. Otherwise, there are 4 ways to choose the first even chair taken by a sister. So there are a total of \(4! \times 5\) possible arrangements.
How many ways can this be done if every sister must sit next to one of her sisters? Solution.
We give two solutions.
\begin{equation*} 4! = 24 \end{equation*}Again, there are \(4!\) ways to arrange the couples. There is one way to seat the first couple, since the sister cannot be on the end. This also forces the arrangement of the second couple. Likewise, the 3rd and 4th couples only have one possible arrangement. Here is another way to argue it. The configuration must be of the form \(PSSPPSSP\) where \(P=\) partner and \(S=\) sister. Our answer is
\begin{equation*} {4 \choose 2} \cdot 2 \cdot 2. \end{equation*}First, we choose the two sisters that will appear in spots 2 and 3. There are two ways to arrange them. The remaining two sisters must sit in spots 6 and 7. Again, there are two ways to arrange them. The placement of the partners is then forced by the seat of their spouses.
How many ways can this be done if at least one pair of sisters sits next to one another? Solution.
\begin{equation*} 4! (2^4 - 5) \end{equation*}We subtract part (b) from part (a) to get the answer.
7. Drawing Rectangles and Triangles.
A \(4 \times 7\) checkerboard is shown below at the left.
How many different rectangles are hiding in it? Six examples of rectangles you need to find are shown in the second two boards. Solution.
The answer is
\begin{equation*} {8 \choose 2} {5 \choose 2}. \end{equation*}We choose two \(x\)-coordinates \(x_1 < x_2\) and two \(y\)-coordinates \(y_1 < y_2\text{.}\) Once we have these, the lower left corner is \((x_1, y_1)\) and the upper right corner is \((x_2, y_2)\text{.}\) Note that there are 8 choices for \(x\)-coordinate (not 7), and 5 choices for \(y\)-coordinate (not 4). If we evaluate this expression, we find that there are \(280\) rectangles in this grid.
How many different triangles with one horizontal side adjacent to two acute angles are hiding in it? Six examples of triangles you need to find are shown in the last two boards. Solution.
This problem is like part (a), but harder.
Choose 3 \(x\)-coordinates \(x_1 < x_2 < x_3\text{.}\) There are \({8 \choose 3}\) ways to do this.
Choose 2 \(y\)-coordinates \(y_1 < y_2\text{.}\) There are \({5 \choose 3}\) ways to do this.
Decide whether the horizontal size will be the upper or lower one. There are 2 ways to do this.
The result is either the triangle
\begin{equation*} (x_1,y_1), (x_3,y_1), (x_2, y_2) \end{equation*}or the triangle
\begin{equation*} (x_1,y_2), (x_3,y_2), (x_2, y_1). \end{equation*}The total number of ways to complete this recipe is
\begin{equation*} {8 \choose 3} {5 \choose 3} \cdot 2. \end{equation*}
8. A Combinatorial Identity.
Find a closed formula for the sum \(\displaystyle{\sum_{k=0}^n {n \choose k} 2^k}\text{.}\) Solution.
By the binomial theorem,
\begin{equation*} 3^n = (2 + 1)^n = \sum_{k=0}^n {n \choose k} 2^k. \end{equation*}Devise a situation that is counted by this sum. Then give a "combinatorial proof" by explaining why both the closed formula and the one given above count all configurations. Solution.
Here is one story that works. Suppose there are \(n\) kids who want ice cream. There are three flavors to choose from: vanilla, chocolate and strawberry. How many possible outcomes are there? Each kid has 3 choices, so there are \(3^n\) possible outcomes. We can count this outcome in two phases. First, determine the number \(k\) of kids ordering vanilla or chocolate. (The remaining \(n-k\) get strawberry.) Next, determine which of these \(k\) kids wants vanilla and which one wants chocolate. For each \(k\text{,}\) we can choose the choco-vanilla kids in \({n \choose k}\) ways, and then determine their status in \(2^k\) ways. We must sum over \(0 \leq k \leq n\) to get all possible outcomes.
9. Non-Attacking Rooks.
How many ways are there to place 8 rooks on an \(8 \times 8\) chessboard so that no two may attack one another? Solution.
There can only be one rook in each row and one rook in each column. Each valid configuration corresponds to a bijection between the rows and columns. There are \(8!\) possibilities.
How many ways are there to place 5 black rooks and 3 white rooks on an \(8 \times 8\) chessboard so that no two may attack one another? Solution.
Place the rooks in 2 phases. Phase 1: place 8 "gray" rooks. Phase 2: decide which of the 8 rooks are black. The entire process can occur in \(8! \times {8 \choose 5}\) ways.
How many ways are there to place 5 rooks on an \(8 \times 8\) chessboard so that no two may attack one another? Solution.
Phase 1: Choose 5 rows (in \({8 \choose 5}\) ways)
Phase 2: Choose 5 columns (in \({8 \choose 5}\) ways)
Phase 3: List the chosen rows in increasing orders. Assign each of the columns to one of these rows (in \(5!\) ways)
Place your 5 rooks in the resulting (row,column) pairs. So the number of configurations is
\begin{equation*} {8 \choose 5} \times {8 \choose 5} \times 5! \end{equation*}
10. Diagonals in a Polygon.
Consider a convex \(n\)-gon such that no pair of diagonals intersect at the same point.
How many diagonals are there? Solution.
We give two different (but equivalent) solutions.
Solution 1.
\begin{equation*} \frac{n (n-3)}{2} \end{equation*}Choose the first vertex in \(n\) different ways
Choose the second vertex in \(n-3\) different ways (we can't pick the first vertex again and we can't pick either of its neighbors).
We've picked each diagonal twice.
Solution 2.
\begin{equation*} {n \choose 2} - n \end{equation*}Pick any two vertices. These form a diagonal, unless we picked one of the \(n\) edges of the polygon. This is an example of the very useful
\begin{equation*} \mbox{good} = \mbox{all} - \mbox{bad} \end{equation*}How many intersections do the diagonals determine? Solution.
\begin{equation*} {n \choose 4} \end{equation*}If we choose 4 vertices, there is exactly one way to pair them up to get crossing diagonals. If our vertices in clockwise order are \(v_1, v_2, v_3, v_4\) then we must pair \(v_1\) with \(v_3\) and \(v_2\) with \(v_4\text{.}\)
In other words, there is a bijection between intersections of diagonals and 4-sets of vertices.