\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth,multicol}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 7}
\duedate{Due: Saturday December 2, 2017 at 11pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Induction, Functions, and Cardinality
\newline
{\sc Reading} Rosen Sections 5.1, 5.2, 5.3, 2.3
\newline
{\sc Key Concepts} Mathematical induction,
recursive definitions, strong induction, structural
induction, basis step, induction hypothesis, induction step, strings.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\vspace{-20pt}
\begin{problem}[1.] ({\bf 6 points})
Consider each of the following attempts at proving the statement
\begin{quote}``the sum of the first
$n$ positive odd integers is $n^2$"
\end{quote}
by mathematical induction. Pretend you are the TA/tutor and grade each attempt:
give each one a score out of $6$ points and justify your decisions;
your explanations should be convincing but brief. Full credit will be awarded
for effort for each part of this this question. For reference, here is the rubric we typically
use when grading proofs:
\begin{itemize}
\item[{\bf 6 points}] Proof by induction clear, complete, and correct (base case and induction step each labelled, assumptions and goals clearly articulated, calculations well supported and explained).
\item[{\bf 5 points}] Proof by induction mostly clear, complete, and correct with minor errors or
omissions.
\item[{\bf 3 points}] Proof by induction has many required components but missing major component, e.g. basis step missing or wrong, or IH not stated or used.
\item[{\bf 1 point}] Some indication of structure of proof by induction or relevant definitions but main arguments missing or irrelevant.
\end{itemize}
\begin{itemize}
\item[(a)]
\begin{quote}
First we need a base case. Since we need to count odd numbers let us use the base case $n =1$.\\
Sum of the first $1$ odd number is $1$\\
$1^2 = 1$\\
So for this our base case of $n=1$ is true.\\
So for some $n$, the sum of the first $n$ odd numbers is $n^2$. Then $n+1$ will also be true.
\end{quote}
\item[(b)]
\begin{quote}
Base Case: $n = 1$\\
First odd number is $1$; $1^2 = 1$. True.\\
$(n + 1)^2 = n^2 + 2n + 1$\\
$n^2$ is the sum of the first $n$ odd numbers, and $2n + 1$ is the next odd number in the sequence, therefore $(n + 1)^2 =$ the sum of the first $n + 1$ odd numbers.
\end{quote}
\item[(c)]
\begin{quote}
Let the sum of the first $n$ odd integers $= n^2$\\
Prove $n=1$\\
$(1)^2 = 1$\\
Since $1$ is the only number, the sum is correct.\\
Assume $n=k$ for some $k$ greater than or equal to $1$.\\
Prove the sum of the first $k+1$ odd integers $= (k+1)^2$.\\
$1+3+...+(2^k)-1 = k^2$\\
$1+3+...+(2^k)-1 + (2^k+1) - 1 = (k+1)^2$\\
$k^2 + (2^k+1) - 1 = (k+1)^2$\\
Since the left side is the sum of the first $k+1$ odd integers, then our statement holds true for all $n$ by induction
\end{quote}
\end{itemize}
\end{problem}
\vspace{10pt}
\noindent{\it This example might help you get started: Let's look at this (other) attempted proof.
\begin{quote}
Base case: $n = 1$, The sum of the first $n$ odd numbers is $n^2 = 1$.\\
Assume: The sum of the first $k$ odd numbers is $k^2$ for $1 <= k <= p$.\\
Show: The sum of the first $k+1$ odd numbers is $(k+1)^2$:\\
The sum of the first $k+1$ odd numbers $=$ The sum of the first $k$ odd numbers $+$ The ($k+1$)'th odd number $= k^2 + (1+2*k) = k^2 + 2k + 1 = (k+1)^2$\\
QED.
\end{quote}
This would score 3 points: many of the key components of the induction proof are present, but
the induction hypothesis is not stated correctly (what's $k$? what's $p$?) and the argument doesn't make it clear where the hypothesis is used. Additional comments: in the base case
it would be useful to say what the first odd number is. Also, the formula $1 + 2k$ for the $(k+1)$th
odd number is used without explanation or justification.
}
\begin{problem}[2.] ({\bf 10 points}) The game of Nim-Move is a two-player game which is a
variant of Nim (the game we discussed in class). At the start of this game, there
are two piles, each containing $n$ stones ($n$ is a positive integer). On a player's turn, that
player picks one of the two piles and does {\bf one} of the following: either
\begin{itemize}
\item removes some positive number of stones from that pile; or
\item moves some positive number of stones (that is less than the current total number of stones
in the pile) from that pile to the other. {\it Note: if there is only one stone left in a pile, the player
cannot move this stone to the other pile.}
\end{itemize}
The player to take the last stone wins.
\begin{itemize}
\item[(a)] Explain briefly why the strategy we discussed in class ``Player 2 mirrors
whatever Player 1 does, but for the opposite pile" does {\bf not} give a winning strategy for Player
2 for Nim-Move.
\item[(b)] Formulate a (different) strategy for Player 2 that guarantees they will win the Nim-Move game. Use strong induction to prove your strategy works.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 12 points})
To extend the notion of {\bf size} to infinite sets, we've established the following definitions:
for nonempty sets $X, Y$
\begin{description}
\item[$|X| \leq |Y|$] means there's a function $f: X \to Y$ which is one-to-one.
\item[$|X| \geq |Y|$] means there's a function $f: X \to Y$ which is onto.
\item[$|X| = |Y|$] means there's a function $f: X \to Y$ which is a bijection.
\end{description}
\begin{itemize}
\item[(a)] Prove that, for any nonempty set $A$, $|A| \leq |\mathcal{P}(A)|$.
\item[(b)] Prove that, for any nonempty set $A$ which is a subset of $\mathbb{ \mathbb{Z} }$,
$|\mathcal{P}(A)| \geq |A|$. {\it Bonus (not for credit): what makes this task harder if we don't restrict
our attention to subsets of $\mathbb{ \mathbb{Z} }$?.}
\end{itemize}
\end{problem}
\vspace{10pt}
\noindent{\it This example might help you get started: We will prove that
\begin{quote}
For any nonempty sets $A, B$ if $A \subseteq B$ then $|A| \leq |B|$.
\end{quote}
{\bf Proof:} Let $A$, $B$ be arbitrary nonempty sets. Assume (towards a direct proof)
that $A \subseteq B$. We WTS that $|A|\leq |B|$, or (equivalently, according to the
definition), that there is a function with domain $A$ and codomain $B$ that is one-to-one.
Let's define the function $f: A \to B$ by $f(x) = x$. This function is well-defined because, for
each $x \in A$, $f(x) \in B$ because of our assumption that $A \subseteq B$. Moreover, this
function is one-to-one: if we consider arbitrary elements $a_1, a_2 \in A$ and assume that
$f(a_1) = f(a_2)$ then by definition of $f$, this guarantees that $a_1 = a_2$, as required.
Thus, we have found a one-to-one function with domain $A$ and codomain $B$ so $|A| \leq |B|$.
}
\begin{problem}[4.] ({\bf 12 points}) Classify each of the following sets as (exactly one of)
{\bf finite}, {\bf countably infinite}, or {\bf uncountable}. Very briefly justify your answers.
For reference sets, you may use any of the sets explicitly discussed in class or in the textbook.
\begin{itemize}
\item[(a)] The set of all bit strings that start with $01$ and end with $0$
\[
\{ 01 w 0~|~ w \in \{0,1\}^* \}.
\]
\item[(b)] The set of all functions whose domain is $\{0,1\}$ and whose codomain is $\{0,1\}^*$.
\item[(c)] The set of all functions whose domain is $\{0,1\}^*$ and whose codomain is $\{0,1\}$.
\item[(d)] The set of all strings that represent possible compiled programs as machine code (just 0s and 1s).
\end{itemize}
\end{problem}
\end{document}