%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan, with updates,
% edits, and simplifications by the lovely folks below.
%
% 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
% Commands slimmed down and simplified in Fall 2022 by Keith Schwarz

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{braket}
\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 --- Spring 2026}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\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{\powerset}[1]{\wp\left(#1\right)}
\newcommand{\suchthat}{\ \vert \ }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\qed}{\blacksquare}
\newcommand{\accepts}{\text{ accepts }}
\newcommand{\rejects}{\text{ rejects }}
\newcommand{\loopson}{\text{ loops on }}
\newcommand{\haltson}{\text{ halts on }}
\newcommand{\encoded}[1]{\left\langle#1\right\rangle}
\newcommand{\rlangs}{\mathbf{R}}
\newcommand{\relangs}{\mathbf{RE}}
\newcommand{\corelangs}{\text{co-}\mathbf{RE}}
\newcommand{\plangs}{\mathbf{P}}
\newcommand{\nplangs}{\mathbf{NP}}

\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

\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}}

\usepackage{boxedminipage}
\newenvironment{blank}{\colorbox{shadecolor}{\strut \underline{\ \ \ \ \ }}}

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, April 10, at 1:00 PM Pacific}
\end{center}

\section*{Symbols Reference}
Here are some symbols that may be useful for this problem set.

\begin{itemize}
    \item Empty set: $\emptyset$
    \item Power set: $\powerset{S}$
    \item Set of natural numbers: $\naturals$
    \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$
    \item Sets: $\Set{1, 2, 3}$, $\Set{n \in \naturals \suchthat n \text{ is even}}$
\end{itemize}

LaTeX typing tips:
\begin{itemize}
    \item Set (curly braces need an escape character backslash): ${1, 2, 3}$ (incorrect), $\{1, 2, 3\}$ or $\Set{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}

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

    \newpage
    
    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}

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

    \newpage
    
    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. We want to show that \blank. Since $n$ is odd, there is an integer $k$ where \blank. 
            \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 \\
                          &= \blank \\
                          &= \blank.
                \end{split}
            \end{equation*}
            Therefore, there is an integer $m$ (namely, \blank) such that \blank, so \blank \annotate{(Write the ``Want to Show'' fact here to announce that you reached it.)}, as required. \qedsymbol
        \end{boxedminipage}
    \end{center}

    \newpage
    
    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}

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

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

    \newpage

    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.To do so, pick \blank. We want to show that \blank. \\
            Since $a, b, $ and c are \blank, we know by our result from the previous problem that $a^{2}, b^{2}, $ and $c^{2}$ are \blank.\\
            Because $a^{2}$ and $b^{2}$ are \blank, there exist integers $p$ and $q$ such that \blank. This means that
            $a^{2} + b^{2} = $ \blank $=$ \blank, which means that $a^{2} + b^{2}$ is \blank.\\
            However, as mentioned earlier we know that $c^{2}$ is \blank. Therefore, we see that \blank \annotate{(Write the ``Want to Show'' fact here to announce that you reached it.)} as required.\qedsymbol 
        \end{boxedminipage}
    \end{center}

    \newpage
    
    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}

    \newpage
    
    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. Since $m$ is \blank, we know that there is an integer $k$ where \blank. Similarly, since $n$ is \blank, there is an integer $r$ where \blank. Then we see that
            \begin{equation*}
                \begin{split}
                    mn &= \blank \\
                       &= \blank \\
                       &= \blank
                \end{split}
            \end{equation*}
            which means that $mn$ is \blank, but this is impossible because \blank.\\
            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 and $b = $ \blank. Then we see that 
            \begin{equation*} \floor{a} \cdot \ceil{b} = 
                  \floor{\blank} \cdot \ceil{\blank} =
                  \blank \cdot \blank = 
                  \blank, \end{equation*} 
            but 
            \begin{equation*} \floor{ab} = \floor{\blank \cdot \blank} = \floor{\blank} = \blank. \end{equation*}
            Thus \blank $\not=$ \blank, as required. \qedsymbol
         \end{boxedminipage}
     \end{center}

     \newpage
            
    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, $b = $ \blank, $c = $ \blank, and $d = $ \blank. Then we see that 
            \begin{equation*} \blank > \blank > \blank > \blank > \blank \end{equation*}
            and
            \begin{equation*} 
            \begin{aligned}
            \blank^2 + \blank^2 + \blank^2 + \blank^2
              &= \blank^2 + \blank^2 + \blank^2 + \blank^2 \\
              &= \blank + \blank + \blank + \blank \\ &= 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. \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.\\
            Now, let $q = $ \blank. \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 \annotate{(Do not write x + qk here)}\\
                      &= \blank \\
                      &= x + qk
                \end{split}
            \end{equation*}
            which is what we needed to show. \qedsymbol 
        \end{boxedminipage}
    \end{center}

    \newpage

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

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

\newpage

\section*{Problem Nine: Proof Critiques}
    i. Fill in the answers to Problem Nine, part i below.
    \begin{shaded}
    \textbf{Proofwriting Checklist:} Write your answers in the blanks below.
    \begin{itemize}
    	\item Clearly Articulate Assumptions and ``Want-to-Shows'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Each Sentence Load-Bearing:  \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Scope and Properly Introduce Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Specific Claims About Specific Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Don't Repeat Definitions; Use Them Instead: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Write In Complete Sentences and Paragraphs: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Avoid the ``Contradiction Sandwich'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
    \end{itemize}
    
    \textbf{Are there any logic errors? If so, where?}: Write your answer here. \\
    
    \textbf{Is the overall theorem true?}: Write your answer here.
    \end{shaded}

    \newpage
    
    ii. Fill in the answers to Problem Nine, part ii below.
    \begin{shaded}
    \textbf{Proofwriting Checklist:} Write your answers in the blanks below.
    \begin{itemize}
    	\item Clearly Articulate Assumptions and ``Want-to-Shows'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Each Sentence Load-Bearing:  \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Scope and Properly Introduce Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Specific Claims About Specific Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Don't Repeat Definitions; Use Them Instead: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Write In Complete Sentences and Paragraphs: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Avoid the ``Contradiction Sandwich'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
    \end{itemize}
    
    \textbf{Are there any logic errors? If so, where?}: Write your answer here. \\
    
    \textbf{Is the overall theorem true?}: Write your answer here.
    \end{shaded}

    \newpage
    
    iii. Fill in the answers to Problem Nine, part iii below.
    \begin{shaded}
    \textbf{Proofwriting Checklist:} Write your answers in the blanks below.
    \begin{itemize}
    	\item Clearly Articulate Assumptions and ``Want-to-Shows'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Each Sentence Load-Bearing:  \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Scope and Properly Introduce Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Make Specific Claims About Specific Variables: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Don't Repeat Definitions; Use Them Instead: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Write In Complete Sentences and Paragraphs: \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
	\item Avoid the ``Contradiction Sandwich'': \blank % Indicate whether or not this rule is violated, and if it is, where the error occurs.
    \end{itemize}
    
    \textbf{Are there any logic errors? If so, where?}: Write your answer here. \\
    
    \textbf{Is the overall theorem true?}: Write your answer here.
    \end{shaded}
    
\newpage

\section*{Problem Ten: Sums of Cubes}

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

    \newpage

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

    \newpage

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

    \newpage

\section*{Problem Eleven: Tag Your Pages}
    You don't need to write anything for this problem. Just make sure to tag
    your pages when submitting!

\newpage

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