20.7: Exercises

Last updated
Save as PDF

Page ID: 95410

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Exercise \(\PageIndex{1}\)

You are trying to decide how to top your ice-cream sundae. You have five choices of sprinkles, four choices of cookie crumbs, five choices of fruit, and three choices of chocolate chunks. For each category of topping, you may choose only one of the available options, or you may choose to skip that category altogether. How many different sundaes could you create out of these choices?

Exercise \(\PageIndex{2}\)

You turn eighteen and your trust fund finally starts paying out. You decide to buy a vehicle, and eventually narrow things down to a choice between five SUVs, four sports cars, and two motorcycles. How many ways are there to choose a vehicle? How many ways are there to choose one vehicle of each type?

Exercise \(\PageIndex{3}\)

Use the Multiplication Rule to demonstrate that the truth table of a logical statement with \(n\) statement variables requires \(2^n\) rows. That is, demonstrate that there are \(2^n\) different possible combinations of input truth values for \(n\) statement variables.
How many different truth tables involving \(n\) statement variables exist?

Exercise \(\PageIndex{4}\)

Recall that if \(A\) is a finite set with \(\vert A \vert = n\text{,}\) then \(\vert \mathscr{P}(A) \vert = 2^n\text{.}\) Use the Multiplication Rule to verify this formula by considering the construction of an arbitrary subset of \(A\) as a process of making \(n\) “either-or” decisions.

Exercise \(\PageIndex{5}\)

It is the year 2030, and Alberta has succeeded in seceding from Canada and has become the landlocked Kingdom of Albertania. The King decrees that the kingdom's citizens will all be assigned a hexadecimal ID. That is, using alphabet

\begin{equation*} \Sigma = \{ 0,1,2,3,4,5,6,7,8,9, \mathrm{a},\mathrm{b},\mathrm{c},\mathrm{d},\mathrm{e},\mathrm{f} \}, \end{equation*}
IDs will be words from \(\Sigma ^{\ast}\text{.}\) However, the king is vain and doesn't want any such ID to contain his initials, \(\mathrm{jk}\text{.}\)

For each \(n \ge 1\text{,}\) let \(s_n\) represent number of allowable IDs of length \(n\text{.}\)

Compute \(s_1\text{,}\) \(s_2\text{,}\) and \(s_3\text{.}\)
Determine a recurrence relation for \(s_n\) which is valid (at least) for \(n \ge 3\text{.}\)

Hint.: For each allowable word of length \(n - 1\) you can create a word of length \(n\) by adding a new letter onto the end. But you want your new word to also be allowable, so be careful about what you add onto the end!