\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{graphpap}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{2}                    % !! start the paper

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

\begin{problem}

The goal of this problem is to translate some assertions about binary
strings into logic notation.

The domain of discourse is all finite-length binary strings:
$\lambda$, 0, 1, 00, 01, 10, 11, 000, 001, \ldots.  (The symbol
$\lambda$ denotes the empty string.)  In your translations, you may
use all the ordinary logic symbols as well as variables, =,
parentheses, and the symbols 0, 1, and $\lambda$.  Two strings placed
side-by-side denote the concatenation of those strings; for example,
$0x$ is the concatenation of $0$ and the binary string represented by
the variable $x$.

Here are some examples of formulas and their English translations.
Names for these predicates are listed in the third column so that you
can reuse them in your solutions, as we have done in the third example.

\begin{center}
\begin{tabular}{lclcl}
Formula & \hspace{0.25in} & Meaning & \hspace{0.25in} & Name \\ \hline
$\exists z\ (xz = y)$ & & $x$ is a prefix of $y$ & & \text{PREFIX}(x, y) \\
$\exists u \exists v\ (uxv = y)$ & & $x$ is a substring of $y$ & & \text{SUBSTRING}(x, y) \\
$\text{PREFIX}(x, 0x)$ & & $x$ contains only 0s & & \text{ALL0}(x)
\end{tabular}
\end{center}

\begin{problemparts}

\problempart $x$ consists of three copies of some string.

\solution{
$\exists y\ (x = yyy)$
}

\problempart $x$ is an even-length string of 0's:

\solution{
$\text{ALL0}(x) \wedge \exists y\ (x = yy)$
}

\problempart $x$ does not contain both a 0 and a 1

\solution{
$\neg (\text{SUBSTRING}(0, x) \wedge \text{SUBSTRING}(1, x))$
}

\problempart $x$ is the binary representation of $2^k + 1$ for some
integer $k \geq 0$.

\solution{
$(x = 10) \vee (\exists y\ (x = 1y1 \wedge \text{ALL0}(y)))$
}

\end{problemparts}

\end{problem}

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

\begin{problem}

A {\em winning configuration} in the game of Mini-Tetris is a complete
tiling of a $2 \times n$ board using only the three shapes shown
below:

\bigskip
\centerline{\includegraphics[height=0.5in]{rec2-tetrispieces}}
\bigskip

For example, here are several possible winning configurations on a $2
\times 5$ board:

\bigskip
\centerline{\includegraphics[height=1.25in]{rec2-2x5wins}}
\bigskip

\begin{problemparts}

\problempart Let $T_n$ denote the number of different winning
configurations on a $2 \times n$ board.  Determine the values of
$T_1$, $T_2$, and $T_3$.

\solution{
$T_1 = 1$, $T_2 = 3$, and $T_3 = 5$.
}

\problempart Express $T_n$ in terms of $T_{n-1}$ and $T_{n-2}$.

\solution{Every winning configuration on a $2 \times n$ board is of
one of the following three types:

\bigskip
\centerline{\includegraphics[height=2in]{rec2-types}}
\bigskip

\noindent There are $T_{n-1}$ winning configurations of the first
type, and there are $T_{n-2}$ winning configurations of the second and
third types.  Overall, the number of winning configurations on a $2
\times n$ board is:

\begin{eqnarray*}
T_n & = & T_{n-1} + 2 T_{n-2}
\end{eqnarray*}
}

\problempart Prove that the number of winning configurations on a $2
\times n$ Mini-Tetris board ($n \geq 1$) is:

\begin{eqnarray*}
T_n & = & \frac{2^{n+1}+(-1)^n}{3}
\end{eqnarray*}

\solution{The proof is by strong induction on $n$, with the induction
hypothesis $T_n = (2^{n+1}+(-1)^n) / 3$.  The hypothesis is true for
$n = 1$ and $n = 2$, since we determined above that $T_1 = 1 =
(2^{1+1}+(-1)^1)/3$ and $T_2 = 3 = (2^{2+1}+(-1)^2)/3$.

Now suppose $n \geq 2$ and assume that the hypothesis holds for all $k
< n$.  Starting from the equation derived in the preceding problem
part, we have:

\begin{eqnarray*}
T_n	& = &	T_{n-1} + 2 T_{n-2} \\
	& = &	\frac{2^n+(-1)^{n-1}}{3} +
		2 \cdot \frac{2^{n-1}+(-1)^{n-2}}{3} \\
	& = &	\frac{2^n-(-1)^n}{3} +
		\frac{2^n+2(-1)^n}{3} \\
	& = &	\frac{2^{n+1}+(-1)^n}{3}
\end{eqnarray*}

\noindent We use the induction hypothesis twice in the second step,
and then simplify in the third and fourth steps.  This completes the
inductive step.  By strong induction, the hypothesis holds for all $n
\geq 1$.  }

\end{problemparts}

\end{problem}

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

\begin{problem}  %f01-ps2-6

A chocolate bar consists $m \times n$ squares of chocolate arranged in
a rectangular grid.  Your job is to break the bar into $mn$ individual
squares.  You can only split one piece of chocolate at a time using a
either a horizontal or vertical break.

For example, suppose that the chocolate bar is $2 \times 2$.  The
first split makes two pieces, both $2 \times 1$.  Each of these pieces
requires one more split to form single squares.  Therefore, three
splits suffice to break a $2 \times 2$ bar into individual squares.

\begin{problemparts}

\problempart Use strong induction to prove that $m n - 1$ splits
suffice to break an $m \times n$ chocolate bar into individual
squares.

\solution{This theorem does not immediately lend itself to an induction
proof, since there are two variables.  In general, propositions involving
several natural-valued variables can often be proved by using a sort of
nested induction.  However, in this case, we can get by with a
single-variable induction and a trick.

Intuitively, to break up a big chocolate bar, we need one split to
make two pieces, and then we can break up the two pieces recursively.
This suggests a proof using strong induction on the {\em size} of the
chocolate bar, where size is measured in chocolate squares.  Now
instead of a problem involving two variables (the two dimensions), we
have a problem in one variable (the size).  With this simplification,
we can prove the theorem using strong induction.

\begin{proof}
The proof is by strong induction on the size of the chocolate bar.  Let
$P(k)$ be the proposition that a chocolate bar of size $k$ requires at
most $k - 1$ splits.  

\emph{Base case, $k=1$}: $P(1)$ is true because there is only a single
square of chocolate, and $1 - 1 = 0$ splits are required.

\emph{Induction step}: We suppose $k \geq 1$ and any chocolate bar of size
$s$, where $1 \leq s \leq k$, requires at most $s-1$ splits.  We must now
show there is a way to split a chocolate bar of size $k+1$ with at most
$k$ splits.

To do this, first break the chocolate bar of size $k+1$ into two smaller
pieces of size $p$ and $q$ where $p + q = k + 1$.  This is certainly
possible because the size of the bar is at least two.  Now the pieces of
sizes $p$ and $q$ are between one and $k$, so by strong induction,
breaking these two pieces into single squares requires only $p - 1$ and $q
- 1$ splits, respectively.  The total number of splits required to break
the bar of size $k+1$ into single squares is therefore at most $1 + (p -
1) + (q - 1) = p + q - 1 = (k + 1) - 1 = k$.

This shows that $P(k)$ implies $P(k+1)$, and the claim is proved by
strong induction.
\end{proof}
}

\problempart Do there exist an $m$ and $n$ such that an $m \times n$
chocolate bar can be broken into individual squares using {\em fewer}
than $mn - 1$ splits?

\solution{The proof really shows that exactly $s - 1$ splits are
needed.  Observe that in the induction step, no matter how we split
the bar into smaller bars of size $p$ and $q$, exactly $1 + (p - 1) +
(q - 1) = s - 1$ splits are required.}
\end{problemparts}

\end{problem}

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

\begin{problem}
Use the least-number principle to prove that there are no positive
integers $x$, $y$, and $z$ such that:

\begin{eqnarray*}
4x^3 + 2y^3 & = & z^3
\end{eqnarray*}

\solution{The proof is by contradiction and the least-number
principle.  Suppose that there is at least one solution.  Then, by the
least number principle, we can pick a solution $(x, y, z)$ such that
$x + y + z$ is as small as possible.

Now we make long chain of elementary deductions to show that $x$, $y$,
and $z$ must all be even.  First, we show that $z$ is even:

\[
2 \mid (4x^3 + 2y^3) \Rightarrow 2 \mid z^3 \Rightarrow 2 \mid z
\]

\noindent Next, we show that $y$ is even:

\[
2 \mid z \Rightarrow 8 \mid z^3 \Rightarrow 4 \mid (z^3 - 4 x^3)
	\Rightarrow 4 \mid 2y^3 \Rightarrow 2 \mid y^3 \Rightarrow 2 \mid y
\]

\noindent Finally, we show that $x$ is even:

\[
2 \mid y \Rightarrow 8 \mid y^3 \Rightarrow 8 \mid (z^3 - 2 y^3)
	\Rightarrow 8 \mid 4 x^3 \Rightarrow 2 \mid x^3 \Rightarrow 2 \mid x
\]

\noindent Therefore, $x/2$, $y/2$ and $z/2$ are all positive integers.
Furthermore, $(x/2, y/2, z/2)$ is another solution to the equation:

\begin{eqnarray*}
4x^3 + 2y^3 & = & z^3 \\
\Rightarrow \quad \frac{4x^3 + 2y^3}{2^3} & = & \frac{z^3}{2^3} \\
\Rightarrow \quad 4 \left(\frac{x}{2}\right)^3 +
	2 \left(\frac{y}{2}\right)^3& = & \left(\frac{z}{2}\right)^3
\end{eqnarray*}

\noindent However, $x/2 + y/2 + z/2 < x + y + z$.  This contradicts
our initial choice of solution.  Therefore, our supposition must have
been wrong, which means that there are no positive integral
solutions.}

\end{problem}

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


\begin{problem}
A self-proclaimed ``great logician'' has invented a new quantifier, on
par with $\exists$ (``there exists'') and $\forall$ (``for all'').
The new quantifier is symbolized by $\exists!$ and read ``there exists a
unique''.  The proposition $\exists!\, P(x)$ is true iff there is
\emph{exactly one} $x$ in the domain of discourse for which $P(x)$ is
true.  The logician has noted, ``There used to be two quantifiers, but
now there are three!  I have extended the whole field of mathematics
by 50\%!''

Rewrite the proposition $\exists! x\, P(x)$ using only the traditional
symbols ($\forall$, $\exists$, $\wedge$, $\vee$, $\implies$, $\neg$,
$\iff$) together with variables, parentheses, $=$, and $P$.

\solution{
Many solutions are possible.  Here is one:

\[
\exists x\ (P(x) \wedge \forall y\ (P(y) \implies x = y))
\]
}

\end{problem} 

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

\end{document}
