\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}

\newcommand{\st}{~\mid~}
\newcommand{\powerset}{\ensuremath{\mathcal{P}}}
\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 5}
\duedate{Due: Sunday February 19, 2017 at noon}

\begin{document}

\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}

{\sc Topics} Sets and Induction.
\newline

{\sc Reading} Rosen Sections 1.8, 2.1, 2.2, 5.1, 5.2.
\newline

{\sc Key Concepts}  Proof strategies,
counterexample, (constructive) example, direct proof, contrapositive
proof, proof by contradiction, sets, element, subset, empty set, power set,
Cartesian product, finite set,
union, intersection, set difference, cardinality, mathematical induction.\newline


\rule{\linewidth}{2pt}
\end{minipage} \hfill

\end{center}

\problemlist{}


\begin{problem}[1.] ({\bf 10 points})
 \begin{itemize}
	\item[(a)] Prove that for every integer $n$, if $3$ divides $n^2$ then $3$ divides $n$.
	\item[(b)] Prove that $\sqrt{3}$ is irrational.  {\it Hint: you may use the fact that fractions can be written 
	in lowest terms, and you can use the result you proved in part (a).} 
 \end{itemize}
\end{problem}

\begin{problem}[2.] ({\bf 8 points}) In this question, you'll explore power sets.  Before you start, 
review the definition from class and from the textbook (Definition 6 on page 120).
  \begin{itemize}
	\item[(a)]  Let $A$ be a set, and consider the statement \[ \left ( \{x\} \in \powerset(A)
    \right) \to \left( x \in A \right) \] The next paragraph claims to prove
  this statement. Is this proof correct? Explain why or why not.

  \begin{quote}
    Let $A$ be a set and suppose $x$ is an element of $A$. Then, by definition of the power set,
    there will be a singleton set containing $x$ in $\powerset(A)$, that is,
    $\{x\} \in \powerset(A)$. Therefore, $\{x\} \in \powerset(A) \to x \in A$.
  \end{quote}
	
	\item[(b)]  Prove or disprove the following statement. 
	
	\begin{quote}
	For all sets $A,B$, $\left( \powerset(A) = \powerset(B) \right) \leftrightarrow \left( A = B \right) $
	\end{quote}
	Clearly state whether this statement is true or false and include guiding text in
  your proof to indicate the proof strategies you're using.

  \end{itemize}

\end{problem}


\begin{problem}[3.] ({\bf 12 points})
Give counterexamples that prove that each of the following statements is {\bf false}.  Include
justification as to why your counterexamples prove this.  Your justification will probably
need to use the definition of the set operations in question.
\begin{itemize}
\item[(a)] For any sets $A$ and $B$, $A \times B \subseteq (A \cup B)$.
\item[(b)] For any sets $A, B, C$, if $A \cup C = B \cup C$ then $A = B$.
\item[(c)] For any finite sets $A$ and $B$, $| A \cup B | > |A|$.
\end{itemize}
\end{problem}



\begin{problem}[4.] ({\bf 10 points})
Find a formula for the sum
\[
\frac{1}{1\cdot 2} +\frac{1}{2 \cdot 3} + \cdots + \frac{1}{n \cdot (n+1)}
\]
and prove that it is correct for all positive integers $n$.


{\it Similar but different example, for reference: the sum $1 + 2 + 3 + \cdots + n$ is given by the formula $\frac{1}{2} n (n+1)$. To prove that this formula is correct, we proceed by mathematical 
induction over the set of positive integers.  The basis step is when $n=1$.  Here, we want to show
that $1 = \frac{1}{2} 1 (1+1)$.  To prove this, we simplify the RHS = $\frac{1}{2} \cdot 2 = 1$, as required.
For the induction step, let $n$ be an arbitrary positive integer and (as the induction hypothesis), assume
that $1 + 2+ \cdots + n = \frac{1}{2} n (n+1)$.  
We WTS that $1 + 2+ \cdots + (n+1) = \frac{1}{2} (n+1) ((n+1) + 1)$.  By the induction hypothesis, we 
can rewrite the LHS as $1 + 2+ \cdots + (n+1) = 1 + 2 + \cdots + n + (n+1) = \frac{1}{2}n(n+1) + (n+1)
= \frac{n(n+1) + 2 (n+1)}{2} = \frac{n^2 + 3n + 2}{2}$.  Factoring the numerator of this last 
expression, we see that 
$1 + 2+ \cdots + (n+1) = \frac{(n+1)(n+2)}{2} = \frac{(n+1)((n+1)+1)}{2}$, as required.  Thus the
induction is complete and the formula is correct for all positive integers $n$.
} 

\end{problem}

\begin{problem}[5.] ({\bf 10 points})
A guest at a party is a celebrity if this person is known by every other guest, 
but knows none of them. There is at most one celebrity at a party, for if there 
were two, they would know each other. A particular party may have no celebrity. 
Your assignment is to find the celebrity, if one exists, at a party, by asking only 
one type of question: asking a guest whether they know a second guest. 
Everyone must answer your questions truthfully. That is, if Alice and Bob are two 
people at the party, you can ask Alice whether she knows Bob; she must answer 
correctly. Use mathematical induction to show that if there are $n$ people at the 
party ($n$ is an integer greater than or equal to 2), 
then you can find the celebrity, if there is one, 
with (at most) $3(n - 1)$ questions. 
[Hint: First ask a question to eliminate one person as 
a celebrity. Then use the inductive hypothesis to identify a potential celebrity. 
Finally, ask two more questions to determine whether that person is actually a 
celebrity.]
%{\it (Rosen 5.1 \# 68)}

\end{problem}

\end{document}