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

\begin{document}
\pset{6}{March 17, 1998}{Tuesday, March 31}

{\bf Reading assignment: Rosen sections 1.6-1.7, 5.1-5.3 }

\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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.

\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$.

\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$.  It follows that $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)$.
\ppart
Set up a recurrence relation obeyed by~$f(n)$(for $n\geq 3$).
\ppart
Solve your recurrence to find a closed form for~$f(n)$(for $n\geq 3$).

\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$

\ppart

$f(n) = 2f(n^{{1}\over{3}}) + 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)$

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

\ppart

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

\ppart

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


\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6 + 7 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?) 

\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.

\end{problems}

\end{document}

