diff options
Diffstat (limited to 'howard')
| -rw-r--r-- | howard/Makefile | 2 | ||||
| -rw-r--r-- | howard/hw10.tex | 379 | ||||
| -rw-r--r-- | howard/hw11.tex | 236 | ||||
| -rw-r--r-- | howard/hw5.tex | 222 | ||||
| -rw-r--r-- | howard/hw6.tex | 298 | ||||
| -rw-r--r-- | howard/hw7.tex | 192 | ||||
| -rw-r--r-- | howard/hw8.tex | 115 | ||||
| -rw-r--r-- | howard/hw9.tex | 144 |
8 files changed, 1587 insertions, 1 deletions
diff --git a/howard/Makefile b/howard/Makefile index 7685eb6..31bfdc1 100644 --- a/howard/Makefile +++ b/howard/Makefile @@ -6,7 +6,7 @@ PDFTEX = pdftex .tex.pdf: $(PDFTEX) $< -all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf +all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf hw5.pdf hw6.pdf hw7.pdf hw8.pdf hw9.pdf clean: rm -f *.pdf *.log 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 diff --git a/howard/hw11.tex b/howard/hw11.tex new file mode 100644 index 0000000..ec30878 --- /dev/null +++ b/howard/hw11.tex @@ -0,0 +1,236 @@ +\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 How many numbers must be selected from the set +$\{1,4,6,8,9,13,14,16,18,21\}$ to guarantee that at least one pair of +these numbers adds up to exactly 22? Simplify your answer to an integer. + +6 numbers must be selected. This set has five pairs that sum to 22, so +we're putting 6 pigeons into 5 holes, which guarantees one pair is +completed, and we get a sum to 22. + +\li How many different combinations of pennies, nickels, dimes, and +quarters can a piggy bank contain if it has 29 coins in it? Simplify +your answer to an integer. + +This is 29 coins into 4 categories, so +$${29+4-1\choose 3} = 4960$$ +different possibilities for the coins in this piggy bank. + +\li How many different ways are there to choose 13 donuts if the shop +offers 19 different varieties to choose from? Simplify your answer to an +integer. + +This is equivalent to putting 13 indistinct balls into 19 urns, which by +stars and bars is +$${19+13-1\choose 13-1} = 141,\!120,\!525$$ +different choices. + +\li Imagine you are drawing cards from a standard deck of 52 cards. For +each of the following, determine the minimum number of cards you must +draw from the deck to guarantee that those cards have been drawn. +Simplify all your answers to integers. + +{\startlist +\li A Straight (5 cards of sequential rank). Hint: when considering the +Ace, a straight could be A, 2, 3, 4, 5 or 10, J, Q, K, A, but no other +wrap around is allowed. + +We must eliminate the 5 and the 10 to prevent us from getting a +straight, so the highest number we can get before we get a straight is +$(13-2)\cdot 4 = 44$ and we need 45 cards to guarantee us a straight. + +\li A Flush (5 cards of the same suit) + +We have 4 holes and we want to guarantee 5 cards in a hole, so by +generalized pigeonhole, we need $4\cdot 4+1 = 17$ cards. + +\li A Full House (3 cards of 1 rank and 2 from a different rank) + +We have thirteen holes (ranks) and we want 3 pigeons in a hole, so +generalized pigeonhole gives us $13\cdot 2 + 1 = 27$ cards. + +\li A Straight Flush (5 cards of sequential rank from the same suit) + +Once we are guaranteed a straight by part (a), we must have a straight +flush since we already have most of the other cards in the same suit. +Therefore, 45 cards guarantees us a straight flush. +} + +\li How many integers between 1 and 1000 meet the criteria below. +Simplify your answer to an integer. + +\ul + +\li the digits are distinct + +\li the digits are odd + +\li the digits are in ascending order + +\endul + +We start from the set of odd digits $\{1,3,5,7,9\},$ complete the +picking process for one-, two-, and three-digits, and then reorder in +ascending order. +This gives us +${5\choose 3} + {5\choose 2} + {5\choose 1} = 25$ +different numbers. + +\li How many teenagers (people from age 13--19) must you select to +ensure that 4 of theme were born on the exact same date (mm/dd/yyyy)? +Simplify your answer to an integer. + +We will use the generalized pigeonhole principle. +This 7 year period includes either one or two leap years. +If it includes one leap year, this is $7\cdot 365 + 1$ days and we will +need $3\cdot(7\cdot 365 + 1) + 1$ teenagers to ensure 4 with the same +birth date. + +\li A coin is flipped 10 times. Simplify your answers to integers. + +{\startlist + +\li How many possible outcomes are there? + +$$2^{10} = 1024.$$ + +\li How many possible outcomes are there where the coin lands on heads +at most 3 times? + +We treat the 0 heads, 1 head, 2 heads, and 3 heads cases: +$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} = 176.$$ + +\li How many possible outcomes are there where the coin lands on heads +more than it lands on tails? + +We treat the 0 tails, 1 tails, 2 tails, 3 tails, and 4 tails cases: +$${10\choose 0} + {10\choose 1} + {10\choose 2} + {10\choose 3} + +{10\choose 4} = 386.$$ + +\li How many possible outcomes are there where the coin lands on heads +and tails an equal number of times? + +$${10\choose 5} = 252.$$ + +} + +\li How many solutions are there to the following equations? Simplify +your answer to an integer. + +{\startlist + +\li $a_1 + a_2 + a_3 + a_4 = 100$ + +where $a_1,$ $a_2,$ $a_3,$ and $a_4$ are positive integers? + +We can compute this using stars and bars, giving 99 spots and 3 bars or +$${99\choose 3} = 156,\!849$$ +solutions to the equation. + +\li $a_1 + a_2 + a_3 + a_4 + a_5 = 100$ + +where $a_1,$ $a_2,$ $a_3,$ $a_4,$ and $a_5$ are non-negative integers, +and $a_1 > 5.$ + +First we subtract 5 from both sides and then add 4 to both sides to +change the bounds on all of our numbers to $a_k > 0.$ +We would then have $\sum = 101.$ +Using stars and bars, we will obtain +$${100\choose 4} = 3,\!921,\!225$$ +solutions to this equation. + +\li $a_1 + a_2 + a_3 = 100$ + +where $a_1,$ $a_2,$ and $a_3$ are non-negative integers, and $a_3\leq +10.$ + +Computing ignoring the restriction, we get ${102\choose 2}$ solutions. +Then we consider the ones that violate the restriction ($a_3\geq11$) as +${91\choose 2}$ solutions. +The number of solutions following the restriction is +$${102\choose 2} - {91\choose 2} = 1056.$$ + +} + +\li How many different strings can be created by rearranging the letters +in ``addressee''? Simplify your answer to an integer. + +There are +$${9\choose 1,2,3,2,1} = 15,\!120$$ +strings (random permutation of 9 characters and then discount the +positioning of the 2 d's, the 3 e's, and the 2 s's) + +\li Let a class consist of 8 CS major students and 8 CM major students. +Each student is either a CS major or a CM major, but not both. How many +distinct ways are there to arrange the students in a line such that no +student stands next to someone in the same major as themselves? Simplify +your answer to an integer. + +There are two ways to do this (assuming indistinct students), either +starting with a CS or CM major. +Then the internal order of each major is $8!,$ giving us, for distinct +students, +$$2\cdot 8! \cdot 8! = 3,\!251,\!404,\!800$$ +ways to arrange them. + +\li Three pairs of twins are sharing a bucket of 24 chicken wings from +Olive Oyl's. Through the magic of twinship, each person always eats +exactly as many chicken wings as their twin. If each person eats at +least one chicken wing, how many ways can the chicken wings be +distributed amongst the people? For the purposes of this problem, +chicken wings are indistinguishable, and every chicken wing is eaten. +Simplify your answer to an integer. + +This is equivalent to three people sharing a bucket of 12 chicken wings. +Using stars and bars, we get +$${11\choose 2} = 55$$ +ways to eat the chicken wings. + +\li CS 2050 has 10 recitation sections. 7 of the recitation sections are +led by a pair of TAs, and 3 recitation sections are led by a trio of +TAs. How many ways are there to line up the TAs such that each TA is +standing next to their recitation partner(s)? Simplify your answer to an +integer. + +First, we consider how many ways we can arrange the recitation sections +($10!$). +Then we determine how many ways each recitation can be internally +arranged in the line ($(3!)^3\cdot(2!)^7$) +This computes to +$$10!\cdot(3!)^3\cdot(2!)^7 = 100,\!329,\!062,\!400$$ +ways to arrange the TAs. + +\bye diff --git a/howard/hw5.tex b/howard/hw5.tex new file mode 100644 index 0000000..e7d8cef --- /dev/null +++ b/howard/hw5.tex @@ -0,0 +1,222 @@ +\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\oldcomma{,} +\catcode`\,=13 +\def,{% + \ifmmode + \oldcomma\mskip\medmuskip\discretionary{}{}{}% + \else + \oldcomma + \fi +} + +\li For each of the following functions, determine $f: \bb Z \times \bb +Z \to \bb Z,$ determine whether the function is: + +\item{i)} onto and one-to-one + +\item{ii)} onto but not one-to-one + +\item{iii)} not onto but one-to-one + +\item{iv)} neither onto nor one-to-one + +\item{v)} not a function + +{\startlist + +\li $f(x,y) = 3x^2-2y.$ + +Neither onto nor one-to-one. +$1$ is unreachable, and $f(1,0) = f(-1,0).$ + +\li $f(x,y) = y! + x.$ + +Not a function. $y!$ is not defined on $y<0.$ + +\li $f(x,y) = 2x\cdot 3y.$ + +Neither onto nor one-to-one. +$1$ is unreachable, but $f(0,1) = f(1,0).$ + +\li $f(x,y) = x - y.$ + +Onto but not one-to-one +All integers are reachable, but $f(0,0) = f(1,1).$ + +\li $f(x,y) = |x| + y.$ + +Onto but not one-to-one +All integers are reachable, but $f(0,1) = f(1,0).$ +} + +\li Use the cashier's algorithm to make change using quarters, dimes, +nickels, and pennies for the following amounts of money. You do not have +to specifically show how you greedily formed change, but rather there +are many ways to make this change and only the cashier's/greedy +distribution will be accepted. + +{\startlist + +\li 43 cents + +One quarter, a dime, a nickel, 3 pennies + +\li 68 cents + +Two quarters, a dime, a nickel, 3 pennies. + +\li 98 cents + +Three quarters, two dimes, 3 pennies +} + +\li Imagine that a new coin that is worth exactly 4 cents has been +introduced to our existing currency system. Prove or disprove the +statement: ``The cashier’s algorithm using quarters, dimes, nickels, +4-cent coins, and pennies and will always produce change using the +fewest coins possible.'' + +This is false. 8 cents is decomposed into 1 nickel and 3 pennies by the +greedy algorithm, but is decomposed as 2 4-coins, which is fewer coins. + +\li State whether the following is True or False and explain your +reasoning for full credit: + +{\startlist + +\li Given two integers $x$ and $c,$ if $x+c < 10,$ then $\lfloor x/10 +\rfloor = \lfloor (x+c)/10 \rfloor.$ + +False. For $x = 0$ and $c=-100,$ then $x+c < 10$ but $\lfloor +x/10\rfloor = 0 \neq -10 = \lfloor (x+c)/10\rfloor.$ + +\li Given two functions $f(x)$ and $g(x),$ if $f(g(x))$ is defined, then +$g(f(x))$ must also be defined. + +False. Let $f: \bb N \to \bb R$ and $g: \bb N \to \bb N.$ +$f\circ g: \bb N \to \bb R,$ but $g\circ f$ undefined. +} + +\li For each of these function from $\bb R^+ \to \bb R,$ find the least +integer $n$ such that $f(x)$ is $O(x^n)$ if possible. If not, explain +why the function cannot be $O(x^n).$ + +{\startlist + +\li $f(x) = x^2\sqrt x.$ + +This function is $O(x^3).$ $x \geq \sqrt x,$ and the product of +$O(f(x))$ and $O(g(x))$ is $O(f(x)g(x)).$ + +\li $f(x) = 2x^3 + x^2\log(3x)$ + +This function is $O(x^3).$ All polynomials are $O(x^n)$ where $n$ is the +highest degree in the polynomial. + +\li $f(x) = {x^5 + x^4 \over x^4 + 5\log_5(5^x)}$ + +This function is $O(x).$ ($n=1$) +The top polynomial is $O(x^5)$ because polynomials are on the order of +their highest degree, and the bottom polynomial is $x^4 + 5x = O(x^4).$ +A rational function $g/h$ is on the order of $O(g)/O(h),$ so $f = O(x).$ + +\li $f(x) = \log(1000)$ + +This function is $O(1).$ ($n=0$) Any constant is $O(1).$ + +\li $f(x) = {3^x\over x^3} + {x^3\over\log(x)}$ + +This function is not $O(x^n)$ for any $n.$ +The exponential function grows faster than any polynomial function. +} + +\li Consider the linear search algorithm as outlined in class. How many +values would 15 be compared to in the sequence $(1,7,13,22,44,15,7,9).$ + +It would be compared to 6 values and on the last comparison, 15 is +found and the algorithm exits. + +\li Consider the binary search algorithm as outlined in class. (You must +use this exact version of the binary search algorithm): + +{\startlist + +\li List the values that 44 would be compared to in a search for 44 in +the following sequence: $(1,7,9,13,15,44,57,88).$ Make sure to include +the final value in the ``equality'' check as well. + +We will examine $(13, 44, 15, 44),$ the 4th, 6th, and 5th elements until +$i=j=6,$ and we exit the loop and check we have the right element. + +\li List the values that 103 would be compared to in a search for 103 in +the following sequence: $(3,8,17,21,44,73,88,101,113).$ Make sure to +include the final value in the ``equality'' check as well. + +We examine $(44, 88, 101, 113),$ the 5th, 7th, and 8th elements until +$i=j=9,$ and we check $x = a_9$ and find that our number is not in the +list. +} + +\li Prove or disprove the following statements. + +{\startlist + +\li $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + 0.5 \rfloor,$ +for all $x\in\bb R.$ + +{\bf Proof.} + +Let $x\in\bb R.$ +$x$ can be uniquely represented as $n+r$ where $0\leq r < 1,$ and +$n\in\bb Z.$ + +If $r < 1/2,$ $\lfloor x \rfloor = \lfloor x + 0.5 \rfloor = n.$ +$2x = 2n + 2r,$ and $0\leq 2r < 1,$ so $\lfloor 2x \rfloor = 2n = +\lfloor x \rfloor + \lfloor x + 0.5 \rfloor.$ + +If $r\geq1/2,$ $\lfloor x \rfloor = n$ and $\lfloor x+0.5 \rfloor = +n+1.$ $2x = 2n + 1 + 2(r-1/2)$ and $0 \leq r-1/2 < 1,$ so $\lfloor 2x +\rfloor = 2n+1,$ so $\lfloor x \rfloor + \lfloor x + 0.5 \rfloor.$ + +\li $x^3 + x^2 + \log(x)$ is $O(x^3).$ (If you choose to prove this +statement you must do so using witnesses). + +{\bf Proof.} + +On $x \geq 1,$ +$x^3 \geq x^3,$ $x^3 \geq x^2,$ and $x^3 \geq \log x,$ so +$3x^3 \geq x^3 + x^2 + \log x$ for $x \geq 1,$ so we know that $x^3 + +x^2 + \log(x) = O(x^3).$ + +\bye diff --git a/howard/hw6.tex b/howard/hw6.tex new file mode 100644 index 0000000..0d2b4ec --- /dev/null +++ b/howard/hw6.tex @@ -0,0 +1,298 @@ +\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}} + +\li Determine the time complexity of the following algorithm where $n$ +is the input size. Briefly explain how you determined the time +complexity (this does not need to be a proof). + +The time complexity is $O(n\log n).$ The outer loop runs $n$ times and +the inner loop takes $\lfloor \log_5(i) \rfloor$ iterations to complete, +each one in constant time. The total of these is dominated by the $\log +n$ term, giving our time complexity. + +\li Determine the time complexity of the following algorithm where $n$ +is the input size. Briefly explain how you determined the time +complexity (this does not need to be a proof). + +The first loop takes $n$ iterations and the inner part in constant time. +The second loop takes $\log_2(3n)$ iterations, and the sum of these two +is dominated by the higher-order term $O(n).$ + +\li Determine whether 47 divides each of the following numbers. + +{\startlist + +\li 4701 + +No. $4701 = 100\cdot 47 + 1.$ + +\li 94 + +Yes. $94 = 2\cdot 47.$ + +\li 232 + +No. $232 = 5\cdot 47 - 3.$ + +} + +\li Let $a,$ $b,$ and $c$ be integers, where $a\neq 0.$ Use a direct +proof to show that ``if $a\mid b$ and $b\mid c,$ then $a\mid c.$'' You +will need to provide a full proof (introduction, body, and conclusion), +not a ``pseudo-proof'' as seen in lecture. We want you to prove this +theorem, so simply citing Theorem 4.1.1 (iii) will receive no credit. + +{\bf Proof.} + +Let $a,$ $b,$ and $c$ be integers, where $a\neq 0$ such that $a\mid b$ +and $b\mid c.$ +We will show by direct proof that $a\mid c.$ + +From $a\mid b,$ there exists $k\in\bb Z$ such that $b = ak.$ +And from $b\mid c,$ there exists $j\in\bb Z$ such that $c = bj.$ +By substitution, $c = (ak)j = a(jk),$ and $jk\in\bb Z$ by closure of the +integers under multiplication, so $a\mid c$ by definition. + +We have shown that for $a,b,c\in\bb Z$ where $a\neq 0$ and $a\mid b$ and +$b\mid c,$ it must be that $a\mid c.$ +\endproof + +\li Prove that if $a$ is a positive integer, then $4$ does not divide +$a^2+5.$ You will need to provide a full proof (introduction, body, and +conclusion). Hint: it may be helpful to consider different cases for +$a.$ + +{\bf Proof By Contradiction.} + +Let $a$ be a positive integer. +Assume, for the sake of contradiction, that $4$ divides $a^2+5.$ + +Because $a$ is an integer, $a$ is either even or odd. + +Note that this proof uses the fact that $x\mid y$ only if $x\leq0$ or +$y \geq x.$ + +\smallskip +(Even) + +For some $k\in\bb Z,$ $a = 2k,$ so $a^2 = 4k^2,$ and $a^2+5 = 4k^2+5.$ +The assumption $4\mid a^2+5$ tells us that there exists $j\in\bb Z$ such +that $4j = a^2 + 5 = 4k^2 + 5.$ $4(j-k^2-1) = 1$ implies $4\mid 1$ +because $j-k^2-1\in\bb Z$ by closure of the integers under subtraction +and multiplication. This is a contradiction, showing that $4$ doesn't +divide $a^2+5.$ + +\smallskip +(Odd) + +For some $k\in\bb Z,$ $a=2k+1,$ so $a^2 = 4k^2 + 4k + 1,$ and $a^2 + 5 = +4k^2 + 4k + 6.$ +The assumption $4\mid a^2+5$ tells us that there exists $j\in\bb Z$ such +that $4j = a^2 + 5 = 4k^2 + 4k + 6.$ $4(j-k^2-k-1) = 2$ implies $4\mid +2$ because $j-k^2-k-1\in\bb Z$ by closure of the integers under +subtraction and multiplication. +This is a contradiction, showing that $4$ doesn't divide $a^2+5.$ + +\medskip +We have thus shown that for all positive integers $a,$ $4$ does not +divide $a^2+5.$ +\endproof + +\li Suppose that $a$ and $b$ are integers. $a\equiv 7 \pmod{13}$ and +$b\equiv 9 \pmod{13}.$ Find the integer $c$ such that $0\leq c\leq 12$ +in each of the following modular congruences. Note: a calculator is not +needed for these problems, and similar difficulty problems may appear on +the exam (where a calculator is not permitted). + +{\startlist + +\li $c \equiv 12a \pmod{13}$ + +$c\equiv 13-a \equiv 6 \pmod{13}.$ + +$c = 6.$ + +\li $c \equiv 5a + 2b \pmod{13}$ + +$c\equiv 5a + 2(b-13) \equiv 35 - 8 \equiv 1 \pmod{13}.$ + +$c = 1.$ + +\li $c \equiv a^2 + b^3 \pmod{13}$ + +$c\equiv (a-13)^2 + (b-13)^3 \equiv 6^2 - 4^3 \equiv 36 - 64 \equiv -28 +\equiv 11 \pmod{13}.$ + +$c = 11.$ + +\li $c \equiv (2a)^{1000} \pmod{13}$ + +$c\equiv (2a-13)^{1000} \equiv 1^{1000} \equiv 1 \pmod{13}.$ + +$c = 1.$ + +} + +\li Find each of these values. Note: a calculator is not needed for +these problems, and similar difficulty problems may appear on the exam +(where a calculator is not permitted). + +{\startlist + +\li $(18^2 \bmod{9}) \bmod{51}$ + +$18^2 \equiv (18-2\cdot 9)^2 \equiv 0 \pmod{9},$ giving us $0.$ + +\li $(7^2 \bmod{23})^3 \bmod{8}$ + +$7^2 \equiv 49-46 \equiv 3 \pmod{23},$ and $3^3 \equiv 27 - 24 \equiv 3 +\pmod{8},$ giving us $3.$ + +\li $(5^4 \bmod{11})^4 \bmod{6}$ + +$5^2 \equiv 3 \pmod{11},$ so $5^4 \equiv (5^2)^2 \equiv 3^2 \equiv 9 +\pmod{11}.$ + +$9^4 \equiv 3^4 \equiv 3 \pmod{6},$ giving us $3.$ + +} + +\li Convert the decimal expansion of each of these integers into a +binary expansion. Show your work for full credit. + +{\startlist + +\li 323 + +We start from $323$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by subtracting one and diving by two to get $1_2$ and $161.$ + +Then we have $11_2$ and $80.$ + +Then $011_2$ and $40.$ + +Then $0011_2$ and $20.$ + +Then $00011_2$ and $10.$ + +Then $000011_2$ and $5.$ + +Then $1000011_2$ and $2.$ + +Then $01000011_2$ and $1.$ + +Then $(1\,0100\,0011)_2,$ and we've completed our algorithm. + +\li 234 + +We start from $234$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by dividing by two to get $0_2$ and $117.$ + +Then we have $10_2$ and $58.$ + +Then we have $010_2$ and $29.$ + +Then we have $1010_2$ and $14.$ + +Then we have $01010_2$ and $7.$ + +Then we have $101010_2$ and $3.$ + +Then we have $1101010_2$ and $1.$ + +Then we have $(1110\,1010)_2$ and we've completed our algorithm. + +\li 52 + +We start from $52$ and subtract one if odd then divide by two, +prepending a one if odd and a zero otherwise. + +We start by dividing by two to get $0_2$ and $26.$ + +Then we have $00_2$ and $13.$ + +Then we have $100_2$ and $6.$ + +Then we have $0100_2$ and $3.$ + +Then we have $10100_2$ and $1.$ + +Then we have $(11\,0100)_2$ and we've completed our algorithm. + +} + +\li Convert the binary expansion of each of these integers into a +decimal and octal expansion. Show your work for full credit. + +{\startlist + +\li $(101\,1111)_2$ + +For the decimal expansion, I computed $1\cdot 2^6 + 1\cdot 2^4 + 1\cdot +2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 64+16+8+4+2+1 = 95.$ + +For the octal expansion, we group it into triplets and then convert each +segment. $111_2 = 7_8,$ $011_2 = 3_8,$ and $1_2 = 1_8,$ giving expansion +$(137)_8.$ + +\li $(1011\,0101)_2$ + +Again, for the decimal expansion, we compute $1\cdot 2^7 + 1\cdot 2^5 + +1\cdot 2^4 + 1\cdot 2^2 + 1 \cdot 2^0 = 128 + 32 + 16 + 4 + 1 = 181.$ + +And for the octal expansion, we group it into triplets again, starting +from the end, $101_2 = 5_8,$ $110_2 = 6_8,$ and $10_2 = 2_8,$ giving +expansion $(265)_8$ + +} + +\li Convert $(A6CD1)_{16}$ from its hexadecimal expansion into a binary +expansion. Show your work for full credit. + +We convert each nibble into its corresponding binary expansion. $A_{16} += 1010_2,$ $6_{16} = 0110_2,$ $C_{16} = 1100_2,$ $D_{16} = 1101_2,$ and +$1_{16} = 0001_2,$ so we get the full expansion +$(1010\,0110\,1100\,1101\,0001)_2.$ + +\li Convert $(1001\,0110\,1010\,0001\,0110)_2$ from its binary expansion +into a hexadecimal expansion. Show your work for full credit. + +We convert each nibble into its corresponding hexadecimal character. +$1001_2 = 9_{16},$ $0110_2 = 6_{16},$ $1010_2 = A_{16},$ $0001_2 = +1_{16},$ and $0110_2 = 6_{16},$ giving us hexadecimal expansion +$(96A16)_{16}.$ + +\bye diff --git a/howard/hw7.tex b/howard/hw7.tex new file mode 100644 index 0000000..39d2f64 --- /dev/null +++ b/howard/hw7.tex @@ -0,0 +1,192 @@ +\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\lcm{\mathop{\rm lcm}} + +\li Find the prime factorization of each of these integers. + +{\startlist + +\li 9072 + +$9072 = 2^4\cdot 3^4\cdot 7.$ + +\li 324 + +$324 = 2^2\cdot 3^4.$ + +\li 6! + +$6! = 2^4\cdot 3^2\cdot 5.$ + +} + +\li Approximate the number of prime numbers not exceeding 50000. Show +your work. + +The approximate number of primes less than $N$ is $N/\ln(N)$ +$${50000\over\ln(50000)} \approx {50000\over 10.82} \approx 4621.$$ + +\li Determine whether the integers 2, 51, 101, and 119 are pairwise +relatively prime. Show your work for full credit. + +These are the prime factorizations of the above numbers: + +$2 = 2.$ + +$51 = 3\cdot 17.$ + +$101 = 101.$ + +$119 = 7\cdot 17.$ + +$51$ and $119$ are not coprime because they share the factor 17. +Every other pair is relatively prime. + +\li What is the greatest common divisors of these pairs of integers? + +{\startlist + +\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$ + +$2^4*3^3*5^2.$ + +\li 19 and $19^1 8.$ + +19. +} + +\li What is the least common multiple of these pairs of integers? + +{\startlist + +\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$ + +$2^5*3^3*5^6*7^2.$ + +\li $2^4*7$ and $5^5*13.$ + +$2^4*5^5*7*13.$ + +} + +\li Find the least integer with $n$ distinct positive factors where $n$ +is below. For example, if $n=4,$ then the solution is $6$ because +$1,2,3,6$ are distinct positive factors of $6$ and there are $n=4$ of +them. + +{\startlist + +\li 3 + +$4$ has factors $1,2,4.$ + +\li 5 + +$16$ has factors $1,2,4,8,16.$ + +\li 6 + +$12$ has factors $1,2,3,4,6,12.$ + +} + +\li Use the Euclidean algorithm to find the following values. You must +clearly show all steps of your work using the Euclidean algorithm taught +in class. + +{\startlist + +\li $\gcd(100,101)$ + +$(100,101)\to (100, 1)\to (1, 0),$ giving $\gcd(100,101) = 1.$ + +\li $\gcd(64, 12)$ + +$(64, 12)\to (12, 4)\to (4, 0),$ giving $\gcd(64,12) = 4.$ + +} + +\li Show your work by using the Chinese Remainder Theorem, find all +values $x$ such that + +$x \equiv 1 \pmod{5}.$ + +$x \equiv 2 \pmod{6}.$ + +$x \equiv 3 \pmod{7}.$ + +\smallskip +5, 6, and 7 are pairwise coprime, so these congruences specify a unique +integer $n$ such that $x\equiv n \pmod{210}.$ + +$y_1 = 42,$ and $a_1 = 1,$ so $z_1 = 3.$ + +$y_2 = 35,$ and $a_2 = 2,$ so $z_2 = 5.$ + +$y_3 = 30,$ and $a_3 = 3,$ so $z_3 = 4.$ + +$a_1y_1z_1 + a_2y_2z_2 + a_3y_3z_3 \equiv 206 \bmod{210}.$ + +\li Decrypt the following ciphertext message: $HJUXDW,$ which was +encrypted first using a shift cipher, then using a transposition cipher. +The key of the shift cipher was $k=3,$ and the transposition cipher was +based on the permutation $\sigma$ of the set 1, 2, 3 with $\sigma(1) = +2$ and $\sigma(2) = 3$ and $\sigma(3) = 1.$ + +We start by computing a transposition $\sigma^{-1}(3) = 2$ and +$\sigma^{-1}(2) = 1$ and $\sigma^{-1}(1) = 3.$ +The ciphertext becomes $JUHDWX.$ +We then convert the ciphertext to numbers +$(9, 20, 7, 3, 22, 23)$ and subtract three to get +$(6, 17, 4, 0, 19, 20),$ and finally convert numbers to letters, +obtaining $GREATU.$ + +\li Suppose you intercept the message ``57 04 00 59 50 57 04 14 52 50 57 +42 00 54'' that has been encrypted using the RSA algorithm. You know +that the public key used for encryption is $(65,7).$ Decrypt the message +to determine what was said. Use the process shown in lecture to complete +this problem. You must show all work. (If your calculator is unable to +calculate $a^d\bmod{n}$ where a is one of the numbers in the message above and +$d$ is the decryption key, then you can just show $a^d\bmod{n}$ for each value of +a. Note that this is the final step in decryption so you won't show what +the message actually was. You must still show the work for calculating +the decryption key $d$). + +$n = 13\cdot 5 = p\cdot q.$ +$\lcm(p-1,q-1) = 12.$ +$7\cdot 7 \equiv 1 \pmod{12},$ +so $d = 7$ (the multiplicative inverse of 7 mod 12) + +We then compute $a^d\bmod{n}$ for each number in the message, obtaining +$(8,4,0,19,15,8,4,14,13,15,8,3,0,24)$ or $IEATPIEONPIDAY.$ + +\bye diff --git a/howard/hw8.tex b/howard/hw8.tex new file mode 100644 index 0000000..c760b02 --- /dev/null +++ b/howard/hw8.tex @@ -0,0 +1,115 @@ +\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\lcm{\mathop{\rm lcm}} + +\li Use mathematical induction to prove that the following statement is +true for all positive integers $n.$ + +$$8+15+22+29+\ldots+(7n+1) = {(7n(n+1)+2n)\over 2}.$$ + +We start with the base case $n = 1.$ +$$8 = {7(1)(1+1)+2(1)\over 2} = {14+2\over 2} = 8.$$ + +We now inductively assume that the statement is true for some positive +integer $k,$ and prove the statement for $k+1.$ + +$$8+15+\ldots+(7k+1) = {7k(k+1)+2k\over 2}.$$ + +We add $7(k+1)+1$ to both sides. +$$8+15+\ldots+(7k+1)+(7(k+1)+1) = {7k(k+1)+2k\over 2} + 7(k+1)+1 =$$$$ +{7k(k+1) + 7(2)(k+1) + 2k + 2\over 2} = {7(k+1)(k+2) + 2(k+1)\over 2}.$$ + +We have thus shown the statement for $k+1.$ + +By mathematical induction, we have proven the initial statement for all +positive integers $n.$ + +\li Use mathematical induction to prove or disprove that the following +statement is true for all non-negative integers $n.$ + +$$1+nh \leq (1+h)^n,\hbox{ where }h>-1.$$ + +We start with the base case of the smallest non-negative integer $n=0.$ +$$1+0h = 1 \leq 1 = (1+h)^0,$$ +(note that $h>-1,$ so $(1+h)>0,$ so $(1+h)^0 = 1.$) + +We now assume that the statement is true for some non-negative integer +$k$ and prove the statement for $k+1.$ + +We know the inductive hypothesis $1+kh \leq (1+h)^k$ and multiply both +sides by $1+h$ to get +$(1+kh)(1+h) = 1+(k+1)h+kh^2 \leq (1+h)^{k+1}$ +$0\leq h^2,$ so $0\leq kh^2,$ so $1+(k+1)h \leq (1+h)^{k+1}.$ + +By mathematical induction, we have shown that for all non-negative +integers $n,$ $1+nh \leq (1+h)^n.$ + +\li Use mathematical induction to prove or disprove that the following +statement is true for all positive odd integers $n.$ + +$$n^2-1\hbox{ is divisible by }8.$$ + +We start with the base case of the smallest positive odd integer $n=1.$ +$n^2-1 = 1-1 = 0,$ and $8\mid 0,$ showing our base case. + +We now assume that the statement is true for some positive odd integer +$k.$ Because $k$ is odd, there is an integer $j$ such that $k = 2j+1.$ +We start from the inductive hypothesis $k^2-1$ is divisible by 8, so +there is an $l$ such that $k^2-1 = 8l.$ +$$k^2-1 = (2j+1)^2-1 = 4j^2+4j.$$ +We add $8j+8$ to both sides. +$$4j^2+12j+8=(2j+3)^2-1 = (k+1)^2-1 = 8(l+j+1),$$ +showing that $(k+1)^2-1$ is divisible by 8. + +By mathematical induction, we have now shown that, for all positive odd +integers $n,$ $n^2-1$ is divisible by 8. + +\li Use mathematical induction to prove that the following statement is +true for all integers $n$ greater than 1. + +$$n! < n^n.$$ + +We start with the base case $n = 2.$ $2! = 2 < 4 = 2^2.$ + +We now inductively assume the statement is true for some $k \geq 2,$ and +we show that $(k+1)! < (k+1)^{k+1}.$ + +Noting that $k^k < (k+1)^k$ for $k > 1,$ +$$k! < k^k < (k+1)^k.$$ + +We then multiply both sides by $k+1,$ giving +$$(k+1)! < (k+1)^{k+1}.$$ + +We have shown by mathematical induction that for all integers $n>1,$ +$n! < n^n.$ + +\bye diff --git a/howard/hw9.tex b/howard/hw9.tex new file mode 100644 index 0000000..eec9dd4 --- /dev/null +++ b/howard/hw9.tex @@ -0,0 +1,144 @@ +\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 Use strong induction to show that the square root of 18 is +irrational. You must use strong induction to receive credit on this +problem. + +Let $P(n)$ be the proposition that $\sqrt{18} \neq {n\over b}$ for all +natural numbers $b$ (note: we can assume $b>0$ because $\sqrt{18} > 0$) +We will $P(n)$ for all nonnegative $n.$ +We will thus conclude that $\sqrt{18}$ is irrational. + +We start with the base case $P(0)$ that $\sqrt{18} \neq {0\over b}$ for +any natural number $b$ (this is clear because $\sqrt{18} \neq 0$). + +We now assume for the sake of induction that for all $0\leq j\leq k,$ +for some $k\geq 0,$ $P(j).$ +We will show $P(k+1),$ that $\sqrt{18} \neq {k+1\over b}$ for any +natural number $b.$ +We assume for the sake of contradiction that $\sqrt{18} = {k+1\over c}$ +where $c\in\bb N.$ +Rearranging, +$$18c^2 = (k+1)^2.$$ +$(k+1)^2=2(9c^2),$ and $9c^2\in\bb Z$ by closure, so $2\mid (k+1)^2,$ so +$2\mid k+1$ (if the square of an integer is even, that integer is even). + +By definition of even, there exists $l\in\bb Z$ such that $2l = k+1.$ +Also, $4l = (k+1)^2.$ +Substituting, $18c^2 = 4l.$ +With algebra, we obtain $9c^2 = 2l.$ +$2\nmid 9,$ and $2\mid 9c^2,$ so we must have $2\mid c^2.$ +Similarly, this implies $2\mid c,$ so there exists $m\in\bb Z$ such that +$c = 2m.$ +We now have $\sqrt{18} = {2l\over 2m} = {l\over m},$ and +$0 < l < k+1,$ contradicting $P(l).$ +We have now shown that $P(0),\ldots,P(k)\impl P(k+1).$ + +By strong induction, we have shown that $\sqrt{18}$ is not equal to any +nonnegative rational, so $\sqrt{18}$ is irrational. + +\li Use strong induction to show that every integer amount of postage 30 +cents or more can be formed using just 6-cent and 7-cent stamps. + +We will first show the base case that all values between 30 and 35 cents +can be formed from 6- and 7-cent stamps by example: $30 = 6(5)$ and $31 += 6(4) + 7(1)$ and $32 = 6(3) + 7(2)$ and $33 = 6(2) + 7(3)$ and $34 = +6(1) + 7(4)$ and $35 = 7(5).$ + +For the sake of induction we assume that for some $k\geq 30,$ all +postage amounts from $k$ to $k+5$ can be formed, and we show that +postage amount $k+6$ can be formed. +By adding a 6-cent stamp to the formulation for $k$ cents, we achieve a +formula for $k+6$ cent postage. +We have shown that being able to form postage of sizes $k$ through +$k+5$ implies we can form postage of $k+6$ cents. + +By strong induction, for all $n\geq 30,$ 6- and 7-cent stamps can form +$n$ cents of postage. + +\li Show that if $a_1,a_2,\ldots,a_n$ are $n$ distinct real numbers, +exactly $n-1$ multiplications are used to compute the product of these +$n$ numbers no matter how parentheses are inserted into their product. + +We first take the base case that the product of $n=1$ numbers can be +computed with 0 multiplications (the answer is $a_1$) + +Then, for the sake of induction, we assume that for some $k\in\bb N,$ +all multiplications of $1\leq j\leq k$ numbers require exactly $j-1$ +multiplications. +We will show that multiplying $k+1$ numbers requires $k$ multiplications +regardless of how the numbers are partitioned (how many parentheses are +inserted). +To account for any possible arrangement of upper level parentheses, we +partition our $k+1$ distinct real numbers into $2\leq r\leq k+1$ sets +$A_1,A_2,\ldots,A_r.$ +This will require $k-r+1$ multiplications to obtain products for each +partition, in total: +$$\sum_{i=1}^r |A_i| = k+1 \Rightarrow \sum_{i=1}^r |A_i| = k-r+1.$$ +We then multiply together the $r$ products which we obtain, requiring +another $r-1$ multiplications, resulting in $k$ total multiplications, +regardless of the parenthesis placement we chose. + +By strong induction, we have now shown that multiplying $n$ numbers +always requires $n-1$ multiplications regardless of the position of +parentheses. + +\li Suppose you begin with a pile of $n$ stones and split this pile into +$n$ piles of one stone each by successively splitting a pile of stones +into two smaller piles. Each time you split a pile you multiply the +nmuber of stones in each of the two smaller piles you form, so that if +the piles have $r$ and $s$ stones in them, you compute $rs.$ Show that +no matter how you split the stones, the sum of the products compared at +each step equals $n(n-1)/2.$ + +We will first show the base case of breaking a pile of 2 stones. +This pile must be broken into piles of one stone and one stone. +The product would then be $1 = {n(n-1)\over 2} = {2(2-1)\over 2}.$ + +We will now assume for the sake of induction that this proposition is +true for all piles of $j\leq k$ stones where $k\geq 1,$ and we will show +that this proposition is true for a pile of $k+1$ stones. +This pile can be broken into a piles of sizes $r$ and $k-r+1,$ where +$1\leq r\leq k.$ +The sum for each of these piles and the new product is +$$r(k-r+1)+{r(r-1)\over 2}+{(k-r+1)(k-r)\over 2} =$$$$ +{2rk-2r^2+2r+r^2-r+k^2+r^2-2kr+k-r\over 2} = +{k^2+k\over2} = {(k+1)k\over 2}.$$ +We have now shown that, assuming all smaller sums for $j$ piles are +${j(j-1)\over 2},$ $k+1$ stones build the sum ${(k+1)k\over 2}.$ + +By strong induction, we have shown that for all piles of $n$ stones, +this process yields a sum ${n(n-1)\over 2}.$ + +\bye |