\documentstyle[12pt,twoside,amstex]{article}
\input{macros-course}

\begin{document}
\psol{6}{March 30, 1998}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem

Consider a standard checkerboard with 64 squares arranged on an
8 by 8 grid.  Suppose I place 33 checkers on the squares.
Prove that either two checkers must be in one square,
or two adjacent squares must both have checkers in them.
Adjacent squares are those that share a full border(not just a corner).
I.e., no square has more than four squares adjacent to it, and
corner squares have only two squares adjacent to them.

{\bf Solution:}
Suppose I place the checkers on the squares.  
Suppose I label each square with a number between 1
and 64, putting a 1 in the upper left square, a 2 in the square to its right,
a 3 in the next square to the right until I put an 8 in the upper right
square, and continuing this pattern with a 9 below the 1... until I put a 64
in the lower right square.  Now consider the 32 pairs of squares denoted by
$2k-1, 2k$, for $1 \leq k \leq 32$.  (So 1 pairs with 2, 3 pairs with 4 etc.)
It is clear that for each pair of squares, the two squares in the pair
are adjacent to each other.  

Since there are 32 pairs and 33 checkers, then,
by the pigeonhole principle, at least one pair must receive two checkers.
Either both of these checkers go into the same square in that pair, or each
goes into a different square in that pair, and, therefore, either two checkers
go into one square or two adjacent squares(the pair) each get a checker.
Therefore, if I place 33 checkers onto the squares, either two checkers must
be in one square or two adjacent squares must both havfe checkers in them.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2 From Rosen, 5.2, problem 4a (page 324), part b made up

\problem

Find exact closed form solutions for the following recurrences.

\bparts
\ppart $f(n) = f(n-1) + 6f(n-2)$ for $n \geq 2$, $f(0) = 3$, $f(1) = 6$

{\bf Solution:}

{\bf Characteristic equation:}

${\alpha}^2 - {\alpha} - 6 = 0$

So the roots are $3$ and $-2$.  The general solution has the form
$A(-2)^n + B(3)^n$ for $A,B \in R$.

Compute $A$, $B$ using the initial conditions:

\[f(0) = 3 = A(-2)^0 + B(3)^0\]
\[3 = A + B\]
\[B = 3 - A\]
\[f(1) = 6 = A(-2)^1 + B(3)^1\]
\[6 = -2A + 3B\]
\[6 = -2A + 9 - 3A\]
\[5A = 3\]
\[A = 3/5\]
\[B = 3 - A\]
\[B = 15/5 - 3/5\]
\[B = 12/5\]

So the general solution is:
$f(n) = (3/5)(-2)^n + (12/5)(3)^n$.

Checking for small values of $n$(to avoid arithmetic and algebraic errors)

\[f(2) = 6 + 6 * 3 = 6 + 18 = 24\]
\[f(2) = (3/5)(-2)^2 + (12/5)(3)^2\]
\[f(2) = 12/5 + 108/5\]
\[f(2) = 120/5\]
\[f(2) = 24\]

The closed form is correct.

\ppart $f(n) = f(n-1) + 8f(n-2) - 12f(n-3)$ for 
$n \geq 3$, $f(0) = 0$, $f(1) = 16$, $f(2) = 14$.

{\bf Solution:}

{\bf Characteristic equation:}

${\alpha}^3 - {\alpha}^2 - 8{\alpha} + 12 = 0$

So the roots are $-3$ and a double root at $2$.  The general solution has the form
$A(-3)^n + B(2)^n + Cn(2)^n$ for $A,B,C \in R$.

Compute $A$, $B$, and $C$ using the initial conditions:

\[f(0) = 0 = A(-3)^0 + B(2)^0 + C(0)(2)^0\]
\[0 = A + B\]
\[A = -B\]
\[f(1) = 16 = A(-3)^1 + B(2)^1 + C(1)(2)^1\]
\[16 = -3A + 2B + 2C\]
\[16 = 3B + 2B + 2C\]
\[16 = 5B + 2C\]
\[-5B = 2C - 16\]
\[f(2) = 14 = A(-3)^2 + B(2)^2 + C(2)(2)^1\]
\[14 = 9A + 4B + 8C\]
\[14 = -9B + 4B + 8C\]
\[14 = -5B + 8C\]
\[14 = 2C - 16 + 8C\]
\[30 = 10C\]
\[3 = C\]
\[-5B = 2C - 16\]
\[-5B = 6 - 16\]
\[-5B = -10\]
\[B = 2\]
\[A = -B\]
\[A = -2\]

So the general solution is:
$f(n) = (-2)(-3)^n + 2(2)^n + 3n(2)^n$.

Checking for small values of $n$(to avoid arithmetic and algebraic errors)

\[f(3) = 14 + 8*16 - 12*0 = 142\]
\[f(3) = (-2)(-3)^3 + 2(2)^3 + 3(3)(2)^3\]
\[f(3) = 54 + 16 + 72\]
\[f(3) = 142\]

The closed form is correct.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3 fall 94 pset 6, formula significantly changed

\problem 


Consider the following depressing scenario:
Every year, each professor of computer science graduates two
new students who hold a postdoc for one year and then go on to become
full professors the following year. 
To compound the miseries of newly graduating students, in year
$n\geq 3$ there are $3(n-3)$ physicists who change careers to become
computer science professors without going to graduate school.
Let $f(n$) denote the number of computer science professors after
$n$ years.  Assume $f(0)=0$ and $f(1)=1$.  
$f(2)=1$: in year 2, there is one CS professor, namely the one
CS professor from year 1(there are also two postdocs who graduated
in year 1 and will be professors in year~3).  Then
$f(3)=3$: in year 3, there are three CS professors, the one
from year 1, and the two postdocs who graduated in year 1.

\bparts
\ppart 
Compute $f(4)$, $f(5)$, and $f(6)$.

{\bf Solution:}

$f(4) = 3$ professors $+ 2$ postdocs becoming professors $+ 3$ physicists $=8$.

$f(5) = 8$ professors $+ 6$ postdocs becoming professors $+ 6$ physicists $=20$.

$f(6) = 20$ professors $+ 16$ postdocs becoming professors $+ 9$ physicists
$=45$.

\ppart
Set up a recurrence relation obeyed by~$f(n)$(for $n \geq 3$).

{\bf Solution:}

$f(n) = f(n-1) + 2f(n-2) + 3(n-3)$

\ppart
Solve your recurrence to find a closed form for~$f(n)$ (for $n \geq 3$).

{\bf Solution:}

{\bf Homogeneous Solution:}

The homogeneous recurrence is:

$f(n) = f(n-1) + 2f(n-2)$.

The characteristic equation is:

${\alpha}^2 - {\alpha} - 2 = 0 \rightarrow ({\alpha} + 1)({\alpha} - 2) = 0$.
So the roots are $-1$ and $2$.  The general solution is then 
$A(-1)^n + B(2)^n$ for $A,B \in R$.   

{\bf Particular Solution:}
Since the ``drive'' formula is $3(n-3)$ we try a polynomial of the same degree
(higher if 1 is a root of characteristic equation).  Guess
$f(n) = an + b$, and solve for $a,b$ satisfying the recurrence:

\[an + b = \]
\[a(n-1) + b + 2(a(n-2) + b) + 3(n-3) = \]
\[an - a + b + 2an - 4a + 2b + 3n - 9 = \]
\[n(3a + 3) + (3b - 5a - 9)\]

which implies that $a = -3/2$, $b = (-5a - 9)/(-2) = (15/2 - 9)/(-2) = 
(3/2)/(2) = 3/4$.

{\bf General Solution for Inhomogeneous Recurrence:}

$f(n) = A(-1)^n + B(2)^n - (3/2)n + 3/4$

Compute A, B using $f(3)$ and $f(4)$:

\[3 = f(3) = -A + 8B - 9/2 + 3/4\]
\[-A + 8B - 9/2 + 3/4 = 3\]
\[8B = 3 + 9/2 - 3/4 + A\]
\[8B = 12/4 + 18/4 - 3/4 + A\]
\[8B = 27/4 + A\]
\[8 = f(4) = A + 16B - 6 + 3/4\]
\[A + 16B - 6 + 3/4 = 8\]
\[A + 2(27/4 + A) - 6 + 3/4 = 8\]
\[3A + 54/4 - 24/4 + 3/4 = 32/4\]
\[3A = 32/4 - 3/4 + 24/4 - 54/4\]
\[3A = -1/4\]
\[A = -1/12\]
\[8B = 27/4 - 1/12\]
\[8B = 81/12 - 1/12\]
\[8B = 80/12\]
\[B = 10/12\]

$f(n) = (-1/12)(-1)^n + (10/12)(2)^n - (3/2)n + 3/4$

Checking these for small values of n (to avoid arithmetic and algebraic errors):

\[f(3) = (-1/12)(-1)^3 + (10/12)(2)^3 - (3/2)3 + 3/4\]
\[f(3) = 1/12 + 80/12 - 9/2 + 3/4\]
\[f(3) = 1/12 + 80/12 - 54/12 + 9/12\]
\[f(3) = 36/12 = 3\]

\[f(4) = (-1/12)(-1)^4 + (10/12)(2)^4 - (3/2)4 + 3/4\]
\[f(4) = -1/12 + 160/12 - 12/2 + 3/4\]
\[f(4) = -1/12 + 160/12 - 72/12 + 9/12\]
\[f(4) = 96/12 = 8\]

\[f(5) = (-1/12)(-1)^5 + (10/12)(2)^5 - (3/2)5 + 3/4\]
\[f(5) = 1/12 + 320/12 - 15/2 + 3/4\]
\[f(5) = 1/12 + 320/12 - 90/12 + 9/12\]
\[f(5) = 240/12 = 20\]

The closed form is correct.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4 divide and conquer recurrences from various sources
\problem 

Give orders of growth for the following divide-and-conquer recurrences:

\bparts

\ppart
$f(n) = 2f(n/2) + 3$

{\bf Solution:}
Using the Master Theorem, $f(n) = af(n/b) + cn^d$,
$a = 2$, $b = 2$, $c = 3$, $d = 0$, $b^d = 1$, so
$a = 2 > b^d = 1$, so $f(n) = \Theta(n^{{log_b}a})$, so
$f(n) = \Theta(n^1) \rightarrow f(n) = \Theta(n)$

\ppart

$f(n) = 2f(n^{{1}\over{3}}) + n $

{\bf Solution:}
First perform a change of variables.  Set $n = 2^m$ and therefore
$m = log_2 n$.  Then
\[f(2^m) = 2f(2^{m^{{1}\over{3}}}) + 2^m\]
\[f(2^m) = 2f(2^{{m}\over{3}}) + 2^m\]
Set $S(m) = f(2^m)$. Then
\[S(m) = 2S(m/3) + 2^m\]
This would seem to fall in case 3 of the master theorem.
Thus we need to find $c < 1$ such that $2 * 2^{({{m}\over{3}})} < c * 2^m$ for
large $m$.  This means that:
\[2^{{{m}\over{3}} + 1} <  c * 2^m\]
\[{{m}\over{3}} + 1 < c * m\]
Pick $c = {{1}\over{2}}$ and this is certainly true for $m>6$.
Applying the Master theorem, $S(m) = \Theta(2^m)$, so 
$f(n) = \Theta(n)$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5 injections, bijections, surjections, see ps7 fall97
\problem 

For each of the following functions, $f: \reals \rightarrow \reals$, determine whether it is an injection, surjection, or bijection and give the inverse if it exists.  (The inverse of a function is defined in Rosen page 64).

\bparts

\ppart
$f(x) = sin(x)$

{\bf Solution:}
$f(x) = sin(x)$ is not an injection because it maps
$0$ and $\pi$ to $0$.  It is not a surjection because
it maps $\reals$ onto $[-1,1]$.  Therefore it is not a 
bijection and does not have an inverse. 


\ppart
$f(x) = {{x+2}\over{x^2 + 4}}$

{\bf Solution:}
$f(x) = {{x+2}\over{x^2 + 4}}$ is not an injection because
it maps $0$ and $2$ to ${1}\over{2}$.  It is not a surjection
because $1$ has no pre-image.  $x^2 + 4 = x+2$ has no
real solutions.  Therefore it is not a bijection and
does not have an inverse.

\ppart

$f(x) = \begin{cases}
        {\ln x} & \text{if $x > 0$},\\
        0 & \text{if $x = 0$},\\
        {e^x} & \text{if $x < 0$}
        \end{cases}$

{\bf Solution:}
This function is not an injection because $ln {{1}\over{2}}$ and
$e^{{1}\over{2}}$ both map to ${1}\over{2}$.  It is a
surjection because for any $x \in \reals$, a pre-image of 
$x$ is $e^x$ for $x \neq 0$, and $0$ for $x=0$.  

\ppart

$f(x) = x^3 + 2$

{\bf Solution:}
$f(x) = x^3 + 2$ is an injection because $x \neq y \rightarrow
x^3 \neq y^3 \rightarrow x^3 + 2 \neq y^3 + 2$.  The function is
a surjection because for every $x \in \reals$  $\exists y = (x-2)^{{1}\over{3}}$.  Therefore $f$ is a bijection.  It's inverse is 
$(x-2)^{{1}\over{3}}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6 countable, uncountable set via diagonalization
\problem 

Consider the set of binary strings of infinite length (strings of zeroes
and ones).  Prove that the set of such strings with at most
$501$ ones in them is countable.
(Hint: how might you list these numbers?)

{\bf Solution:}
Let $A$ be the set of infinite binary strings with at most $501$ ones 
in them.
For any arbitrary $x>0$, only a finite number of elements of $A$
have all of their ones occur before the $x$th digit.
(i.e., only 2 have all ones before the $2$nd digit, specifically
$1000000$\dots and $000000$\dots)  Let $A_x$ be the set of those elements in $A$
such that all of their ones occur before the $x$th digit.
Each $A_x$ is a finite set, and a subset of $A$.
For any element $a \in A$, look at the position of the last one in $a$.
If that one is in position $i$ then $a \in A_{i+1}$.  Therefore, every 
element of $A$ appears in at least one $A_x$.  
To list all of the elements in $A$, first list all of the elements
in $A_1$, then all of the elements in $A_2$, then all of the
elements in $A_3$ etc, removing duplicates.
Since each $A_x$ is finite, the list is a valid list.
Thus a list has been generated for all elements in
$A$ and therefore $A$ is countable.

\problem 
Consider the set of binary strings of infinite length (strings of zeroes
and ones).  Define $A_n$ to be the set of binary strings such that, at any
point in the string, at most $1/n$ of the preceding numbers can be $1$.
So $A_1$ is the set of all binary strings of infinite length, since at any
point, at most all of the preceding numbers can be $1$.  $A_2$ is the set
of strings such that at any point, at most half of the preceding terms
can be $1$.  For instance, the first element of every string in  $A_2$ must 
be 0, and of the first three elements, at most $1$ can be $1$.  In general,
the first $n-1$ elements of $A_n$ must be $0$.
As a further example, the string $010101000$... $ \in A_2$, but the string
$0101011000$... $\not\in A_2$.

Prove that $A_{501}$ is uncountable.

{\bf Solution:}
The proof is by diagonalization.  Assume for the purposes of
contradiction that the set is countable.  Then there must be
a way to list the elements in order.  Construct such a list, using
a mapping function such that $f(i)$ represents the $i$th element in
the list.  Now construct a number $a$ as follows.  For each $f(i)$, set
the $501(i)$th element of $a$ to be the opposite of the $501(i)$th element
of $f(i)$.  For all elements of $a$ not set in this manner, set them to $0$. 
Since at any point, there are at least $500$ zeroes for every one, $a$ is 
in $A_{501}$.  Therefore it must appear in this list at $a = f(j)$.  However,
$f(j)$ and $a$ differ on the $501(j)$th element of the string, so
$a \neq f(j)$, and a contradiction is reached.  Therefore $a$ cannot be in
the list and the elements of $A_{501}$ cannot be listed, therefore $A_{501}$ is
uncountable.

\end{problems}

\end{document}









