\documentclass{article}
\input{/Users/brendansullivan/Documents/127-2012/preamble.tex}
\usepackage{fullpage}
\renewcommand{\theenumi}{\bf4-\arabic{enumi}\normalfont}
\renewcommand{\labelenumi}{\theenumi}
\renewcommand{\theenumii}{\theenumi\bf-\alph{enumii}\normalfont}
\renewcommand{\labelenumii}{\theenumii}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent {\large\bf Homework 4 [100 pts] \hfill 21-127 Concepts of Math \hfill due 07.20.2012}\\
\normalfont\rule{\linewidth}{0.01cm}\vspace{0.2cm}\\
{\large\bf Explain}
\begin{enumerate}
\item {\bf $\Z\Z\Z$:} Define the relation $R$ on $\Z$ by
\[ R= \setof{(x,y)\in\Z\times\Z\mid \exs k\in\N \st y=x\cdot k} \]
Prove that $R$ is reflexive, not symmetric, and transitive.\vspace{0.2cm}\\
{\bf [10 pts]}
\item {\bf Induction Production:} Let $P(n)$ be a proposition that depends on the variable $n$, which is allowed to assume any {\bf integer} value.\vspace{0.3cm}\\
For each of the following situations, you are given some kind of ``Base Cases'' and some kind of ``Inductive Implication''. Identify and explain which instances of the proposition you would {\bf necessarily} know, from those assumptions. (We are not looking for a rigorous {\bf proof}, just a short explanation and perhaps a ``conditional diagram'', like you saw in class, if that helps your argument.)\vspace{0.3cm}\\
For instance, if you were given $P(3)$ as a Base Case and $\fa n\in\N\st P(n)\imp P(n+1)$ as an Inductive Implication, a correct answer would be ``We would know $P(n)$ holds for every $n\in\N$ with $n\geq 3$.''
\begin{enumerate}
\item Base Cases: $P(-3)$. Implication: $\fa n\in\Z\st P(n)\imp P(n+1)$
\item Base Cases: $P(1)\oand P(2)$. Implication: $\fa n\in\N\st P(n)\imp P(2n)$
\item Base Cases: $P(0)$. Implication: $\fa n\in\Z\st P(n)\imp\bigl(P(n-1)\oand P(n+1)\bigr)$
\item Base Cases: $P(-1)\oand P(0)$. Implication: $\fa n\in\N\st P(n)\imp P(n+2)$.
\end{enumerate}
{\bf [10 pts]}
\item {\bf Define The Relation:} Let $S$ be the set of students in this course. For each of the following, define a relation on the set $S$ that has the specified properties. Be sure to {\bf prove} why those properties hold.\vspace{0.2cm}\\(Note: If there is no specification about a property, you do {\bf not} have to disprove it. For instance, in (b), you don't have to say anything about transitivity.)
\begin{enumerate}
\item Reflexive
\item Neither Reflexive nor Symmetric
\item Reflexive, Symmetric, and Transitive
\end{enumerate}
{\bf [10 pts]}
\end{enumerate}
\noindent\rule{\linewidth}{0.01cm}\vspace{0.3cm}
{\large\bf Apply}
\begin{enumerate}[resume]
\item {\bf 2 The Max:} Prove the following summation formula holds for every $n\in\N\cup\{0\}$:
\[ \sum_{i=0}^n 2^i = 2^{n+1}-1 \]

{\bf [15 pts]}
\item{\bf Well, I Order You To Prove The Well-Ordering! :} In this problem, you will prove the fantastically useful {\it Well-Ordering Principle} of the natural numbers.\\{\bf [25 pts]}\vspace{0.3cm}\\
{\bf Theorem:} For any {\it non-empty} subset $S\subseteq\N$, there is a {\bf least element} of $S$. That is,
\[ \fa S\subseteq\N\st S\neq\es \imp \exs \ell\in S \st \fa x\in S\st \ell\leq x \]
\begin{enumerate}
\item Using proper, logical symbolic notation, define a statement $P(n)$ that is true if and only if the following holds: whenever any subset $S\subseteq\N$ has $n$ as an element, $S$ has a least element.\\{\bf [3 pts]}
\item Prove that $P(1)$ holds.\\{\bf [4 pts]}
\item Let $k\in\N$ be arbitrary and fixed. Write down an Induction Hypothesis for a General (Strong) Induction proof.\\{\bf [3 pts]}
\item Let $S\subseteq\N$ be arbitrary and fixed. Suppose $k+1\in S$. Define the set $T=S-\{k+1\}$.\vspace{0.2cm}\\Consider {\bf Case 1:} $T=\es$. Prove that $S$ has a least element in this case.\\{\bf [4 pts]}
\item Consider {\bf Case 2:} $T\neq\es$ and $\fa x\in S\st x\geq k+1$. Prove that $S$ has a least element in this case.\\{\bf [4 pts]}
\item Consider {\bf Case 3:} $T\neq\es$ and $\exs x\in S\st x<k+1$. Use the IH to prove that $S$ has a least element in this case.\\{\bf [4 pts]}
\item Deduce that $P(k+1)$ holds. Explain why Induction applies and succesfully proves the Theorem!\\{\bf [3 pts]}
\end{enumerate}
\end{enumerate}
\noindent\rule{\linewidth}{0.01cm}\vspace{0.3cm}
{\large\bf Explore}
\begin{enumerate}[resume]
\item{\bf What the $L$? :} Consider a chessboard of size $2^n\times 2^n$, for some arbitrary $n\in\N$. Remove {\bf any} square from the board. Is it possible to tile the remaining squares with $L$-shaped triominoes?\vspace{0.2cm}\\
If your answer is {\sf Yes}, prove it using some relevant proof technique. (What do you think this could possibly be $\ldots$?)\vspace{0.3cm}\\
If your answer is {\sf No}, provide a counterexample argument. (That is, find an $n$ such that no {\it possible} way of tiling the board will work.)\vspace{0.2cm}\\
({\bf Note:} Please ask me if you don't understand the problem statement.)\vspace{0.2cm}\\
{\bf [15 pts]}
\item{\bf Mo' Brendans, Mo' Problems:} In a futuristic society, there are only two different denominations of currency: a coin worth 3 Brendans, and a coin worth 8 Brendans. There is also a nation-wide law that says shopkeepers can only charge prices that can be paid in {\bf exact change} using these two coins.\vspace{0.3cm}\\
What is the set of legal costs that a shopkeeper could charge you for a cup of coffee? Define a set $S$ that is your guess, and then prove it is correct by using induction and pointing out special cases.\vspace{0.2cm}\\({\bf Hint:} Try a bunch of small values and see what happens.)\vspace{0.2cm}\\{\bf [15 pts]}
\end{enumerate}

\end{document}
