\include{preamble}
\setcounter{try}{18}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\title{}
\author{Zajj Daugherty}
\date{\today}
\usepackage{multicol}
\begin{document}
\begin{flushright}
SOLUTIONS\\
Homework 4\\
Due 2/27/19
\end{flushright}
%-----------------% HANDOUT 7 %-----------------%
\begin{try}For each of the following, use some combination of the sum and product rules to find your answer. Give an un-simplified numerical answer (i.e.\ give your answer as, say, $5*4$ instead of $20$), and explain it, saying which rule(s) you're using when.
\begin{enumerate}[(a)]
\item A particular kind of shirt comes in two different cuts - male and female, each in three color choices and five sizes. How many different choices are made available?
\begin{ans}We can count the choices in steps as follows.
\begin{enumerate}[\bf Step 1:]
\item Choose the cut (2 ways).
\item Choose the color (3 ways).
\item Choose the size (5 ways).
\end{enumerate}
Using product rule, there are \fbox{$2 \cdot 3 \cdot 5$} options in total.
\end{ans}
\item On a ten-question true-or-false quiz, how many different ways can a student fill out the quiz if they definitely answer all of the questions? How many ways if they might leave questions blank?
\begin{ans}We can count the number of possible answers in steps, where step $n$ is the number of options for ways to answer the $n$the questions (2 ways). So using product rule, there are there are \fbox{$2^{10}$} ways in total.
But if they might leave answers blank, then there are 3 options per step, giving \fbox{$3^{10}$} possibilitie in total.
\end{ans}
\item How many 3-letter words (these don't have to be real words, just strings of letters) are there?
\begin{ans}
We can count the number of words in steps, where step $n$ is the number of options for letters for the $n$th letter of the word. So using product rule, since there are 26 letters, there are there are \fbox{$26 \cdot 26 \cdot 26 = 26^3$} words in total.
\end{ans}
\item How many 3-letter words are there that end in a vowel?
\begin{ans}
Again, we can count the number of words in steps, where step $n$ is the number of options for letters for the $n$th letter of the word. So using product rule, since there are 26 letters and 5 vowels, there are there are \fbox{$26 \cdot 26 \cdot 5$} 3-letter words ending in vowels.
\end{ans}
\item How many 3-letter words are there that have no repeated characters?
\begin{ans}~
\begin{enumerate}[\bf Step 1:]
\item Choose the first letter (26 ways).
\item Choose the first letter (25 remaining letters).
\item Choose the first letter (24 remaining letters).
\end{enumerate}
Using product rule, there are \fbox{$26 \cdot 25 \cdot 24$} 3-letter words with no repeated characters
\end{ans}
\pagebreak
\item How many 3-letter words are there that have the property that if they start in a vowel then they don't end in a vowel? (You'll want to break this into disjoint cases).
\begin{ans}~
\begin{enumerate}[\bf C{a}se 1:]
\item If they start with a vowel.
Step 1: $5$ choices; step 2: $26$ choices; step 3: $26-5 = 21$ choices. \\
Total: $5 \cdot 26 \cdot 21$ words starting in a vowel but not ending in a vowel. (Product rule)
\item If they don'e start with a vowel.
Step 1: $26-5 = 21$ choices; step 2: $26$ choices; step 3: $26$ choices. \\
Total: $21 \cdot 26 \cdot 26$ words not starting in a vowel. (Product rule)
\end{enumerate}
Using sum rule, there are \fbox{$5 \cdot 26 \cdot 21 + 21 \cdot 26 \cdot 26$} words satisfying these criteria.
\end{ans}
\item How many 2-letter passwords are there that are made up of upper and/or lower case letters?
\begin{ans}~
\begin{enumerate}[\bf Step 1:]
\item Choose the first letter--- using sum rule, there are $26+26$ ways.
\item Choose the second letter--- using sum rule, there are $26+26$ ways.
\end{enumerate}
Using product rule, there are \fbox{$(26 +26)(26 +26)$} such passwords.
\end{ans}
\item How many 2-letter passwords are there that are made up of upper and/or lower case letters, but where at least one of the letters is upper-case? (Again, you'll want to break this into disjoint cases).
\begin{ans}~
\begin{enumerate}[\bf C{a}se 1:]
\item the first letter is upper case. \\
Letter 1: $26$ choices; letter 2: $26+26$ choices.\\
Total: $26(26+26)$.
\item the first letter is lower case, meaning the second letter must be upper case. \\
Letter 1: $26$ choices; letter 2: $26$ choices.\\
Total: $26 \cdot 26$.
\end{enumerate}
Using product rule, there are \fbox{$26(26+26) +26 \cdot 26 $} such passwords.
\medskip
Alternatively, we could have used the subtraction rule. \\
{\bf All passwords:} $(26 + 26)^2$\\
{\bf ``Bad'' passwords} (both characters are lower case): $26^2$\\
{\bf Total ``good'' passwords:} \fbox{$(26 + 26)^2 - 26^2$}\
\medskip
(You can check that these two produce the same number.)
\end{ans}
\end{enumerate}
To check your answers: (a) 30; (b) 1024; 59,049; (c) 17,576; (d) 3380; (e) 15,600; (f) 16,926; (g) 2704; (h) 2028.
\end{try}
\pagebreak
\begin{try}For each of the following, use some combination of the sum, product, inclusion-exclusion, and division rules to find your answer. Give an un-simplified numerical answer, and explain it, saying which rule(s) you're using when. (Note, there are 26 letters and 5 vowels.)
\begin{enumerate}[(a)]
\item How many strings of three letters are there that satisfy the following:
\begin{enumerate}[(i)]
\item that contain exactly one vowel?
\begin{ans}
\begin{enumerate}[\bf Step 1:]
\item Choose the which letter will be the vowel: $3$ choices.
\item Choose the vowel: $5$ choices.
\item Choose the first non-vowel: $21$ choices.
\item Choose the secons non-vowel: $21$ choices.
\end{enumerate}
Combining using product rule: \fbox{$3 \cdot 5 \cdot 21 \cdot 21$}
\end{ans}
\item that contain exactly 2 vowels?
\begin{ans}
\begin{enumerate}[\bf Step 1:]
\item Choose the which letter won't be the vowel: $3$ choices.
\item Choose the first vowel: $5$ choices.
\item Choose the second vowel: $5$ choices.
\item Choose the non-vowel: $21$ choices.
\end{enumerate}
Combining using product rule: \fbox{$3 \cdot 5 \cdot 5 \cdot 21$}
\end{ans}
\item that contain at least 1 vowel?
\begin{ans}
\begin{enumerate}[\bf C{a}se 1:]
\item Exactly 1 vowel: $3 \cdot 5 \cdot 21 \cdot 21$ (product rule)
\item Exactly 2 vowels: $3 \cdot 5 \cdot 5 \cdot 21$ (product rule)
\item Exactly 3 vowels: $5 \cdot 5 \cdot 5$ (product rule)
\end{enumerate}
Combining using sum rule: \fbox{$3 \cdot 5 \cdot 21^2 + 3 \cdot 5^2 \cdot 21 + 5^3$}
\medskip
Alternatively, we can take the total number of strings and subtract the ones with no vowels:
\fbox{$26^3 - 21^3$} (product and subtraction rules).
\end{ans}
\end{enumerate}
\item How many 3-card hands are there from a 52-card deck, which\dots
\begin{enumerate}[(i)]
\item have no other restrictions?
\begin{ans}~\\
{\bf Step 1, 2, and 3:} choose cards in order. $52\cdot 51\cdot 50$.\\
{\bf Count the number of rearrangements of those three cards:} $3 \cdot 2 \cdot 1$.
{\bf Using division rule:} \fbox{$\displaystyle \frac{52\cdot 51\cdot 50}{3 \cdot 2 \cdot 1}$}
\end{ans}
\item are all hearts? \Ans{\fbox{$\displaystyle \frac{13\cdot 12\cdot 11}{3 \cdot 2 \cdot 1}$}}
\pagebreak
\item are all the same suit?
\begin{ans}~\\
{\bf Step 1:} choose the suit: $4$ ways.
{\bf Step 2, 3, and 4:} choose cards in order. $13\cdot 12\cdot 11$\\
{\bf Count the number of rearrangements of those three cards:} $3 \cdot 2 \cdot 1$.
{\bf Using division rule:} \fbox{$\displaystyle 4 \cdot \frac{13\cdot 12\cdot 11}{3 \cdot 2 \cdot 1}$}
\end{ans}
\item form a straight (like 2,3,4 in possibly mixed suits. Note that Ace, 2, 3 and Queen, King, Ace are both straights.)
\begin{ans}~\\
{\bf Step 1:} choose the lowest card: $12$ ways (since King-Ace-2 isn't a straight)\\
Note that this determines the values of the other cards (e.g.\ if the lowest card is 2, then the others must be 3 and 4).
{\bf Step 2, 3, and 4:} choose suits of the other cards. $4 \cdot 4\cdot 4$\\
Note that there is no problem with order: choosing, for example, $\spadesuit$, $\spadesuit$, $\clubsuit$, means that the lowest two cards are spades and the highest card is a club.
\medskip
\textbf{Total:} \fbox{$12\cdot 4^3$}
\end{ans}
\item are not all the same suit? (use two of your previous answers)
\begin{ans}
This will be
$$\#\{\text{all 3-card hands}\} - \#\{\text{all the same suit}\}
= \fbox{$\displaystyle \frac{52\cdot 51\cdot 50}{3 \cdot 2 \cdot 1} - 4 \cdot \frac{13\cdot 12\cdot 11}{3 \cdot 2 \cdot 1}$}.$$
\end{ans}
\end{enumerate}
\item How many ways are there to seat 6 people at a round table with 6 chairs, if you're only paying attention to who is sitting next to whom?
\begin{ans}
First think about seating them in numbered seats: $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$.\\
Then divide by all the possible rotations of those seats: $6$ ways.\\
Finally, reversing the (rotational) orientation also preserves seat neighbors: $2$ choices.
\medskip
\textbf{Total:} \fbox{$\displaystyle \frac{6!}{6 \cdot 2}$}
\end{ans}
\item How many positive integers (strictly) less than 100 are there that are divisible by 2 and/or 3?
\begin{ans}
There are $\lfloor 99/2\rfloor = 49$ positive integers (strictly) less than 100 are there that are divisible by 2, and $\lfloor 99/3\rfloor = 33$ positive integers (strictly) less than 100 are there that are divisible by 3. But there are numbers that are divisible by both 2 and 3 (those divisible by 6): there are $\lfloor 99/6\rfloor = 16$ of these.
\medskip
\textbf{Total:} \fbox{$49 + 33 - 16$}
\end{ans}
\end{enumerate}
To check your answers: (a) 6615; 1575; 8315; (b) 22,100; 286; 1144; 768; 20,956; (c) 60; (d) 66.
\end{try}
\pagebreak
\begin{try}~
\begin{enumerate}[(a)]
\item How many positive integers less than 1000
\begin{enumerate}[(i)]
\item are divisible by 7? \Ans{$\lfloor 999/7\rfloor = $\fbox{$142$}}
\item are divisible by 7 but not by 11? \Ans{\fbox{$\lfloor 999/7\rfloor - \lfloor 999/(7\cdot 11)\rfloor$}}
\item are divisible by both 7 and 11? \Ans{\fbox{$\lfloor 999/(7\cdot 11)\rfloor$}}
\item are divisible by either 7 or 11? \Ans{\fbox{$\lfloor 999/7\rfloor + \lfloor 999/11\rfloor - \lfloor 999/(7\cdot 11)\rfloor$}}
\item are divisible by exactly one of 7 and 11? \\
$\quad$ \Ans{\fbox{$\lfloor 999/7\rfloor + \lfloor 999/11\rfloor - 2\lfloor 999/(7\cdot 11)\rfloor$}}
\item are divisible by neither 7 nor 11?\\
$\quad$ \Ans{\fbox{$999 - \left(\lfloor 999/7\rfloor + \lfloor 999/11\rfloor - \lfloor 999/(7\cdot 11)\rfloor \right)$}}
\item have distinct digits?
\begin{ans}The set of integers that are less that 1000 and greater than 0 are exactly the three digit numbers (writing, say, 31 as 031). So we can count these in the three steps of choosing one digit at a time: \fbox{$10\cdot9\cdot8$}.
\end{ans}
\item have distinct digits and are even?
\begin{ans}This is the same as the last problem, except the last digit must be 0, 2, 4, 6, or 8. Except be will run into trouble if we try to count the same way since we don't know if we have used one of those even digits or not. So instead, let's choose the last digit first!
\begin{enumerate}[\bf Step 1:]
\item Choose the last digit: $5$ choices.
\item Choose the second digit: $9$ choices.
\item Choose the first digit: $8$ choices. \hfill Total: \fbox{$5 \cdot 9 \cdot 8$}.
\end{enumerate}
\end{ans}
\end{enumerate}
\item How many strings of three decimal digits
\begin{enumerate}[(i)]
\item do not contain the same digit three times? \Ans{\fbox{$10^3 - 10$}}
\item begin with an odd digit? \Ans{\fbox{$5 \cdot 10^2$}}
\item have exactly two digits that are 4s? \Ans{\fbox{$3 \cdot 9$}}
\end{enumerate}
\item How many license plates can be made using either three digits followed by three uppercase English letters or three uppercase English letters followed by three digits?
$\quad$ \Ans{\fbox{$10^3 \cdot 26^3 + 26^3 \cdot 10^3$}}
\item Suppose that at some future time every telephone in the world is assigned a number that contains a country code that is 1 to 3 digits long, that is, of the form X, XX, or XXX, followed by a 10-digit telephone number of the form NXX-NXX-XXXX (as described in Example 8 in the book). How many different telephone numbers would be available worldwide under this numbering plan?
$\quad$ \Ans{\fbox{$(10 + 10^2 + 10^3) \cdot ( 8\cdot 10\cdot 10\cdot 8 \cdot 10^6 )$}}
\item How many injective functions are there from $\{a,b,c\}$ to $\{1,2,3,4\}$?
\Ans{\fbox{$4\cdot3\cdot2$}}
\item How many surjective functions are there from $\{a,b,c,d\}$ to $\{1,2,3\}$? \\
{[Hint: If $f: \{a,b,c,d\} \to \{1,2,3\}$ is surjective, then exactly one of $1, 2$, or $3$ has a preimage of size 2. First choose which of those three elements has the larger preimage, then pick it's preimage, and then assign the other two preimages.]}
$\quad$ \Ans{\fbox{$3 \cdot \frac{4 \cdot 3}{2} \cdot 2 \cdot 1$}}
\end{enumerate}
\end{try}
\end{document}