Exercises 8.6 Exercises
1.
Alex is choosing a class to take next semester. They can choose from \(9\) math classes or \(7\) computer science classes, of which \(3\) are cross-listed (listed as both math and CS courses). How many classes can they choose from?
Addition rule.
2.
A math teacher has access to a textbook that includes \(60\) questions. Of these \(60\) questions all are at least easy or important, \(42\) are easy, and \(23\) are important. How many questions are both easy and important?
3.
In one game, a certain NBA player attempts \(20\) shots. Suppose all his shots either make it, or are worth three points. If he throws \(15\) shots that make it and \(9\) three-pointers, how many of his throws must be three-pointers that made it?
4.
Your math professor has \(17\) books with yellow covers and \(5\) books with green covers. How many ways can they choose two books for a course, where one has a yellow cover and one has a green cover? (Assume a math book bears a single color.)
5.
Iori is customizing her giant robot. She has \(13\) possible options for her robot's left arm, and \(11\) possible options for its right arm. (You may assume that there is no overlap; i.e. an arm is either built intended to be a left or right arm.) How many possible choices of arms does she have?
6.
Two distinguishable six-sided dice are rolled (e.g., one is red and one is blue) and the sum of both rolls is tallied.
How many possible outcomes are there?
How many ways are there for the sum of the two rolls to be at least (including) \(7\text{?}\)
How many ways are there to get a prime sum?
How many ways are there to get a sum that is prime or at least \(7\text{?}\)
To start, list the possible results (sums) in a 6-by-6 grid.
7.
Suppose at once you flip a coin and draw a card from a deck of \(52\) standard playing cards (2 through 10, Jack, Queen, King, Ace).
How many possible outcomes are there?
In how many of those outcomes do you get a face card (Jack, Queen, King, Ace)?
In how many of those outcomes do you get a tails on the coin?
In how many of those outcomes do you get a face card and flip tails?
In how many of those outcomes do you get a face card or flip tails?
8.
In a 64-team single-elimination tournament, how many games are played? (“Single-elimination” means that a team is out of the tournament upon losing once. The winner is the only team that never loses.) Once you have solved the problem using the tools from this chapter, see if you can think of a more clever approach.
This problem was stolen with permission from Jay Cummings’ very good book Real Analysis: A Long-Form Mathematics Textbook , where I saw it first.
9.
Prove using the multiplication rule that a set with \(n\) elements has \(2^n\) subsets.
10.
Prove using induction that a set with \(n\) elements has \(2^n\) subsets.
A set with \(k+1\) elements can be written as
11.
There are ten volunteers to form a team of four people where everyone on the team has a different role. How many such teams are possible?
12.
There are fifteen candidates for seven different positions. How many ways can the hiring manager choose which seven people to hire?
A case-sensitive alphanumeric password is a password whose characters may be the capital letters A through Z, the lowercase letters a through z, and the digits 0 through 9. The next few problems deal with this definition.
13.
How many case-sensitive alphanumeric passwords with \(n\) characters are there?
14.
A \(10\)-character case-sensitive alphanumeric password is to have no repeated characters. How many such passwords are there?
15.
A \(10\)-character case-sensitive alphanumeric password is to be made with at least one repeated character. How many such passwords are there?
Last problem.
16.
A \(10\)-character case-sensitive alphanumeric password is to be made so that it is a palindrome; that is, the last half of the password is just the first half in reverse. How many of these passwords are there?
How many of the ten characters do you actually choose?
The next few problems deal with the language of the green-skinned, many-tentacled Glomulek people. Their language contains \(78\) different characters, including ones that sound like “squirk” and “chomly,” and some whose sounds cannot be approximated by human communication.
17.
How many words in the Glomulek language can be made from \(n\) characters?
18.
A \(17\)-character word in Glomulek is to contain no repetition. How many such words are possible?
19.
How many \(17\)-character Glomulek words contain some repetition?
20.
How many ways can four couples sit in a row such that everyone sits next to their partner?
Order the couples, then order the partners.
21.
How many ways can nine different people be seated in a circle?
Since the configuration is a circle, the first person's position is only fixed by the people next to them. In other words, it doesn't matter where the first person sits.
22.
How many ways are there to flip five coins and get three heads?
How many binary strings with five digits have exactly three ones?
How many subsets of the set \(\{a,b,c,d,e\}\) have three elements?
23.
Let \(\Omega=\{x,y,z\}\text{.}\)
Enumerate all the multisets from \(\Omega\) of cardinality \(r=3\text{.}\)
How many distinguishable terms are in the polynomial \((x+y+z)^3\text{?}\)
24.
How many multisets of \(10\) elements can be taken from the universe \(\{a,b,c,d\}\text{?}\)
How many bit strings can be written that have three ones and ten zeros?
How many distinguishable terms (i.e. after like terms are combined) are in the polynomial \((a+b+c+d)^{10}\text{?}\)
Make the connection between parts (a) through (c) explicit. Write down a single multiset, a single bit string, and a single term of the polynomial that all correspond to each other.
25.
How many ways are there to flip seven coins and get at least five heads?
26.
A seven-game series between the Toronto Raptors and the Golden State Warriors ends as soon as one team wins four games. How many ways can the series go? (In other words, you are counting strings of the form \(TTTGGGT\) or \(TGGGG\) where T or G appears exactly four times.)
First, since a team must win exactly four times, the string \(TGGGG\) may be regarded as the string \(TGGGGTT\text{.}\) Second, there are two possibilities for the winning team.
27.
A research team is to be made in the following way. There are two professors on the team, one of whom is the principal investigator. There are five students on the team who all have the same job. If eight professors and ten students volunteer, how many such teams are possible?
28.
A word is to be made by first choosing the letters that will be in the word, and then creating the word itself. Suppose we will choose five letters from the usual \(26\)-letter alphabet, and then make an eight-letter word from the five letters chosen. How many such words are possible?
29.
How many ways can fifteen people be divided into four teams if all that matters is how many people are on each team?
30.
How many non-negative integer solutions are there to the equation \(w+x+y+z=58\text{?}\)
Goofus and Gallant are going to the ice cream parlor. The parlor has 31 flavors. Goofus and Gallant will each get three scoops on a cone.
31.
Thoughtless Goofus doesn’t care what order his scoops are in. How many ways can he make his cone?
32.
Gallant, a man of taste, cares what order his scoops are in. How many ways can Gallant make his cone?
Goofus and Gallant are at the popular submarine sandwich chain, Sub Direction. Sub Direction has twenty-seven different sandwich toppings including meats, cheeses, and sauces, and you can have as many of each as you like on your sandwich. If you put more than five toppings on your sandwich, you have to pay extra, so Goofus and Gallant just want the five.
33.
Gallant (rightly) believes that the order of the toppings on the sandwich matters. How many ways can Gallant construct his five-topping sandwich?
34.
Goofus is just going to inhale the whole sandwich anyway, so who cares what order the toppings are in, he says. How many sandwiches can Goofus make?
35.
Goofus has $10 to bet that a particular team will win the NBA finals. He can bet on the Bucks, the Raptors, the Warriors, or the Nuggets. Goofus can place his bets in one-dollar increments (he may bet $0 or $1 on a team, but not $0.50). How many ways can Goofus allocate his money? (Gallant does not gamble.)
36.
After a nice day of picking apples, Goofus is carrying a basket of eleven apples, but he doesn't want to. How many ways can he discretely hide his apples in the baskets of his friends Gallant, Gerald, Gumby, and Grimlock?
37.
How many ways can twenty wedding guests be seated at five tables if each table has unlimited capacity, and all that matters is how many people are at each table?
38.
A monic polynomial is a polynomial whose leading coefficient is \(1\text{,}\) e.g. \(p(z)=z^3-2z+7\) is a degree \(3\) monic polynomial. Monic polynomials are uniquely determined by their roots, i.e. values \(z=c\) where \(p(c)=0\text{,}\) and the multiplicity of each root, i.e. the number of times \(p(z)\) is divisible by \((z-c)\text{.}\) The degree of a polynomial is the sum of the multiplicities of each root.
Anyway, count the number of monic polynomials of degree \(5\) whose roots are one of the first ten natural numbers, i.e. elements of \(\{0,1,2,3,4,5,6,7,8,9\}\text{.}\)
Where have you very recently seen the word “multiplicity” before?