 \documentclass[12pt,twoside]{article}

\usepackage{amsmath}

\input{../handouts/macros-course}

\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}


%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
\handout{tut2}{Mini-Quiz 1}{February 16, 2001}

\begin{enumerate}
\item Write your name:
\item ????

\end{enumerate}
\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

\handout{tut2}{Tutorial 2 Problems}{February 16, 2001}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
 % False Proofs

The following theorems are false, but where exactly are the bugs in
the proofs?

\bparts

\ppart

$\forall x \in \mathbb{R} \ \forall n \in \mathbb{N} \ x^n=1$.


\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that $x^n = 1$ for all real $x$.  In the base case, $P(0)$ holds
because $x^n = x^0 = 1$ by definition of ``zero-th power'' of a real
number.

In the inductive step, for some $n \geq 0$ we may assume that $x^k = 1$
for all real $x$ and for all integers $0 \leq k \leq n$

We must show that $x^{n+1}=1$.  By the induction hypothesis with $k=n$ and
again with $k=1$, we have $x^n=1$ and $x^1=1$.  So,
\[
x^{n+1} = x^n \cdot x^1 = 1 \cdot 1 = 1.
\]
\end{proof}

\solution{
\textbf{Solutions:}
The proof of the induction step is not correct when $n=0$.  In this
case, $k=1$ does not satisfy $0 \leq k \leq n$.  Therefore we cannot
assume by strong induction that $x^1 = 1$, which is false anyway when
$x \neq 1$.}

\ppart

Let $p$, $n$, and $x_1, x_2,\ldots, x_n$ be positive integers.  If $p
\mid x_1 x_2 \cdots x_n$, then $p \mid x_i$ for some $1 \leq i \leq
n$.


\begin{proof}
The proof by strong induction on $n$.  Let $P(n)$ be the proposition
that if $p$ divides the product $x_1 x_2 \cdots x_n$, then $p$ divides
$x_i$ for some $1 \leq i \leq n$.

\emph{Base case}. $P(1)$ is trivial: if $p$ divides the length one product
$x_1$, then $p$ divides $x_1$.

In the inductive step, assume $P(1), \ldots, P(n)$ to prove $P(n+1)$.

So suppose that $p \mid x_1x_2\cdots x_{n+1}$.  Let $y_n = x_n
x_{n+1}$, so $x_1x_2\cdots x_{n+1} = x_1x_2\cdots x_{n-1}y_n$.  Since
the right side of this equality is a product of $n$ terms, we have by
induction that $p$ divides one of them.  If $p \mid x_i$ for some $i <
n$, then we have the desired $i$.  Otherwise $p \mid y_n$.  But since
$y_n$ is a product of the two terms $x_n, x_{n+1}$, we have by strong
induction that $p$ divides one of them.  So in this case $p \mid x_i$
for some $i = n$ or $i = n+1$.
\end{proof}

\solution{
\textbf{Solutions:}
The statement ``we have by strong induction that $p$ divides one of them''
is the place where the proof breaks down: it appeals to strong induction
to justify applying the induction hypothesis for $2=k\leq n$.  But the
base case was $n=1$, so we can't assume $2 \leq n$.  Note that the
reasoning above is fine for every $n\geq 2$, so the whole proof would be
fine if we had an argument to prove the claim for $n+1=2$.  But of course
we can't prove it for $n+1=2$ because it isn't true: let $p=6, x_1 =2, x_2
=3$.  Even though the reasoning is fine for every $n\geq 2$, the fact that
it failed for $n=1$ let us deduce a patently false result.}



\ppart Consider the following recursive definition of the set $F$
    of full binary trees:
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item A single node is in $F$.
      
    \item If $t$ and $t'$ are in $F$, then the structure formed from
      $t$, $t'$, and a single new node, with an arrow labeled
      ``left'' from the new node to $t$ and another arrow labeled
      ``right'' from the new node to $t'$, is also in $F$.
    \end{enumerate}

    The recursive definition of the set $F$ of full binary trees is
    similar to the one for binary trees, except that we only allow the
    recursive definition step that includes both a left and a right
    child.


    Find the flaw in the following proof.  Define the \emph{height} of
    a binary tree to be 0 for a single node, otherwise one more than
    the larger of its two children's heights.

    \begin{claim*}
      Any height-$n$ binary tree has exactly $2^n-1$ nodes.
    \end{claim*}
    \begin{proof}
      By induction.  The base case is clear.  For the inductive step,
      assume it is true for height-$n$ binary trees.  Putting two of
      them together under a new node gives a height $n+1$ binary tree
      which has $2*(2^n-1)+1=2^{n+1}-1$ nodes.  This proves the
      inductive step.
    \end{proof}


    \solution{
\textbf{Solutions:}
      The basic problem here is that we are building \emph{some}
      height $n+1$ binary tree, but we are not showing the theorem for
      \emph{all} height $n+1$ binary trees.  There are height $n+1$
      trees that are \emph{not} assembled from two height $n$ trees:
      for example, I could have a height $n$ left subtree and a height
      zero right subtree.

      This general flaw, of building some but not all of the possible
      ``bigger instances,'' is known as \emph{buildup error}.
      }
  
\ppart A false proof about 2n by 2n tilings.

\begin{claim*}
  For $n \in \nats, n\geq 1$, any $2n \times 2n$ square grid can be
  tiled by L-shaped tiles such that any particular square is left
  untiled.
\end{claim*}

\begin{proof}
  The proof is by strong induction on $n$.  Let $P(n)$ be the
  predicate: ``Any $2n \times 2n$ square grid can be tiled by L-shaped
  tiles such that any particular square is left untiled''.
  \begin{description} 
  \itemsep 0 \baselineskip
  \item[Base Case:] \mbox{} \\ %
    The base case, for $n = 1$, is very simple: just use one tile.
  \item[Inductive Step:] \mbox{} \\ %
    Assume that the claim is true for all square grids smaller than
    $2n$, and we prove it for the $2n \times 2n$ square grid.  This
    follows the proof of the $2^n \times 2^n$ case: Given a $2n \times
    2n$ square grid, with one square designated to be left untiled, we
    construct a tiling (using L-shaped tiles) for all the other
    squares, as follows: Divide the square grid up into four
    quadrants, each $n \times n$.  By the inductive hypothesis (since
    $n < 2n$ for all $n \geq 1$), we can tile each of these quadrants
    (with the L-shaped tiles) completely, except for one square of our
    choice.  For the quadrant with the square to be left untiled,
    choose that square.  For the others, choose the squares at the
    corner where the quadrants meet.  This forms an L-shaped space at
    the center of the $2n \times 2n$ square grid, which can be filled
    by a single L-shaped tile.  Thus, the entire $2n \times 2n$ square
    grid is tiled, except for the square designated.
  \end{description}
\end{proof}
Point out any logical errors in this proof (that is, not simply places
where some steps were skipped, but where there is actually an error,
though you are free to point out places where more steps should have
been included for clarity).  Then, either construct a correct proof,
or show that the claim is false.

\solution{
\medskip
\textbf{Solution:}
  The error in the proof is that we erroneously invoke the induction
  hypothesis.  The inductive hypothesis states that we can tile all
  square grids of size $2m \times 2m$, for all $m \in \nats, m < n$.
  That is, we can tile all square grids of even size that are smaller
  than the $2n \times 2n$ square grid.  When we invoke the induction
  hypothesis, we use it to claim that we can tile an $n \times n$
  square grid.  The problem occurs when $n$ is odd.

  In fact, the claim is false.  Consider $n = 3$, \ie a $6 \times 6$
  square grid.  The grid contains $36$ squares which is divisible by
  $3$ the number of squares of an L-shaped tile.  Thus, it is not
  possible to tile such a grid so that exactly one particular square
  is left untiled.
  }
\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
% Induction
\ppart Prove that $2^0 + 2^1 + \cdots + 2^n = 2^{n+1}-1$, for every $n \in N$.

\solution{
\medskip
\textbf{Solution:}\\
The proof is by induction:\\
Inductive Hypothesis P(n): $2^0 +  2^1 + \cdots + 2^n = 2^{n+1}-1$\\
Base Case: n=0.  $2^0 = 2^{1}-1$. So the base case works.\\
Inductive Step: Assume P(n) in order to show P(n+1) is true.\\
P(n+1) says that $2^0 +  2^1 + \cdots + 2^{n} + 2^{n+1} = 2^{n+2}-1$.\\
From our inductive hypothesis, we know that the first $n+1$ terms of the above equation sum up to $2^{n+1}-1$, so let's substitute that in to P(n+1):\\
\begin{eqnarray*}
2^{n+1}-1 + 2^{n+1} & = & 2*(2^{n+1}-1)\\
& = & 2^{n+2}-1\\
\end{eqnarray*}
p(n+1): $2^{n+2}-1 = 2^{n+2}-1$. We have used P(n) to show that P(n+1)
is true, so the proof is complete.
}
\ppart Come up with a formula for $3^0 + 3^1 + \cdots + 3^n$, and prove
your formula.

\solution{
\medskip
\textbf{Solution:}
The formula is $\frac{3^{n+1} - 1}{2}$.  The proof by induction is nearly identical to the one above.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%\problem \textbf{ Structural Induction}
%
%Definition: the set of rooted trees $T$\\
%1. A single node is in $T$\\
%2. if $t_1,t_2,\cdots,t_i$ are in $T$, then an addition of a root node $r$
%and arrows connecting each $t_j$ $1 \leq j \leq i$ to $r$ to be
%a child (subtree) of $r$ is also in $T$\\
%
%Use structural induction to prove that the numbers of edges in
%any rooted tree is exactly one fewer than the number of nodes.

\problem \textbf { Induction and Recursive Algorithms}

{\bf Procedure} $binary~search(x,i,j)$\\
$m:=\lfloor(i+j)/2\rfloor$\\
{\bf if} $x=a_m$ {\bf then}\\
$~~~~location:=m$\\
{\bf else if} ($x<a_m$ and $i<m$) {\bf then}\\
$~~~~binary~search$($x,i,m-1$)\\
{\bf else if} ($x>a_m$ and $j>m$) {\bf then}\\
$~~~~binary~search$($x,m+1,j$)\\
{\bf else } $location:=0$

The above procedure searches $x$ in a sequence $a_1,a_2,\ldots,a_n$
(when called with $i=1$, $j=n$).
Prove by (strong) induction that the binary search procedure 
sets $location$ to an index $i$ such that $a_i=x$, if there is such
an index, and otherwise sets $location$ to 0. 

\solution{
\medskip
\textbf{Solution:}\\
Proof by Strong Induction:\\

\textbf{P(n):} The binary search procedure correctly searches a list of length $n$ such that the $location$ variable is set to $i$, where $a_i=x$, if such an index exists, and otherwise $location$ is set to 0.\\

\textbf{Base Case:} P(1) - Calling binary search on an array consisting of one element.  If that element is equal to $x$, then, according to the first \textit{if statement}, $location$ will be set equal to $\lfloor(i+2)/2\rfloor=\lfloor(1+1)/2\rfloor=1$, as desired.  If, however, $a_1 \neq 1$, then since $i$ is not less than $m$ and $j$ is not greater than $m$ ($i=1, j=1, m=1$), the program would go to the final \textit{else statement}, where $location$ gets set to $0$, as desired.\\

\textbf{P(n+1):} To see that this procedure correctly searches a list
of length $(n+1)$, we need only to check that the two \textit{else if
statements} do the correct thing, because they each call binary search
on a smaller array, which, we know by our strong inductive hypothesis,
will get searched correctly.  Now, if the element we are looking for
($x$), is less than $a_m$ and $i<m$ (meaning that there are more
indices to search through), then the procedure gets called again on a
smaller array, that consisting of indices $i$ up to $m-1$.  We already
know the procedure searches this correctly by our strong inductive
hypothesis.  The second \textit{else if statement} does the same thing
if $x$ is bigger than our current element ($x>a_m$), and there is more
of the array to search through ($j>m$).  Therefore, the procedure
correctly calls itself on a smaller array, which by P(n) we know does
the correct search.  Therefore, we have show that $P(1)\vee P(2)\vee
P(3)\vee \ldots \vee P(n) \implies P(n+1)$, and our proof by strong
induction is complete.  }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    


\problem
% structural induction

\mbox{}

\bparts

\ppart

Give the structural inductive definition of the set $F$ of full
binary trees.


\solution{%
\textbf{Solution:}
  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\kill
    $\forall t \in F (P(t))$ \\
    1. (Base) $P(n)$, where $n$ is the single-node tree. \\
    2. (Inductive step) 
    $\forall t,t' \in F, (P(t) \wedge P(t') \Rightarrow P(\ms{makeboth}(t,t')))$ \\
    3. QED
  \end{tabbing}
 } 




\ppart

Define the function $\ms{numleaves}(t)$, for $t \in F$, giving the
number of ``leaves'' of the full binary tree $t$; that is,
$\ms{numleaves}(t)$, for $t \in F$, gives the number of nodes in $t$
that do not have children.  Your definition should be recursive, based
on the recursive definition of the set $F$.


\solution{
\textbf{Solution:}
We define the function $\ms{numleaves}(t)$, for $t \in F$, as
   follows:

   $\ms{numleaves}(\text{single node}) = 1$

   $\ms{numleaves}(\ms{makeboth}(t,t')) 
   = \ms{numleaves}(t) + \ms{numleaves}(t')$ }

\ppart

Define the function $\ms{numinternal}(t)$, for $t \in F$, giving the
number of ``internal'' nodes of the full binary tree $t$; that is,
$\ms{numinternal}(t)$, for $t \in F$, gives the number of nodes in $t$
that have children.  Your definition should be recursive, based on the
recursive definition of the set $F$.


\solution{
\textbf{Solution:}

   We define the function $\ms{numinternal}(t)$, for $t \in F$, as
   follows:

   $\ms{numinternal}(\text{single node}) = 0$

   $\ms{numinternal}(\ms{makeboth}(t,t')) = 
   \ms{numinternal}(t) + \ms{numinternal}(t') + 1$
}

\ppart

Prove by structural induction that for any full binary tree $t$ in
$F$, $\ms{numleaves}(t) = 1 + \ms{numinternal}(t)$.

\solution{
\textbf{Solution:}

This part is shown by structural induction on the recursion step.

   Let $P(t): \ms{numleaves}(t) = 1 + \ms{numinternal}(t)$.

   Use the structural inductive definition of part (a) to show the
   property is true. 
}

\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem I recently went to a party with my Significant Other; there
were 11 other couples there.  A lot of handshaking happened, but of
course no one shook hands with their Significant Other.  At the end,
it turned out that for every $k$ from $0$ to $22$, someone other than
me had shaken hands with exactly $k$ people.  How many people did I
shake hands with?  Prove your answer.
\bigskip

\solution{
\textbf{Solution}:
We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

\begin{proof}
By induction on $n$.

\emph{Base case, $n=1$}: There are no other couples. My wife has shaken
$0$ hands (can't shake with me). I have shaken $0$ hands ($=n-1$). (some
party!)

\emph{Induction case}: Assume $P(n-1)$ is true for some $n>1$. To prove
$P(n)$, consider a party with $n$ couples.

Someone has shaken $2n-2$ hands, i.e., with everyone in the room except
themselves and their spouse. Therefore everyone else but this couple has
shaken hands at least once. So the one who hasn't shaken hands at all must
be this person's spouse. $2n-2$ is paired with $0$.  Consider the subparty
of the remaining $n-1$ couples. I must be in this group since there cannot
be two people who shook hands $2n-2$ times or $0$ times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the number
of handshakes I see is every number between $0$ and $2n-4$. This is
because this group of people has original handshake counts of
$1,2,3,\ldots, 2n-3$. Since everyone shakes the $2n-2$ person's hand once,
we are left with handshake counts of $0,1,\ldots,2n-4$.  This is exactly
the premise of $P(n-1)$. So by the I.H. I must have shaken $n-2$ hands
within this group. Adding the one handshake with the $2n-2, 0$ couple, I
must have shaken a total of $n-1$ hands.

\end{proof}

Note that there are 24 people (12 couples)in this case.  So $n=12$, and
the answer is that I shook 11 hands.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{problems}
\end{document}

