\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}

\renewcommand{\implies}{\longrightarrow}
\askaboutsolutions

\begin{document}
\handout{tut2}{Tutorial 2 Problems}{September 15, 2000}

%Should cover:  Quantifiers, induction, strong induction.
%Maybe tournaments, set identities,...


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\ppart Show that $(\forall x P(x)) \vee (\forall x Q(x))$ is not logically
equivalent to $\forall x (P(x) \vee Q(x))$ \\
(that is, that the universal quantifier does not distribute over OR).

\solution{
\medskip
\textbf{Solution:}
Even if $\forall x (P(x) \lor Q(x))$, 
there may be two elements, $c_1$ and $c_2$, such that 
$P(c_1) \land \neg Q(c_1) \land \neg P(c_2) \land Q(c_2)$, 
and thus, $\neg (\forall x P(x) \lor \forall x Q(x))$. 

For example, suppose the universe of discourse is $\mathbb{N}$,
$P(x)$ is the proposition ``$x$ is even,'' and $Q(x)$ is the
proposition ``$x$ is odd.''  
It is not true that every natural number is even 
(i.e., $\neg \forall x P(x)$), 
nor is it true that every natural number is odd 
(i.e., $\neg \forall x Q(x)$). 
However, every natural number is either even or odd 
(i.e., $\forall x (P(x) \lor Q(x))$). 
}
\ppart Show that the existential qualifier does distribute over OR.

\solution{
\medskip
\textbf{Solution:}
This problem asks us to prove $\exists x (P(x) \lor Q(x))
                \Longleftrightarrow \exists x P(x) \lor \exists x Q(x)$. 

\textit{Proof:} 
Suppose that $\exists x (P(x) \lor Q(x))$. \\
By existential instantiation, for some $c \in U$, $P(c) \lor Q(c)$. By existential generalization, $\exists x P(x) \lor \exists x Q(x)$.

\medskip
To see the other direction, 
suppose $\exists x P(x) \lor \exists x Q(x)$. 
We proceed by cases:
\begin{description}

\item[Case 1 ($\exists x P(x)$): ]
By existential instantiation, 
$P(c)$ for some $c \in U$. 
Therefore $P(c) \lor Q(c)$, 
and by existential generalization, 
$\exists x (P(x) \lor Q(x))$. 

\item[Case 2 ($\exists x Q(x)$): ]
This is exactly analogous to the previous case. 

\item[Exhaustive cases: ]
Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.
\qed
\end{description}
}
\problem
 % Tiling, induction
\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.
  }

\ppart Show that a 7 by 7 chessboard with one square removed can be
   completely covered using L-shaped tiles.

%\solution{
%\medskip
%\textbf{Solution:}
%[[[This seems to need a special-case argument.  I don't have a nice
%argument here.  Give it a try, and if your argument is also
%boring/ugly, we can always state this as a fact.]]]
%}
\ppart Show that an n by n chessboard with one square removed can be
   completely covered using L-shaped pieces of the sort described in
   lecture, if $n > 5$, $n$ is odd, and $n$ is not divisible by 3.

%\solution{
%\medskip
%\textbf{Solution:}
%My solution sketch (but maybe you can find a nicer argument):
%I broke the problem into cases, based on whether n was 1 mod 6 or 5
%mod 6.  For 1 mod 6, a width 2 strip around 2 adjacent edges,
%not containing the square to be left blank,
%can be tiled completely (needs a little argument about handling the
%corner).
%That reduces the problem to a smaller 5 mod 6 case.
%For 5 mod 6, (that means at least 9) I had to remove a width 4 strip
%and argue specially about the corner.
%That reduces the problem to the 1 mod 6 case.  (Check me.)
%}

\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.
}
%%%%%
\end{problems}
\end{document}
