Section5.1The Multiplicative and Additive Principles
In this section we begin our quest to start answering a question that sounds simple enough: “how many elements are in a set?” Counting the number of sets is common enough that we gave it its own symbol, \(|S|\text{,}\) in Section 1.2. Numbers of elements in the domain and codomain of functions determine whether a function is bijective, as we saw in an exercise in the functions section
It’s common to count “hands of cards,” so we’ll note that a standard deck of playing cards contains four suits (spade, heart, club, diamond). There are 13 cards in each suit (2,3,4,5,6,7,8,9,10, Jack, Queen, King, Ace). Face cards refers to jacks, queens, and kings. Spades and clubs are black and hearts and diamonds are red.
The multiplication principle states that if an event \(A\) can occur \(m\) ways and an event \(B\) can occur \(n\) ways, then the event “\(A \and B\)” can occur \(m\cdot n\) ways.
If in your closet you have five ironic t-shirts, three pairs of pants, and three collegiate hats, how many different outfits do you have? Here an outfit is pants, shirt, hat.
The addition principle states that if event \(A\) can occur \(m\) ways and event \(B\) can occur \(n\) ways and the two events are disjoint, then the event “\(A \text{ or } B\) (but not both)” can occur \(m + n\) ways.
It helps, when working counting problems with unions, even if using the principle of inclusion-exclusion, to draw a Venn diagram and label the number of elements in each section.
Suppose a company receives 350 applications from college graduates for a job. Suppose 220 of these applicants majored in computer science, 147 majored in business, and 51 majored in both computer science and business. How many majored in neither computer science nor business?
We will now consider bit strings which are strings of characters containing only \(0\) and \(1\text{.}\) For example, these are bit strings: \(0011, 1010, 110,\) etc.
There are 30 people in a club. Assuming everyone is qualified to serve in any position, how many different ways are there to assign a president, vice-president, secretary, and treasurer?
Suppose we surveyed a class of 41 students, asking if they could play an Accordion, a Bassoon, or a Clarinet. 12 could play the clarinet, 8 could play bassoon, and 5 the accordion. 6 played clarinet and bassoon, 2 played clarinet and accordion, and 3 played bassoon and accordion. One student played all three.
Our next counting approach is pretty straight forward. If you have three cookies, but only two plates, you know that one person is eaching at least two cookies.
I’ll pause here to note that a “pigeonhole” is a slot on a desk or shelf for holding papers. In our scenario, if we have five slots in our desk to hold our papers, and six papers, one slot has at least two papers.
Let’s imagine there are 100 people in a large lecture hall, then we know that at least at least \(\left\lceil \dfrac{100}{12} \right\rceil = 9\) have the same birth month. Divide the number of people by the number of months, and round up.
For the rest of your outfit, you have 5 shirts, 4 skirts, 3 pants, and 7 dresses. You want to select either a shirt to wear with a skirt or pants, or just a dress. How many outfits do you have to choose from?
To maximize the number of elements in common between \(A\) and \(B\text{,}\) make \(A \subset B\text{.}\) This would give \(\card{A \cap B} = 10\text{.}\)
In a recent survey, 30 students reported whether they liked their potatoes Mashed, French-fried, or Twice-baked. 15 liked them mashed, 20 liked French fries, and 9 liked twice baked potatoes. Additionally, 12 students liked both mashed and fried potatoes, 5 liked French fries and twice baked potatoes, 6 liked mashed and baked, and 3 liked all three styles. How many students hate potatoes? Explain why your answer is correct.
Consider all 5 letter “words” made from the letters \(a\) through \(h\text{.}\) (Recall, words are just strings of letters, not necessarily actual English words.)
\(64 + 64 - 0 = 128\) words. There are 64 words which start with “aha” and another 64 words that end with “bah.” Perhaps we over counted the words that both start with “aha” and end with “bah”, but since the words are only 5 letters long, there are no such words.
\((8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\) words. All the words minus the bad ones. The taboo word can be in any of three positions (starting with letter 1, 2, or 3) and for each position we must choose the other two letters (from the remaining 5 letters).
For how many three digit numbers (100 to 999) is the sum of the digits even? (For example, \(343\) has an even sum of digits: \(3+4+3 = 10\) which is even.) Find the answer and explain why it is correct in at least two different ways.
Assuming that no one has more than 1,000,000 hairs on their head and that the population of New York City was 8,008,278 in 2010, what is the least number of people in NYC in 2010 with the same number of hairs on their heads?
There are a total of four different remainders modulo 4. According to the Generalized Pigeonhole Principal, if we have 5 numbers divided among four different remainders, \(\left\lceil \dfrac{5}{4} \right\rceil = 2\) of them have to have the same remainder. Thus they differ by a multiple of four.
