Finished work from last semesterHEADmaster

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