\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\usepackage{textcomp} % to get \textcent

\newcommand{\cent}{\text{\textcent}}

\renewcommand{\reading}{Course Notes 2.  Rosen \S1.1--1.2, \S1.3
through Example 20, \S1.4, \S3.1 through Example 13, \S3.3.  In
addition, you should be familiar with sets and functions (\S1.6--1.8
through Example 20) and summation notation (pp. 229--230).}

%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutions
%\showsolutions

\begin{document}
\problemset{1}

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

\begin{problem}

Rewrite each of the following logical expressions using only the
$\implies$ and $\neg$ operators.

\begin{problemparts}

\problempart $A \wedge B$

\solution{$A \wedge B = \neg (\neg A \vee \neg B) = \neg (A \implies \neg B)$}

\problempart $A \vee B$

\solution{$\neg A \implies B$}

\problempart $A \iff B$

\solution{$A \iff B = (A \implies B) \wedge (B \implies A)$ which can be written as 

$\neg ((A \implies B) \implies \neg (B \implies A))$ according to part a.}

\end{problemparts}

\end{problem}

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

\begin{problem}

Rewrite the following assertions using only variables, logic symbols,
and arithmetic expressions involving constants, addition,
multiplication, exponentiation, and comparison.  In all parts, the
domain of discourse is $\mathbb{N}$.  In the first part, you are asked
to write a definition of a prime number.  Then, in the second and
subsequent parts, you may make use of $\text{Prime}(n)$, a predicate
that is true if and only if $n$ is a prime number.

\begin{problemparts}

\problempart $p$ is a prime number.

\solution{
\[
(p > 1)
\wedge
\neg \left( \exists m \exists n (m > 1 \wedge n > 1 \wedge mn = p) \right)
\]
}

\problempart There is no largest prime number.

\solution{
The domain of discourse is $\mathbb{Z}$.

\[
\neg \left(\exists p (Prime(p) \wedge (\forall q (Prime(q) \implies p \geq q)))
\right)
\]
}

\problempart (Goldbach Conjecture) Every even natural number $n \geq
4$ can be expressed as the sum of two primes.

\solution{
\[
\forall n 
\left(
(n \geq 4 \wedge \exists k\ n = 2k) \implies \exists p \exists q (Prime(p) \wedge Prime(q) \wedge (n = p + q))
\right)
\]
}

\problempart (Bertrand's Postulate) If $n > 1$, then there is always
at least one prime $p$ such that $n < p < 2n$.

\solution{
The domain of discourse is $\mathbb{Z}$.

\[
\forall n
\left( (n > 1) \implies (\exists p ( Prime(p)  \wedge (n < p) \wedge (p < 2n))) 
\right)
\]
}

\problempart (Fermat's Last Theorem) There are no solutions to the
equation:

\begin{eqnarray*}
x^n + y^n & = & z^n
\end{eqnarray*}

where $n > 2$ and $x$, $y$, and $z$ are positive.

\solution{
The domain of discourse is $\mathbb{Z}$.

\[
\forall x \forall y \forall z \forall n
    \left(
    (x > 0 \wedge y > 0 \wedge z > 0 \wedge n > 2)
    \rightarrow
    \neg (x^n + y^n = z^n)
    \right)
\]
}

\end{problemparts}

\end{problem}

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

\begin{problem}

Use induction to prove that the remarkable equation below holds for
every $n \in \mathbb{N}$.

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

\solution{
The proof is by induction on $n$. Let $P(n)$ be the proposition that 
\begin{eqnarray*}
(1 + 2 + \cdots + n)^2 & = & 1^3 + 2^3 + \cdots + n^3
\end{eqnarray*}

Base case: $P(0)$ is true vacuously. We must prove that $P(1)$ is true; that is, $1^2 = 1^3$. This equation holds since both sides are equal to 1.

Inductive step: for all $n \geq 1$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\begin{eqnarray*}
\left( \sum_{k=1}^{n+1} k \right)^2 & = & \left( \sum_{k=1}^{n} k + (n + 1) \right)^2 \\
                                    & = & \left( \sum_{k=1}^{n} k \right)^2 + (n + 1)^2 + 2 \left( \sum_{k=1}^{n} k \right) (n + 1) \\
                                    & = & \sum_{k=1}^{n} k^3 + (n + 1) ^ 2 + 2 \left( \frac{n(n+1)}{2}\right) (n + 1) \\
                                    & = & \sum_{k=1}^{n} k^3 + (n + 1) (n + 1 + n^2 + n) \\
                                    & = & \sum_{k=1}^{n} k^3 + (n + 1)^3 \\
                                    & = & \sum_{k=1}^{n+1} k^3 
\end{eqnarray*}

Therefore, $P(n)$ holds for all $n \geq 0$ by induction. That is, for all $n \in \mathbb{N}$:

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

}

\end{problem}

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

\begin{problem}

Let $p$ be a prime, and let $x$ and $y$ be natural numbers.  You may
assume that if $p \mid x y$, then $p \mid x$ or $p \mid y$.  Use
induction to prove the following claim.

\begin{claim}
Let $p$ be a prime, and let $a_1, a_2, \ldots, a_n$ be natural
numbers.  If $p \mid a_1 a_2 \cdots a_n$, then $p \mid a_i$ for some
$1 \leq i \leq n$.
\end{claim}

Generalizing a statement about two objects to a statement about $n$
objects in this way is a common (if mundane) application of induction.

\solution{

The proof is by induction on $n$. Let $P(n)$ be the proposition that 
\begin{eqnarray*}
\left(Prime(p) \wedge p \mid a_1 a_2 \cdots a_n\right) \implies \left(\exists i ( 1 \leq i \leq n\ \wedge\ p \mid a_i)\right)
\end{eqnarray*}

Base case: $P(1)$ is trivial and $P(2)$ is given. 

Inductive step: for all $n \geq 2$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\begin{eqnarray*}
\left(Prime(p) \wedge p \mid a_1 a_2 \cdots a_n a_{n+1}\right) & \implies & \left((p \mid a_1 a_2 \cdots a_n) \vee (p \mid a_{n+1})\right) \\
                                               & \implies & \left((\exists i ( 1 \leq i \leq n\ \wedge\ p \mid a_i)) \vee (p \mid a_{n+1})\right) \\
                                               & \implies & \left(\exists i ( 1 \leq i \leq n+1\ \wedge\ p \mid a_i)\right) 
\end{eqnarray*}
}

\end{problem}

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

\begin{problem}

Suppose that you take a piece of paper and draw a bunch of straight
lines, no one exactly on top of another, that completely cross the
paper.  This divides the paper up into polygonal regions.  Prove by
induction that you can always color the various regions using only
\emph{two} colors, so that two regions that share a boundary are
always colored differently.  Regions that share only a boundary point
may have the same color.


\solution{

Proof is by induction on $n$, i.e. the number of lines drawn. 

Base case: If $n = 0$, then there's no line drawn. So the whole paper 
is a single region which can be 
colored by one color. Thus the assertion holds. 

Inductive step: Assume the assertion holds for $n$ lines. We prove it holds for $n + 1$ lines.

Given $n + 1$ lines, remove/ignore an arbitrary line (Let's call it $l$). Now there are $n$ lines on the paper. So the 
polygonal regions can be colored using 2 colors according to the induction hypothesis. We refer to this coloring as
$coloring 1$.
Now put $l$ back and flip the colors of all the regions on one side
of it (Let's call this side $side 1$) to get $coloring 2$. We claim that coloring 2 satisfies the constraints:

This proof is by cases:
Let $R_1$ and $R_2$ be any two regions that share a boundary line. 

Case 1: If they are both on side 2 of $l$, then their colors in coloring 2 are the same as their colors in 
coloring 1. Furthermore, since they are both on the same side of $l$, they remain adjacent even after removing $l$. 
This means, according to the induction hypothesis, they have different colors in coloring 1 and thus, in coloring 2.

Case 2: If they are both on side 1 of $l$, then their colors in coloring 2 are different from their colors in 
coloring 1. But, similar to the above case, $R_1$ and $R_2$ get different colors in coloring 1 since they are both on the same side
of $l$. Thus, they have different colors in coloring 2 as well.

Case 3: If one of them (e.g. $R_1$) is on side 1 and the other ($R_2$) is on side 2 of $l$, then since
all the lines are straight and considering the fact that no line is exactly on top of another line, 
$l$ is the only boundary line they have in common. Thus, $R_1$ and $R_2$ compose a single region 
after removing $l$. But in coloring 2, the color of $R_1$ in flipped. So $R_1$ and $R_2$ have different
colors in coloring 2.

}

\end{problem}

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

\begin{problem}
The function $g : \mathbb{N} \to \mathbb{N}$ has the following
properties:

\begin{eqnarray*}
g(0) & = & 2 \\
g(1) & = & 1 \\
g(n) & = & g(n-1) + 2 g(n-2)
\end{eqnarray*}

Use strong induction to prove that $g(n) = 2^n + (-1)^n$.

\solution{

Let $P(n)$ be the proposition that 
\begin{eqnarray*}
g(n) = 2^n + (-1)^n
\end{eqnarray*}

Base case: $g(0) = 2 = 2^0 + (-1)^0$ and $g(1) = 1 = 2^1 + (-1)^1$. Thus, $P(0)$ and $P(1)$ hold.

Inductive step:
using strong induction, we assume $P(n)$ and $P(n - 1)$ hold to prove that $P(n + 1)$ is true.
\begin{eqnarray*}
g(n + 1) & = & g(n) + 2 g(n - 1) \\
         & = & 2^n + (-1)^n + 2 \left( 2^{n-1} + (-1)^{n-1} \right) \\
         & = & 2^n - (-1)^{n-1} + 2^n + 2 (-1)^{n-1} \\
         & = & 2^{n+1} + (-1)^{n-1} \\
         & = & 2^{n+1} + (-1)^{n+1} 
\end{eqnarray*}

Thus, $P(n)$ holds for all natural numbers.

}

\end{problem}

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

\begin{problem}

Three pirates are considering an attack on the {\em Pi\~{n}ata}, a
Spanish galleon laden with $n \geq 50$ pieces of gold.  Redbeard
insists that his share of the treasure must be a multiple of 7 gold
pieces, Bluebeard insists that his share be a multiple of 11 gold
pieces, and Blackbeard demands a multiple of 13 gold pieces.
Furthermore, although any of these pirates can tolerate a 
zero share (surprisingly!), 
no pirate can tolerate treasure going to waste.  If these
constraints are not all met after the attack, the pirates will surely
have a fatal quarrel.  Can the pirates safely attack the {\em
Pi\~{n}ata}?  Prove that your answer is correct.

\solution{
The answer is Yes! The proof is by strong induction on $n$, i.e. the number of gold pieces:

Let $P(n)$ be the proposition that:

\begin{eqnarray*}
\exists xyz \left( x \geq 0 \wedge y \geq 0 \wedge z \geq 0 \wedge n = 7x + 11y + 13z \right)
\end{eqnarray*}

Base cases: 
\begin{eqnarray*}
n & = & 50  =  11 + 13 \times 3 \\
n & = & 51  =  7 \times 2 + 11 + 13 \times 2 \\
n & = & 52  =  7 \times 4 + 11 + 13 \\
n & = & 53  =  7 \times 6 + 11 \\
n & = & 54  =  7 \times 3 + 11 \times 3 \\
n & = & 55  =  11 \times 5 \\
n & = & 56  =  7 \times 8 
\end{eqnarray*}

Inductive step: given that $P(i)$ is true for $n-1 \geq i \geq 50$, we prove $P(n)$ is true where $n \geq 57$.

Let $x$, $y$ and $z$ be natural numbers satisfying $n - 7 = 7x + 11y + 13z$ according to the induction hypothesis.
Then, $n$ can be written az $7(x + 1) + 11y + 13z$ and thus, $P(n)$ is true. (You may want to increase bluebeard's and 
blackbeard's shares for $n \geq 61$ and $n \geq 63$,respectively, just to be fair, though not necessary for the purpose of this
problem!)

}

\end{problem}

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

\end{document}                            

