diff options
Diffstat (limited to 'howard/hw10.tex')
| -rw-r--r-- | howard/hw10.tex | 379 |
1 files changed, 379 insertions, 0 deletions
diff --git a/howard/hw10.tex b/howard/hw10.tex new file mode 100644 index 0000000..01b8a46 --- /dev/null +++ b/howard/hw10.tex @@ -0,0 +1,379 @@ +\input tikz + +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv + +\newcount\indentlevel +\newcount\itno +\def\reset{\itno=1}\reset +\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in} +\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset +\aftergroup\afterstartlist} +\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or + i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or + s\or t\or u\or v\or w\or x\or y\or z\fi} +\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or + \alph\itno)\else + (\number\itno)\fi + }% + #1\smallskip\advance\itno by 1\relax} +\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}} +\let\endul\egroup +\def\hline{\noalign{\hrule}} +\let\impl\rightarrow +\newskip\tableskip +\tableskip=10pt plus 10pt +\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt +depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}} +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} + +\li Given that $f(n)$ is a function for all non-negative integers $n,$ +find $f(2),$ $f(3),$ and $f(4)$ for each of the following recursive +definitions: + +{\startlist + +\li $f(0) = 1$ + +$f(n+1) = 2f(n)^2+2$ +\smallskip +$f(2) = 34$ + +$f(3) = 2314$ + +$f(4) = 10,709,194.$ + +\li $f(0) = 5$ + +$f(1) = 4$ + +$f(n+1) = (3*f(n)) \bmod{(f(n-1)+1)}$ +\smallskip +$f(2) = 0$ + +$f(3) = 0$ + +$f(4) = 0$ + +\li $f(0) = 1$ + +$f(n+1) = 2^{f(n)}$ +\smallskip +$f(2) = 4$ + +$f(3) = 16$ + +$f(4) = 65536$ + +\li $f(0) = 1$ + +$f(1) = 3$ + +$f(n+1) = f(n) - f(n-1)$ +\smallskip +$f(2) = 2$ + +$f(3) = -1$ + +$f(4) = -3$ + +\li $f(0) = 2$ + +$f(n+1) = (n+1)^{f(n)}$ +\smallskip +$f(2) = 2$ + +$f(3) = 9$ + +$f(4) = 4^9 = 262,144.$ +} + +\li Recursively define the following sets. + +{\startlist + +\li The set of all positive powers of 3 (i.e. 3, 9, 27, \dots) + +$3\in S.$ + +If $x,y\in S,$ then $xy\in S.$ + +\li The set of all bitstrings that have an even number of 1s + +$0\in S.$ + +If $\gamma\in S,$ then $0\gamma,\gamma0,1\gamma1\in S.$ + +\li The set of all positive integers $n$ such that $n\equiv 3\pmod{7}$ + +$3\in S.$ + +If $x\in S,$ then $7+x\in S.$ + +} + +\li Recursively define the following sequences, where $n\in\bb Z^+$ + +{\startlist + +\li $a_n = 2n!$ + +$a_1 = 2.$ $a_n = na_{n-1}.$ + +\li $a_n = n*(5^n)$ + +$a_1 = 5.$ $a_{n+1} = {n+1\over n}5a_n.$ + +} + +\li Recursively define the function $\rm CS(x)$ that takes in a string +of uppercase letters and finds the sum of the number of C's and the +number of S's in the string. For example, ${\rm CS(`SOCKS')} = 3$ +because SOCKS has two S's and one C. + +$CS('') = 0$ + +$CS(S\lambda) = 1+CS(\lambda).$ + +$CS(C\lambda) = 1+CS(\lambda).$ + +And, where $l$ is any letter other than $C$ or $S,$ +$CS(l\lambda) = CS(\lambda).$ + + +\li Use a tree diagram to find the number of bit strings of length four +that do not contain three consecutive zeros. + +\tikzpicture +[ + level 1/.style = {sibling distance = 8.5cm}, + level 2/.style = {sibling distance = 4.5cm}, + level 3/.style = {sibling distance = 2.5cm}, + level 4/.style = {sibling distance = 1cm}, +] +\node {} + child {node {0} + child {node {00} + child {node {001} + child {node {0010}} + child {node {0011}} + } + } + child {node {01} + child {node {010} + child {node {0100}} + child {node {0101}} + } + child {node {011} + child {node {0110}} + child {node {0111}} + } + } + } + child {node {1} + child {node {10} + child {node {100} + child {node {1001}} + } + child {node {101} + child {node {1010}} + child {node {1011}} + } + } + child {node {11} + child {node {110} + child {node {1100}} + child {node {1101}} + } + child {node {111} + child {node {1110}} + child {node {1111}} + } + } + }; +\endtikzpicture + +There are 13 bit strings. + +\li Use a tree diagram to determine the number of ways to arrange the +letters a, b, c, and d such that c comes before b. + +\tikzpicture +[ + level 1/.style = {sibling distance = 4.5cm}, + level 2/.style = {sibling distance = 2cm}, + level 3/.style = {sibling distance = 1cm}, +] +\node {} + child {node {a} + child {node {ac} + child {node {acb} + child {node {acbd}} + } + child {node {acd} + child {node {acdb}} + } + } + child {node {ad} + child {node {adc} + child {node {adcb}} + } + } + } + child {node {c} + child {node {ca} + child {node {cab} + child {node {cabd}} + } + child {node {cad} + child {node {cadb}} + } + } + child {node {cb} + child {node {cba} + child {node {cbad}} + } + child {node {cbd} + child {node {cbda}} + } + } + child {node {cd} + child {node {cda} + child {node {cdab}} + } + child {node {cdb} + child {node {cdba}} + } + } + } + child {node {d} + child {node {da} + child {node {dac} + child {node {dacb}} + } + } + child {node {dc} + child {node {dca} + child {node {dcab}} + } + child {node {dcb} + child {node {dcba}} + } + } + }; +\endtikzpicture + +There are 12 ways to arrange these such that c comes before b. + +\li How many integers from 1 to 1000: + +{\startlist + +\li Are divisible by 7? + +$$\lfloor {1000\over 7}\rfloor = 142.$$ + +\li Are divisible by 7 but not 11? + +$$\lfloor {1000\over 7}\rfloor - \lfloor{1000\over 77}\rfloor = 130.$$ + +\li Are divisible by exactly one of 7 and 11? + +$$\lfloor {1000\over 7}\rfloor + \lfloor{1000\over 11}\rfloor - +2\lfloor{1000\over 77}\rfloor = 208.$$ + +\li Are divisible by neither 7 nor 11? + +$$1000 - \lfloor{1000\over 7}\rfloor - \lfloor{1000\over 11}\rfloor + +\lfloor{1000\over 77}\rfloor = 780.$$ + +\li Have distinct digits? + +Treating the three-, two-, and one-digit cases separately, and then +evaluating all choices of digits which don't start with 0 gives: +$$9\cdot9\cdot 8 + 9\cdot 9 + 9 = 738.$$ + +\li Have distinct digits and are even? + +In the one digit case, we have $\{2,4,6,8\},$ so four numbers. + +In the two digit case, we have one of the 9 numbers ending in zero, or +we have one of the 8 distinct-digit numbers for each other even digit, +giving $32+9=41$ amounts. + +In the three digit case, we can take the two-digit numbers and insert +one of the remaining 8 digits into the middle, +giving $41\cdot 8 = 328$ numbers. + +Adding these up, we get $373$ even numbers with distinct digits between +1 and 1000. +} + +\li A password name is a string between 1 and 4 characters (inclusive), +and it can consist of lowercase letters, uppercase letters, digits, +dollar signs, or underscores. However, the first character cannot be a +digit, and if the first character is either a dollar sign or an +underscore, then all other characters must be digits. How many different +password names exist under these rules? + +% backus-naur form +% L = [a-Z] 52 +% D = [0-9] 10 +% C = [_$] 2 +% * = L | D | C +% P = C[D[D[D]]] | L[*[*[*]]] +% 2 * (1 + 10 * (1 + 10 * (1 + 10))) +%+52 * (1 + 64 * (1 + 64 * (1 + 64))) + +There are 52 letters, 10 digits, and 2 special characters. +Dividing the set into two classes (starting with letters and starting +with special characters), we can then compute the choice of ending the +password (1 option) or adding another digit/letter (10 or 52 times the +number of combinations remaining) + +This gives us the combinatorial expression +$$2 * (1 + 10 * (1 + 10 * (1 + 10))) + 52 * (1 + 64 * (1 + 64 * (1+64))) += 13,850,082.$$ + +\li Assume that a website only allows strings of length 5 as a username +for a user account. Valid characters for a username consist of lowercase +letters, uppercase letters, digits, or underscores, and they have the +following requirements: + +\ul + +\li If the username begins with a vowel, then it must end with 2 even +digits. + +\li If the username begins with a consonant, then the remaining four +characters must also be letters. + +\endul + +How many different usernames exist under the given constraints? + +% V = 10 +% C = 42 +% L = 52 +% E = 5 +% O = 11 +% * = 63 +% V**EE | CLLLL | O**** + +There are three different patterns. +The first is a vowel, 2 of any character, and 2 even digits, giving us +$10*63^2*5^2$ options. +The second is a consonant and four letters, gviing +$42*52^4$ options. +The third is a digit or underscore and four of any character, giving +$11*63^4$ characters. + +The total number of options is $481,362,693.$ + +\bye |