\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{1: The Art and Language of Proof}{Due Friday, week 1}

Do \textbf{three} of the \textbf{five} problems listed here!  Prove all of your claims.


\begin{enumerate}
\item Suppose that $x$ is some variable.  Form the following four mathematical statements:
\begin{multicols}{2}
\begin{itemize}
\item $A$: the statement ``$\frac{11}{3} > x > \frac{5}{3}$.''
\item  $C$: the statement ``$x^2 = 4$.'' 
\item $B$: the statement ``$x^2 = -1$.''
\item $D$: the statement ``$x \neq 2$.''
\end{itemize}
\end{multicols}
  Which of the following statements are true?  Justify your answers.
\begin{multicols}{2}
\begin{enumerate}
\item $\forall x \in \mathbb{R}, C \Rightarrow A$.
\item $\forall x<0 \in \mathbb{R}, A \Rightarrow C$.
\item $\exists x>0 \in \mathbb{R}$ such that $C \wedge D$.
\item $\exists x\in \mathbb{N}$ such that $C \wedge D \wedge A$.
\item $\forall x\in \mathbb{Z}$, $D \Rightarrow (C \wedge D)$.
\item $\forall x\in \mathbb{Z}, (A \vee B) \Rightarrow (\neg(C \vee D))$.
\item $\neg(\exists x \in \mathbb{Q}$ such that $C \vee D$.)
\item $\neg(\forall x\in \mathbb{Q}, \neg(A \wedge B \wedge C)$.)
\end{enumerate}
\end{multicols}

\item \begin{enumerate}
\item Describe in words what the following  ``multiplicative inverses'' property of the real numbers means:
\begin{itemize}
\item \textbf{Inverses($\cdot$)}: $\forall a \neq 0 \in \mathbb{R}, \exists \textrm{ a unique } a^{-1} \in \mathbb{R} \textrm{ such that }a \cdot a^{-1} = 1$.
\end{itemize}
\item Suppose that $n$ is a natural number greater than 1.  Look at $\langle \mathbb{Z} / n\mathbb{Z}, +, \cdot\rangle$.  Show that this set satisfies the ``multiplicative inverses'' property above if and only if $n$ is a prime number. 

In other words, show that $n$ is a prime number if and only if the following property holds:
\begin{itemize}
\item \textbf{Inverses($\cdot$)}: $\forall a \neq 0 \in \mathbb{Z}/n\mathbb{Z}, \exists \textrm{ a unique } a^{-1} \in \mathbb{Z}/n\mathbb{Z}\textrm{ such that }a \cdot a^{-1} \equiv 1.$
\end{itemize}
\end{enumerate}
\item  Prove that $\sqrt{2}$ is an irrational number.


\item Take a $ 8 \times 8$ checkerboard and punch out its top-right corner (drawn below.)  Can you completely cover it with $2 \times 1$ rectangles that don't overlap and don't hang off the board?  What if you remove its top right and bottom-left corner; can you cover it with $ 2 \times 1$ rectangles then?
\begin{center}
\includegraphics[width=4in]{mc2012_prooftech_hw1_chess1.pdf}
\end{center}
\item  Consider the following solitaire game:
\begin{center}
\includegraphics[width=1in]{mc2012_prooftech_hw1_circles.pdf}
\end{center}
The picture above contains three circles drawn in the plane.  In each of the bounded regions formed by the intersections of these circles, we've placed a coin, which is white on one side and black on the other.  All of the coins start with their black side up.  
 
The moves you're allowed to perform in this game are the following:
\begin{itemize}
\item You can at any time flip all of the coins within any circle.
\item Alternately, you can at any time take any circle and flip all of its white coins over to black.
\end{itemize}
Can you ever reach the following configuration?  (Prove your claim.)
\begin{center}
\includegraphics[width=1in]{mc2012_prooftech_hw1_circles2.pdf}
\end{center}
\end{enumerate}





\end{document}