\documentstyle[12pt,amssymb]{article}
\input{/a/class/6.042/spring95/macros-course}
\input{LectureNotes/mk-macros}

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

% \setcounter{page}{0}
\begin{document}
\qsol{2}{April 28, 1995}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem
Prove that if
\[\Lambda \cup \{\psi\} \models \chi \mbox{ and }
\Lambda \cup \{\phi\} \models \chi \mbox{ and }
\Lambda \models \psi\vee \phi
\]
then
\[
\Lambda \models \chi
\]

In Lecture notes $10$ section $7$, it is proved that the system is sound
and complete.  That is, $$
\Gamma\vdash A \hbox{  implies  } \Gamma\models A; \, \mbox{ and }
\Gamma\models A \hbox{  implies  } \Gamma\vdash A.$$

\begin{enumerate}
\item 	$ \Lambda \cup \{\psi\} \vdash \chi $ \hfill completeness. 
\item 	$ \Lambda \cup \{\phi\} \vdash \chi $ \hfill completeness. 	
\item 	$ \Lambda \vdash \psi\vee \phi $ \hfill completeness. 	
\item   $ \Lambda \vdash \chi $ \hfill Rule $8$ and step $1, 2, 3$.
\item   $ \Lambda \models \chi $ \hfill step $4$ and soundness. 
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Prove or disprove: $f(n)=O(g(n))$ implies $\lg(f(n)) = O(\lg(g(n)))$,
where $g(n)$ is nondecreasing, $g(1) > 1$ and $f(n) \geq 0$ for all
sufficiently large $n$.

We will assume that $f(n) \geq 1$ in this problem.
Given $f(n)=O(g(n))$, we know that there exist some constants $c$ and $n_0$, 
such that $\forall n\geq n_0$, $f(n) \leq c  g(n)$. 
Choose a constant $c_2 > \displaystyle \frac{\lg c}{\lg(g(n_0))}+1 $, so
$\lg c < (c_2 -1) \lg(g(n_0))$. Then we have $\forall n \geq n_0,$
\begin{eqnarray*}
 \lg(f(n)) & \leq & \lg(c  g(n))\\ 
	 & =& \lg c + \lg(g(n)) \\
	&<& (c_2 -1) \lg(g(n_0)) + \lg(g(n))\\
	&<& (c_2 -1) \lg(g(n)) + \lg(g(n)) \\
	&=&  c_2 \lg(g(n)) 
  \end{eqnarray*}  
The first inequality is because $f(n) \leq c  g(n)$ and $\lg(\cdot)$ is
strictly increasing.  The second to last inequality is because $n \leq n_0$,
g(n) is nondecreasing and $\lg(\cdot)$ is strictly increasing. 
Therefore, $\lg(f(n)) = O(\lg(g(n)))$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Solve the following recurrence:
\[
f(1)=f(2)=1
\]
\[
f(n)-f(n-1)+f(n-2) = 3^n
\]

This is a nonhomogenous linear recurrence. First, we isolate and solve
the homogeneous part $f(n)-4(n-1)+4(n-2) =0$. We try the exponential 
solution $f(n)=\alpha^n$. Substituting into the recurrence we get
$\alpha^n -4 \alpha^{n-1} +4 \alpha^{n-2} = 0 $.  This gives us the
characteristic equation, $\alpha^2-4\alpha+4=0$.  The roots of this
equation are $\alpha_1 = \alpha_2 = 2$. Hence,
$f(n)=c_1 2^n+c_2 n 2^n$, for some constants $c_1$ and $c_2$. 
Second, we obtain a particular solution for the nonhomogenous part. 
We try a solution of the form $c 3^n$. Substituting into the recurrence
 we get $c 3^n -4c 3^{n-1} + 4c 3^{n-2} = 3^n$, which gives us the constant
$c=9$. Now we know that the general solution has the form 
$f(n)=c_1 2^n+c_2 n 2^n + 9 \cdot 3^n$.  We solve for $c_1$ and $c_2$ using
the initial condition, $f(1) = c_1 \cdot 2 + c_2 \cdot 2 + 27 = 1$ and
$f(2) = c_1 \cdot 4 + c_2 \cdot 8 + 81 = 1$. We get $c_1 = -6, c_2=-7$.
Therefore, $f(n) = -6 \cdot 2^n -7 \cdot n2^n+3^{n+2}$.
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts
\ppart 
$S(n,k)\, k!$ is the number of ways to color $n$ (distinguishable) balls
using exactly $k$ colors.
First partition the balls into $k$ (nonempty) classes (all the balls in 
each class will be colored the same).   
By definition, there are $S(n,k)$ ways to do this.
Now assign colors to the classes.  This can be done in $k!$ ways.
(Recall that there is no simple closed-form for $S(n,k)$.)

\begin{quotation}\small
If you like, you may think of different colors as bins. 
This is the problem of throwing $n$ 
different balls into $k$ different nonempty bins. 
We studied this problem in Lecture $17$, where we noticed that the answer,
denoted $T(n,k)$, equals $k! \, S(n,k)$ where $S(n,k)$, the Stirling
number of the second kind, is the answer for {\em indistinguishable} bins.
We proceeded to derive an expression for $T(n,k)$ using inclusion/exclusion.
\end{quotation}

\ppart  
$S(n,k)\, x(x-1)\cdots (x-k+1)$ is the number ways to color 
the $n$ balls using exactly $k$ colors 
if $x > k$ colors are available.
%	how many ways are there to color
%	the $n$ balls using exactly $k$ of those colors?

This is the same as part {\bf (a)} except that the number of ways to 
assign colors to the classes is $x(x-1)\cdots (x-k+1)$.
%	\hfill {\bf Answer:} $S(n,k)\, x(x-1)\cdots (x-k+1)$.

Alternatively, we may think of first choosing the $k$ colors to use,
and then coloring as in part {\bf (a)}, which gives 
$\displaystyle {x \choose k} T(n,k) = {x\choose k} S(n,k) \, k!$, which is the same.

\ppart %Prove that
\[
x^n = \sum_{k=1}^n S(n,k)\cdot x(x-1)\cdots(x-k+1).
\]
%	by showing that the two sides agree for any positive integer $x$. 

Each side counts the  number of ways to color $n$ different balls 
using $x$ colors. 

This is clear for the LHS: there are $x$ ways to color each of the $n$ balls.

The RHS counts in an alternative way:
First choose the number $k$ of colors ($1\leq k\leq n$) actually to be used, 
then color the balls using exactly $k$ colors, as done in part {\bf (b)}.

Each side is a polynomial of degree $n$ in $x$.
Since the two sides agree for any positive integer $x$, in particular
they agree on $n+1$ points and therefore are equal---this is a an identity.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
How many permutations of ABCDEFG are there that don't contain
``$\cdots$BEG$\cdots$'' or ``$\cdots$AD$\cdots$''?

\begin{tabbing}
Define \= $X = \{ \mbox{permutations of ABCDEFG}\}$\\
\>	$Y  = \{ \mbox{permutations of ABCDEFG that contain BEG}\}$\\
\>	$Z  = \{ \mbox{permutations of ABCDEFG that contain AD}\}$
\end{tabbing}
So, we need to find 
\[
|X|-|Y \cup Z| = |X| - |Y|-|Z| + |Y \cap Z|
\]

$|X|= 7!$ is trivial. $|Y|=5!$ since you can just
consider BEG as one letter: the number of
permutations of \{A, BEG, C, D, F\} is $5!$. 
Similarly, $|Z|=6!$ and $|Y \cap Z|=4!$.\\
\hfill {\bf Answer:} $7!- 5!-6!+4! = 4224$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}


