path: root/howard/hw10.tex

\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