%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 1}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2021}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

% start MZ
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother
% end MZ

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

% Lucy
\usepackage{boxedminipage}
\newenvironment{blank}[1]{\colorbox{shadecolor}{\strut \underline{\hspace{#1}}}}
% Lucy

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, October 1 at 2:30 pm Pacific}
\end{center}

\section*{Symbols Reference}
Here are some symbols that may be useful for this PSet. If you are using LaTeX, view this section in the template file (the code in \texttt{cs103-ps1-template.tex}, not the PDF) and copy-paste math code snippets from the list below into your responses, as needed. If you are typing your Pset in another program such as Microsoft Word, you should be able to copy some of the symbols below from this PDF and paste them into your program. Unfortunately the symbols with a slash through them (for ``not'') and font formats such as exponents don't usually copy well from PDF, but you may be able to type them in your editor using its built-in tools.
\begin{itemize}
    \item Empty set: $\emptyset$
    \item Power set: $\wp(S)$
    \item Set of Natural numbers: $\mathbb{N}$
    \item Union, intersection: $\cup$, $\cap$
    \item Equal, not equal: $x = x$, $x \neq y$
    \item Element-of, not element-of: $x \in S$, $y \not \in S$
    \item Subset-of, not subset-of: $A \subseteq B$, $A \not \subseteq C$
    \item Symmetric difference: $S \triangle T$
    \item Modular congruence: $x \equiv_k y$
\end{itemize}

LaTeX typing tips:
\begin{itemize}
    \item Set (curly braces need an escape character backslash): ${1, 2, 3}$ (incorrect), $\{1, 2, 3\}$ (correct)
    \item Exponents (use curly braces if exponent is more than 1 character): $x^2$, $2^{3x}$
    \item Subscripts (use curly braces if subscript is more than 1 character): $x_0$, $x_{10}$
\end{itemize}

\pagebreak

Problems One and Two are to be answered by editing the appropriate files
(\texttt{MuchAdoAboutNothing.sets} and \texttt{SetTheory.cpp}, respectively).
Do not put your answers to Problems One and Two in this file.

\newpage

\section*{Problem Three: Describing the World in Set Theory}

    i.
    \begin{shaded}
    Write your answer to Problem Three, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Three, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Three, part iii. here.
    \end{shaded}
    
\newpage

\section*{Problem Four: Writing Direct Proofs}
    i. 
    \begin{shaded} 
    Write your answer to Problem Four, part i. here. 
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Four, part ii. here.
    \end{shaded}
    
    iii. Fill in the blanks to Problem Four, part iii below.
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For all integers $n$, if $n$ is odd, then $n^{2}$ is odd. \\
            \emph{Proof: } Pick \blank{3cm}. We want to show that \blank{3cm}. Since $n$ is odd, there is an integer $k$ where \blank{2cm}. 
            \annotate{(Note: When following the direct proof guidelines, the first three sentences are fairly mechanical, but now we need to exercise actual creativity. It helps to look at our want-to-show to remind ourselves of our destination on this journey. It says we want to show something about $n^2$, so we will begin with the expression $n^2$, and then apply algebra to it.)}
            Then we see that
            \begin{equation*}
                \begin{split}
                    n^{2} &= \blank{4cm} \\
                          &= \blank{4cm} \\
                          &= \blank{4cm}.
                \end{split}
            \end{equation*}
            Therefore, there is an integer $m$ (namely, \blank{1.5cm}) such that \blank{1.5cm}, so \blank{1cm}\emph{(Write the ``Want to Show'' fact here to announce that you reached it.)}, as required. \qedsymbol
        \end{boxedminipage}
    \end{center}
    iv.
    \begin{shaded}
    Write your answer to Problem Four, part iv. here.
    \end{shaded}
    
\newpage

\section*{Problem Five: Writing Proofs by Contrapositive}
    i.
    \begin{shaded}
    Write your answer to Problem Five, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Five, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Five, part iii. here.
    \end{shaded}

    iv. Fill in the blanks to Problem Five, part iv. below.
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For all integers $a, b, $ and $c$, if $a^{2} + b^{2} = c^{2}$, then at least one of $a, b, $ and $c$ is even. \\
            \emph{Proof: } We will prove the contrapositive of this statement, namely, \blank{2cm}.To do so, pick \blank{1.5cm}. We want to show that \blank{1.5cm}. \\
            Since $a, b, $ and c are \blank{1.5cm}, we know by our result from the previous problem that $a^{2}, b^{2}, $ and $c^{2}$ are \blank{1cm}.\\
            Because $a^{2}$ and $b^{2}$ are \blank{1cm}, there exist integers $p$ and $q$ such that \blank{1cm}. This means that
            $a^{2} + b^{2} = $ \blank{1cm} $=$ \blank{1cm}, which means that $a^{2} + b^{2}$ is \blank{1cm}.\\
            However, as mentioned earlier we know that $c^{2}$ is \blank{1cm}. Therefore, we see that \blank{1.5cm}\emph{(Write the ``Want to Show'' fact here to announce that you reached it.)} as required.\qedsymbol 
        \end{boxedminipage}
    \end{center}
    
    v.
    \begin{shaded}
    Write your answer to Problem Five, part v. here.
    \end{shaded}
    
\newpage
\section*{Problem Six: Writing Proofs by Contradiction}
    
    i.
    \begin{shaded}
    Write your answer to Problem Six, part i. here.
    \end{shaded}
    
    ii. Fill in the blanks to Problem Six, part ii. below.
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For all integers $m$ and $n$, if $mn$ is even and $m$ is odd, then $n$ is even. \\
            \emph{Proof: } Assume for the sake of contradiction that \blank{5cm}. Since $m$ is \blank{1cm}, we know that there is an integer $k$ where \blank{1cm}. Similarly, since $n$ is \blank{1cm}, there is an integer $r$ where \blank{1cm}. Then we see that
            \begin{equation*}
                \begin{split}
                    mn &= \blank{5cm} \\
                       &= \blank{5cm} \\
                       &= \blank{5cm}
                \end{split}
            \end{equation*}
            which means that $mn$ is \blank{1cm}, but this is impossible because \blank{2cm}.\\
            We have reached a contradiction, so our assumption must have been wrong. Therefore, if $mn$ is even and $m$ is odd, then $n$ is even.\qedsymbol 
        \end{boxedminipage}
    \end{center}

\newpage

\section*{Problem Seven: Proving Existentially-Quantified Statements}

    i. Fill in the blanks to Problem Seven, part i. below.
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} There are real numbers $a$ and $b$ where $\floor{a} \cdot \ceil{b} \not= \floor{ab}$. \\ \emph{Proof: } Pick $a = $ \blank{1cm} and $b = $ \blank{1cm}. Then we see that 
            \begin{equation*} \floor{a} \cdot \ceil{b} = 
                  \floor{\blank{1cm}} \cdot \ceil{\blank{1cm}} =
                  \blank{1cm} \cdot \blank{1cm} = 
                  \blank{1cm}, \end{equation*} 
            but 
            \begin{equation*} \floor{ab} = \floor{\blank{1cm} \cdot \blank{1cm}} = \floor{\blank{1cm}} = \blank{1cm}. \end{equation*}
            Thus \blank{1cm} $\not=$ \blank{1cm}, as required. \qedsymbol
         \end{boxedminipage}
     \end{center}
            
    ii. Fill in the blanks to Problem Seven, part ii. below.
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} There exist natural numbers $a, b, c,$ and $d$ such that $a > b > c > d > 0$ and $a^2 + b^2 + c^2 + d^2 = 137.$\\
            \emph{Proof: } Pick $a = $ \blank{1cm}, $b = $ \blank{1cm}, $c = $ \blank{1cm}, and $d = $ \blank{1cm}. Then we see that 
            \begin{equation*} \blank{1cm} > \blank{1cm} > \blank{1cm} > \blank{1cm} > \blank{1cm} \end{equation*}
            and
            \begin{equation*} 
            \begin{aligned}
            \blank{1cm} ^2 + \blank{1cm} ^2 + \blank{1cm} ^2 + \blank{1cm} ^2
              &= \blank{1cm}^2 + \blank{1cm}^2 + \blank{1cm}^2 + \blank{1cm}^2 \\
              &= \blank{1cm} + \blank{1cm} + \blank{1cm} + \blank{1cm} \\ &= 137, \end{aligned} \end{equation*}
            as required. \qedsymbol
            \end{boxedminipage}
        \end{center}

\newpage

\section*{Problem Eight: Proving Mixed Universal and Existential Statements}
    i. Fill in the blanks to Problem Eight, part i. below.

    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For all integers $x$ and $y$ and any integer $k$, if $x \equiv_{k} y$, then $y \equiv_{k} x$. \\
            \emph{Proof: } Let $x, y, $ and $k$ be arbitrary integers where $x \equiv_{k} y$. We want to show that $y \equiv_{k} x$.\\
            To do so, we will show that there is an integer $q$ where \blank{6cm}. \annotate{(Notice that after stating our want-to-show as usual for a direct proof, we expanded the want-to-show to be more specific about what it means to show that. Now our want-to-show has the form of an existential (``...there exists an integer $q$...''). This is an important structural trait to focus in on. It means that in the body of the proof, we are going to have to demonstrate that such a $q$ exists very concretely by proposing a specific value for $q$.)}
            Because $x \equiv_{k} y$, we know there is an integer $r$ such that \blank{4cm}.\\
            Now, let $q = $ \blank{4cm}. \annotate{(Here it is, our announcement of the value we are proposing for $q$. Next, we need to justify to the reader that our choice works. What follows is that justification. Always do it in this order: first announce the value, then justify.)} Then we see that
            \begin{equation*}
                \begin{split}
                    y &= \blank{6cm} \annotate{(Do not write x + qk here; see below)}\\
                      &= \blank{6cm} \\
                      &= x + qk
                \end{split}
            \end{equation*}
            which is what we needed to show. \qedsymbol 
        \end{boxedminipage}
    \end{center}

    ii.
    \begin{shaded}
    Write your answer to Problem Eight, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Eight, part iii. here.
    \end{shaded}

\newpage

\section*{Problem Nine: Proof Critiques}
    i.
    \begin{shaded}
    Write your answer to Problem Nine, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Nine, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Nine, part iii. here.
    \end{shaded}
    
\newpage

\section*{Problem Ten: Multiples of Three}

    \begin{shaded}
    Write your answer to Problem Ten here.
    \end{shaded}

\newpage
    
\section*{Problem Eleven: Tiling a Checkerboard}
    i.
    \begin{shaded}
    Write your answer to Problem Eleven, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Eleven, part ii. here.
    \end{shaded}

\newpage

\section*{Optional Fun Problem: Infinite Deviation}
    \begin{shaded}
    Write your answer to the Optional Fun Problem here.
    \end{shaded}
    
\end{document}
