%%%%%%%%%%%%%%%%%%%%% PACKAGE IMPORTS %%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{amsmath, amsfonts, amsthm, amssymb}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{fullpage}
\usepackage{romannum}

\usepackage[x11names, rgb]{xcolor}
\usepackage{graphicx}
\usepackage{circuitikz}
\usetikzlibrary{decorations,arrows,shapes}

\usepackage{etoolbox}
\usepackage{enumerate}
\usepackage{enumitem}
\usepackage{listings}
\usepackage{array}
\usepackage{probsoln}

%%%%%%%%%%%%%%%%%%%%%%%% QUESTION # %%%%%%%%%%%%%%%%%%%%%%%%
%% This part helps number your questions and creates a    %%
%% new page with each question for the aesthetics.        %%
%% It also creates parts that helps you answer questions  %%
%% To use do: \begin{question} ... \end{question}         %%
%% and: \begin{part} ... \end{part}                       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}

\providetoggle{questionnumbers}
\settoggle{questionnumbers}{true}
\newcommand{\noquestionnumbers}{
    \settoggle{questionnumbers}{false}
}

\newcounter{questionCounter}
\newenvironment{question}[2][\arabic{questionCounter}]{%
    \addtocounter{questionCounter}{1}%
    \ifnum\value{questionCounter}=1 {} \else {\newpage}\fi%
    \setcounter{partCounter}{0}%
    \vspace{.25in} \hrule \vspace{0.5em}%
        \noindent{\bf \iftoggle{questionnumbers}{Question #1: }{}#2}%
    \vspace{0.8em} \hrule \vspace{.10in}%
}

\newcounter{partCounter}[questionCounter]
\renewenvironment{part}[1][\alph{partCounter}]{%
    \addtocounter{partCounter}{1}%
    \vspace{.10in}%
    \begin{indented}%
       {\bf (#1)} %
}{\end{indented}}

\def\indented#1{\list{}{}\item[]}
\let\indented=\endlist
\def\show#1{\ifdefempty{#1}{}{#1\\}}

%%%%%%%%%%%%%%%%%%%%%%%% SHORT CUTS %%%%%%%%%%%%%%%%%%%%%%%%
%% This is just to improve your quality of life. Instead  %%
%% of having to type long things, you can type short      %%
%% things. Ex: \IMP instead of \rightarrow to get ->      %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\IMP{\rightarrow}
\def\AND{\wedge}
\def\OR{\vee}
\def\BI{\leftrightarrow}
\def\DIFF{\setminus}
\def\SUB{\subseteq}

\newcolumntype{C}{>{\centering\arraybackslash}m{1.5cm}}
\renewcommand\qedsymbol{$\blacksquare$}
\newcommand{\pred}[1]{\textsf{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%% TITLE %%%%%%%%%%%%%%%%%%%%%%%%%%
%% This is shows the homework number, your name, your     %%
%% collaborators, and the day. If you'd prefer to not so  %%
%% your name, just comment out the "\maketitle" below     %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\vspace{-2cm}Homework 4\vspace{-0.3cm}}
\author{Insert Your Name}
\date{\vspace{-0.3cm}\today\vspace{-1cm}}

%%%%%%%%%%%%%%%%%%%%%%%% WORK BELOW %%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

%%%%%% QUESTION 1 %%%%%
\begin{question}{Collaborators}
% Please list your collaborators here; or state that you worked alone.

\end{question}

%%%%%% QUESTION 2 %%%%%
\begin{question}{English Spoofs and Confusions [18 points]}
\setcounter{section}{2}

\begin{subsection}{Lions and tigers and bears (oh my!) [6 points]}
  A grizzly bear stole a toddler from a pair of parents. The grizzly bear
  promises that he will return the child if and only if the parents correctly
  predict whether or not the grizzly will return the child.

\begin{part}
Imagine the parents predict that the child will be returned. In this case, will the bear always, sometimes, or never keep his promise? Show your reasoning. \textit{Hint: Consider the two choices that the bear can make and whether or not these choices are consistent with his promise.}

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
Imagine the parents predict that the child will \textbf{not} be returned. In this case, will the bear always, sometimes, or never keep his promise? Show your reasoning.

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
The grizzly then says ``if I am unable to keep my original promise, then I will return the child." Assume that the bear is telling the truth. What prediction should the parents make? Show your reasoning.

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{subsection}

\bigskip

\begin{subsection}{Sugar makes everything better [6 points]}
\setcounter{partCounter}{0}
  Assume the following things to be true.

Ice cream is delicious, and dessert this evening is something delicious. The
desserts which were available at the store today were ice cream and
cake. Dessert this evening was purchased at the store today.

Consider the following (incorrect) proof of the proposition ``Tonight's dessert must be ice cream.''

Tonight's dessert must be ice cream because:

(a) tonight's dessert was purchased at the
store today (by assumption), (b) and ice cream and cake were the only two desserts available at the
store today (by assumption), and (c)  we know that tonight's dessert is delicious,
(d) and ice cream is delicious (by assumption), (e) so we conclude that tonight's dessert is ice cream.

\begin{part}
Identify the most significant error in the proof and discuss why this step is incorrect. Sentences have been labeled to easily refer back to specific portions of the proof.

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
If the given statement is true, write a correct proof. If it is false, provide a counterexample.

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{subsection}

\begin{subsection}{What's wrong with this picture? [6 points]}
\setcounter{partCounter}{0}
 Consider the following statement: for all real numbers $a$ and $b$,
        if $a^2 = b^2$ then $a = b$.

        And the following spoof (incorrect proof) of the statement:

        \begin{quote}
          Let $a$ and $b$ be real numbers such that $a^2 = b^2$. Since
          $a^2 \geq 0, b^2 \geq 0$, their square root is a real number and
          nonnegative. Then, applying the square root function to both sides, we
          conclude $a = \sqrt{a^2} = \sqrt{b^2}= b$.
        \end{quote}

\begin{part}
Why is the above proof incorrect?

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
Is the original statement true or false? If the statement is true, write a correct proof. If it is false, provide a counterexample.

\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{subsection}


\end{question}

%%%%%% QUESTION 3 %%%%%
\begin{question}{Formal and English [20 points]}
In this problem, we'll practice writing both Formal and English proofs. Let your domain of discourse be integers. Define $\pred{Even}(x)$ to be true if and only if $\exists k (x=2k)$.\\ Define $\pred{divBy6}(x)$ to be true if and only if $6\mid x$.

\begin{part}
Give a predicate definition of $\pred{divBy6}(x)$, that uses an $\exists$ quantifier. [2 points]

\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
Show that $\forall x (\pred{divBy6}(x) \rightarrow \pred{Even}(x))$, using an inference proof. Let the domain of discourse for your proof be integers. \\
You may use the definitions of predicates in the problem (including your answer to part a), as well as ``algebra'' to complete the proof. [8 points]
\begin{solution}
% Your solution here
\end{solution}

\end{part}

\begin{part}
Write an English proof to show the if $6$ divides an integer $x$, then $x$ is even. Recall that English proofs don't have domains of discourse, so you need to define types for your variables. [8 points]
\begin{solution}
% Your solution here
\end{solution}

\end{part}


\begin{part}
Go through your English proof, for each sentence in it, state which step(s) of your inference proof it most closely corresponds to (it's ok if a few steps overlap or don't correspond to a particular sentence, but this shouldn't happen to a lot of steps.). [2 points]
\begin{solution}
% Your solution here
\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 4 %%%%%
\begin{question}{English Proofs (6 points)}
Provide an English proof for the following statement: \emph{For any integer $x$, $y$, and $z$, if $x+y$ is even and $y+z$ is even, then also $x+z$ is even.}


\begin{solution}
% Enter your solution here...

\end{solution}

\end{question}

%%%%%% QUESTION 5 %%%%%
\begin{question}{Set Proofs [16 Points]}
Let $A, B, C$ be arbitrary sets. For each of the following claims: if it is true, give an \textbf{English proof}. If it is false, disprove it with an English proof (If you need to disprove the statement, remember that we've seen only one proof technique in class for disproving a $\forall$).

\begin{part}
$(B \backslash A) \cup (C \backslash A) = (B \cup C) \backslash A$.

\begin{solution}
% Enter your solution here...

\end{solution}

\end{part}


\begin{part}$A \backslash (B \backslash C) = (A \backslash B) \backslash C$

\begin{solution}
% Enter your solution here...

\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 6 %%%%%
\begin{question}{I've never seen such raw power[sets]  [16 points]}
Let $S,T$ be arbitrary sets. For each of the following claims: if it is true, give an English proof. If it is false, disprove it with an English proof (if you need to disprove the statement, remember that we've seen only one proof technique in class for disproving a $\forall$).\\

\begin{part}
$\mathcal{P}(S \cup T) = \mathcal{P}(S) \cup \mathcal{P}(T) \cup \mathcal{P}(S \cap T)$

\begin{solution}
% Enter your solution here...

\end{solution}

\end{part}


\begin{part}
$\mathcal{P}(S \cap T) = \mathcal{P}(S) \cap \mathcal{P}(T)$.\\
\emph{Note: This problem is challenging. We recommend starting in advance, once we've introduced the power set definition in Friday's lecture.}

\begin{solution}
% Enter your solution here...

\end{solution}

\end{part}

\end{question}

%%%%%% QUESTION 7 %%%%%
\begin{question}{Cartesian Products [15 points]}

Let $A$, $B$, and $C$ be arbitrary sets. Prove that $A \times (B \cap C) = (A \times B) \cap (A \times C)$.

\begin{solution}
    % Enter your solution here...

\end{solution}

\end{question}

%%%%%% QUESTION 8 (EXTRA CREDIT) %%%%%
%%%%%% DELETE IF YOU ARE NOT DOING THIS PROBLEM) %%%%%
\begin{question}{Extra Credit: Matchmaker, Matchmaker, Make Me a Match}

In this problem, you will show that given $n$ red points and $n$ blue points in the plane such that no three points lie on a common line, it is possible to draw line segments between red-blue pairs so that all the pairs are matched and none of the line segments intersect.  Assume that there are $n$ red and $n$ blue points fixed in the plane.\\

% See the pdf version for the picture

A \emph{matching} $M$ is a collection of $n$ line segments connecting distinct red-blue pairs.  The \emph{total length} of a matching $M$ is the sum of the lengths of the line segments in $M$.  Say that a matching $M$ is \emph{minimal}
if there is no matching with a smaller total length.

Let $\textsf{IsMinimal}(M)$ be the predicate that is true precisely when $M$ is a minimal matching.
Let $\textsf{HasCrossing}(M)$ be the predicate that is true precisely when there are two line segments in $M$ that cross each other.

Give an argument in English explaining why there must be at least one matching
$M$ so that $\textsf{IsMinimal}(M)$ is true, i.e.
$$\exists M \textsf{IsMinimal}(M))$$
Give an argument in English explaining why
$$\forall M (\textsf{HasCrossing}(M)\to \neg \textsf{IsMinimal}(M))$$
Now use the two results above to give a proof of the statement:
$$\exists M \neg \textsf{HasCrossing}(M).$$

\emph{Note: length is defined as usual (in Euclidean space).}

\begin{solution}
% Enter your solution here...

\end{solution}

\end{question}


%%%%%% FEEDBACK %%%%%
\begin{question}{Feedback}
\begin{part}{How many hours did you spend working on this assignment?} %% (a) %%
\end{part}

\begin{part}{Which problem did you spend the most time on?} %% (b) %%
\end{part}

\begin{part}{Which problem did you find to be the most confusing?} %% (c) %%
\end{part}

\begin{part}{Any other feedback for us?} %% (d) %%
\end{part}

\end{question}

\end{document}
