% 
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Updated for Summer 2019 by Amy Liu

\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[table]{xcolor}
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{minted}
\usemintedstyle{perldoc}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{}
\date{June 24, 2019}

\lhead{}
\chead{Problem Set 1}
\rhead{June 24, 2019}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Summer 2019}
\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}

% For Polyominoes
% Source: https://tex.stackexchange.com/a/110669
\usepackage{color}

\definecolor{lightgray}{rgb}{0.75, 0.75, 0.75}

\newdimen\omsq  \omsq=16pt
\newdimen\omrule    \omrule=1pt
\newdimen\omint

\newif\ifvth    \newif\ifhth    \newif\ifomblank
\def\OMINO#1{%
    \vthtrue \hthtrue
    \vbox{ \offinterlineskip\parindent=0pt \OM#1\relax\vskip1pt}}
\definecolor{gray}{rgb}{0.5, 0.5, 0.5}

\def\OM#1{%
    \omint=\omsq    \advance\omint-\omrule
    \ifx\relax#1%
    \else
      \ifx\\#1 \newline\null \hthtrue \ifvth\vthfalse\else\vskip-\omrule\vthtrue\fi
      \else%
        \ifx .#1\hskip\ifhth \omrule\else \omint\fi
        \else%
          \ifx +#1\def\colour{black}\fi%
          \ifx -#1\def\colour{black}\fi%
          \ifx |#1\def\colour{black}\fi%
          \ifx @#1\def\colour{black}\fi%
          \ifx r#1\def\colour{red}\fi%
          \ifx g#1\def\colour{green}\fi%
          \ifx b#1\def\colour{blue}\fi%
          \ifx y#1\def\colour{yellow}\fi%
          \ifx m#1\def\colour{magenta}\fi%
          \ifx c#1\def\colour{cyan}\fi%
          \ifx x#1\def\colour{lightgray}\fi%
          \textcolor{\colour}{\rule{\ifhth\omrule\else\omsq\fi}{\ifvth\omrule\else\omsq\fi}}%
          \ifhth\else\hskip -\omrule\fi%
        \fi%
        \ifhth\hthfalse\else\hthtrue\fi%
      \fi%
    \expandafter\OM%
    \fi}

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

\begin{document}

\maketitle

\textbf{Checkpoint Questions Due Monday, July 1st at 3:00PM Pacific time.}

\textbf{Remaining Questions Due Friday, July 5th at 3:00PM Pacific time.} \\

Here we are -- the first problem set of the quarter! This problem set is designed to give you practice writing proofs on a variety of different topics. We hope that this problem set gives you a sense of what proof-based mathematics is like and helps solidify your understanding of set theory. \\

Before you start this problem set, please do the following:
\begin{itemize}
	\item Sign up for Piazza so that you have an easy way to ask us questions.
 	\item Review the office hours timetable to find good times to drop on by to ask questions.
	\item Review Handout ``Proofwriting Checklist,'' for a detailed set of criteria you should apply to your proofs before submitting them. We will be running this same checklist on your proofs when grading, so please be sure to look over it before submitting!
\end{itemize}
The following are additional resources and handouts that can clarify or supplement your understanding of lecture topics:
\begin{itemize}
	\item ``Guide to $\in$ and $\subseteq$'' to make sure you understand the distinction between these terms.
    	\item ``Guide to Set Theory Proofs,'' for more information about how to structure proofs about sets and their properties.
    	\item ``Mathematical Vocabulary,'' which covers mathematical phrases you may need to use in your proofs and how to use them correctly.
    	\item ``Guide to Indirect Proofs,'' which provides some guidance about how to set up proofs by contradiction and contrapositive.
    	\item ``Ten Techniques to Get Unstuck,'' for advice about how to make progress on these sorts of problems when you're not sure what to do.
\end{itemize}
As always, please feel free to drop by office hours or post on Piazza if you have any questions. We're happy to help out. \\

Good luck, and have fun! \pagebreak

Write your solutions to the following checkpoint problems and submit them through GradeScope by Monday at 3:00PM Pacific time. Note in particular that late days may NOT be used on checkpoints. These problems will be graded on a 0 / \checkmark / $\checkmark^+$ scale. Solutions that reasonably attempt to solve all of the problems, even if the attempts are incorrect, will receive a $\checkmark^+$. Solutions that reasonably attempt some but not all of the problems will receive a \checkmark. Solutions that do not reasonably attempt any of the problems -- or solutions that are submitted after the deadline -- will receive a 0. Essentially, if you've made a good, honest effort to solve all of the problems and you submit on time, you should receive full credit even if your solutions contain errors. \\

Please make the best effort you can when solving these problems. We want the feedback we give you to be as useful as possible, so the more time and effort you put into them, the better we'll be able to comment on your proof style and technique. We will try to get these problems returned to you with feedback on your proof style by Wednesday. Submission instructions are in the ``Problem Set Policies'' handout.

\section*{Checkpoint Problem One: Finding Negations}

In order to write a proof by contradiction or contrapositive, you'll need to determine the negation of one or more statements. In Friday's lecture, we talked about a few common classes of statements and how to form their negations. Using what you've learned, answer the following multiple-choice questions and \textit{\textbf{briefly explain how you arrived at your answer}}. \\

Which of the following is the negation of ``everything that has a beginning has an end?''

\begin{enumerate}[label=\Alph*)]
    \item Everything that does not have a beginning has an end.
    \item Everything that has a beginning has no end.
    \item There is something that has no beginning and has an end.
    \item There is something that has a beginning and has no end.
\end{enumerate}

\begin{shaded}
Write your answer here.
\end{shaded}

Which of the following is the negation of ``there is a successful person who is grateful?''

\begin{enumerate}[label=\Alph*)]
    \item There is an unsuccessful person who is grateful.
    \item There is a successful person who is ungrateful.
    \item Every successful person is grateful.
    \item Every successful person is ungrateful.
    \item Every unsuccessful person is grateful.
    \item Every unsuccessful person is ungrateful.
\end{enumerate}

\begin{shaded}
Write your answer here.
\end{shaded}

Which of the following is the negation of ``if $A \subseteq B$, then $A - B = \emptyset$?''

\begin{enumerate}[label=\Alph*)]
    \item If $A \subseteq B$, then $A - B = \emptyset$.
    \item If $A \subseteq B$, then $A - B \neq \emptyset$.
    \item If $A \not\subseteq B$, then $A - B = \emptyset$.
    \item If $A \not\subseteq B$, then $A - B \neq \emptyset$.
    \item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B = \emptyset$.
    \item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B \neq \emptyset$.
    \item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B = \emptyset$.
    \item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B \neq \emptyset$.
\end{enumerate}

\begin{shaded}
Write your answer here.
\end{shaded}

\textit{\textcolor{blue}{Remember that you need to provide a justification for your answers. While it's not required, ideally you should be able to explain both why your answer is correct \textbf{and} why all the other answers are incorrect.}}

\section*{Checkpoint Problem Two: Set Theory Warmup}

This question is designed to help you get used to the notation and mathematical
conventions surrounding sets.
Consider the following sets:
\begin{align*}
A &= \{0, 1, 2, 3, 4\} \\
B &= \{2, 2, 2, 1, 4, 0, 3\} \\
C &= \{1, \{2\}, \{\{3, 4\}\}\} \\
D &= \{1, 3\} \\
E &= \N \\
F &= \{\N\}
\end{align*}
Answer each of the following questions and briefly justify your answers.
No proofs are necessary.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Which pairs of the above sets, if any, are equal to one another?

\begin{shaded}
Write your answer here.
\end{shaded}

\item Is $D \in A$? Is $D \subseteq A$?

\begin{shaded}
Write your answer here.
\end{shaded}

\item What is $A \cap C$? How about $A \cup C$? How about $A \Delta C$?

\begin{shaded}
Write your answer here.
\end{shaded}

\item What is $A - C$? How about $\{A - C\}$? Are those sets equal?

\begin{shaded}
Write your answer here.
\end{shaded}

\item What is $|B|$? What is $|E|$? What is $|F|$?

\begin{shaded}
Write your answer here.
\end{shaded}

\item What is $E - A$? Express your answer in set-builder notation.

\begin{shaded}
Write your answer here.
\end{shaded}

\item Is $0 \in E$? Is $0 \in F$?

\begin{shaded}
Write your answer here.
\end{shaded}

\end{enumerate}

\section*{Checkpoint Problem Three: Modular Arithmetic}

Different numbers can yield the same remainder when divided by some number. For example, the numbers 1, 12, 23, and 34 all leave a remainder of one when divided by eleven. To formalize this relationship between numbers, we'll introduce a relation $\equiv_k$ that, intuitively, indicates that two numbers leave the same remainder when divided by $k$. For example, we'd say that $1 \equiv_{11} 12$, since both 1 and 12 leave a remainder of 1 when divided by 11, and that $8 \equiv_3 14$, since both 8 and 14 leave a remainder of 2 when
divided by 3. 

To be more rigorous, we'll formally define $\equiv_k$. For any integer $k$, define $a \equiv_k b$ as follows:
\begin{center}
    We say that $a \equiv_k b$ if there exists an integer $q$ such that $a = b + kq$
\end{center}

We'd read the statement ``$x \equiv_k y$'' aloud as ``\textit{$x$ is congruent to $y$ modulo $k$}.'' For example, $7 \equiv_3 4$, because $7 = 4 + 3 \cdot 1$, and $5 \equiv_4 13$ because $5 = 13 + 4 \cdot (-2)$. 
In this problem, you will prove several properties of modular congruence.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Prove that for any integer $x$ and any integer $k$ that $x \equiv_k x$.

\textit{\textcolor{blue}{Be careful not to assume what you need to prove. Don't start your proof by assuming there's a choice of $q$ where $x = x + kq$ and then solving for $q$. If you assume there's an integer $q$ where $x = x + kq$, you're already assuming that $x \equiv_k x$! Look at the proofs we did in lecture with odd and even numbers as an example of how to prove that there is a number with a specific property without making any unfounded assumptions.}}

\begin{shaded}
Write your answer here.
\end{shaded}

\item Prove that for any integers $x$ and $y$ and any integer $k$ that if $x \equiv_k y$, then $y \equiv_k x$.

\textit{\textcolor{blue}{Keep an eye out for your variable scoping in the above proof. Make sure you introduce the variables $x$, $y$, and $k$ before you use them. Are they chosen arbitrarily? Do they represent specific values?}}

\begin{shaded}
Write your answer here.
\end{shaded}

\item Prove that for any integers $x$, $y$, and $z$ and any integer $k$ that if $x \equiv_k y$ and $y \equiv_k z$, then $x \equiv_k z$.

\begin{shaded}
Write your answer here.
\end{shaded}

\end{enumerate}

Modular congruence is a powerful mathematical tool. You'll use it later in this problem set to build a better
understanding of star-drawing!

\pagebreak

\begin{center}
\textit{\textbf{The rest of these problems are due on Friday at 3:00PM. \\ Please type your solutions and submit them on GradeScope.}}
\end{center}

\section{Much Ado About Nothing}

It can take a bit of practice to get used to the empty set. This problem will ask you to think about a few different sets related to $\varnothing$. \\

Go to the CS103 website and download the starter files for Problem Set One. Unpack the files somewhere convenient and open up the bundled project. Answer each part of this question by editing the relevant resource files (they're in the \texttt{res/} directory). There's information in the top of each of the files about how to represent sets; most importantly, note that to write out the empty set, you should write \{\} rather than using the empty-set symbol. For example, the set $\{\varnothing\}$ would be written as \{\{\}\}.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
	\item Edit the file \texttt{PartI.object} so that it contains a set equal to $\varnothing \cup \{\varnothing\}$.
    	\item Edit the file  \texttt{PartII.object} so that it contains a set equal to $\varnothing \cap \{\varnothing\}$.
    	\item Edit the file  \texttt{PartIII.object} so that it contains a set equal to $\{\varnothing\} \cup \{\{\varnothing\}\}$.
    	\item Edit the file  \texttt{PartIV.object} so that it contains a set equal to $\{\varnothing\} \cap \{\{\varnothing\}\}$.
    	\item Edit the file  \texttt{PartV.object} so that it contains a set equal to $\wp(\wp(\varnothing))$.
    	\item Edit the file  \texttt{PartVI.object} so that it contains a set equal to $\wp(\wp(\wp(\varnothing)))$.
\end{enumerate}

The starter code contains a driver program you can use to see the contents of your files and confirm they're syntactically correct. Submit your answers through GradeScope under ``Coding Problems for Problem Set One'' by uploading your edited starter files. You're welcome to submit as many times as you'd like.

\begin{shaded}
Submit your six $\mathsf{.object}$ files through GradeScope under ``Coding Problems for Problem Set One'' by uploading your edited starter files. 
\end{shaded}

\section{Set Theory in C++}

The C++ standard library contains a type called \mintinline{c++}{std::set} that represents a set of elements, all of which must be of the same type. For example, the type \mintinline{c++}{std::set<int>} represents a set of integers, the type \mintinline{c++}{std::set<std::string>} represents a set of strings, and \mintinline{c++}{std::set<std::set<int>>} is a type representing a set of sets of integers. \\

There are all sorts of operations you can perform on \mintinline{c++}{std::sets}. For example, here's how you iterate over all the elements of a set:

\begin{minted}{c++}
	std::set<T> mySet;
	for (T elem: mySet) {
	    /* ... do something with the current element elem ... */
	}
\end{minted}

Here's how you check whether a particular value is an element of a set:

\begin{minted}[escapeinside=||,mathescape=true]{c++}
	if (mySet.count(value)) {
	    /* ... value $\in$ mySet ... */
	} else {
	    /* ... value $\notin$ mySet ... */
	}
\end{minted}

And, finally, here's how you can get the cardinality of a set:

\begin{minted}{c++}
	size_t size = mySet.size();
\end{minted}

Here, the \mintinline{c++}{size_t} type is a type representing a natural number, since sets can't have negative size. (The folks who designed the C++ standard libraries had a strong discrete math background.) \\

One of the major differences between the sets we've talked about in CS103 and the \mintinline{c++}{std::set type} is that in discrete mathematics, sets can contain anything -- numbers, philosophies, recipes, other sets, etc. -- but in C++ all objects in a set must have the same type. For the purposes of this problem, we've created a custom C++ type called \mintinline{c++}{Object}. Variables of type \mintinline{c++}{Object} can represent just about anything, so a \mintinline{c++}{std::set<Object>} represents something pretty similar to the sets we've been studying so far. \\

Some \mintinline{c++}{Objects} are actually just \mintinline{c++}{std::sets} in disguise. If you have an \mintinline{c++}{Object}, you can test whether it's actually a set by using this provided helper function:

\begin{minted}{c++}
				     bool isSet(Object o);
\end{minted}

This takes in an \mintinline{c++}{Object}, then returns true if that \mintinline{c++}{Object} is actually a set and false otherwise. If you have an \mintinline{c++}{Object} that really is a set, you can convert it to a set by using this helper function:

\begin{minted}{c++}
				std::set<Object> asSet(Object o);
\end{minted}

This function takes in an \mintinline{c++}{Object} that you know happens to be a set, then returns the \mintinline{c++}{std::set<Object>} that it actually is. \\

For example, suppose you have an \mintinline{c++}{Object} that you know is really the set $\{1, 2, 3, 4\}$. You could iterate over it using this code:

\begin{minted}{c++}
	Object reallyASet = /* ... */;
	for (Object x: asSet(reallyASet)) {
	    /* ... do something with x ... */
	}
\end{minted}

In this problem, we'd like you to demonstrate your understanding of sets and set theory by coding up a number of functions in C++ that operate on sets. In doing so, we hope that you'll solidify your grasp of the distinctions between related concepts in set theory, such as the $\in$ and $\subseteq$ relations and power sets. \\

Open the file \texttt{SetTheory.cpp} from the starter files. There, you'll find a bunch of stubs of functions that you'll need to implement. The provided starter code contains a test harness you can use to try out your functions. You won't need to modify any of the other C++ files bundled with the starter code. \\

As with Problem One, you'll submit the code that you write through GradeScope separately from the rest of the problems on this problem set. The GradeScope autograder will get back to you with feedback about how you're doing on this problem, and you're welcome to submit as many times as you'd like.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Implement a function
\begin{minted}{c++}
       bool isElementOf(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S \in T$. 

\textit{\textcolor{blue}{S and T might not be sets; you'll need to use the isSet and asSet functions appropriately.}}

\item Implement a function
\begin{minted}{c++}
       bool isSubsetOf(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S \subseteq T$.

\textit{\textcolor{blue}{S and T might not be sets; use the isSet predicate to check whether the appropriate arguments are sets and asSet to get a view of them as sets.}}

\item Implement a function
\begin{minted}{c++}
       bool areDisjointSets(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S$ and $T$ are sets where $S \cap T = \varnothing$. (Two sets with this property are called \textbf{\textit{disjoint}}.) The input parameters $S$ and $T$ may or may not be sets, and if they aren't, your function should return false.

\item Implement a function
\begin{minted}{c++}
       bool isSingletonOf(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S = \{T\}$. Again, $S$ and $T$ may or may not be sets.

\item Implement a function
\begin{minted}{c++}
       bool isElementOfPowerSet(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \in \wp(T)$. Again, $S$ and $T$ may or may not be sets.

\textit{\textcolor{blue}{As a hint, you shouldn't need to write code that computes $\wp(T)$ explicitly. See if you can find a different way to do this.}}

\item Implement a function
\begin{minted}{c++}
       bool isSubsetOfPowerSet(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(T)$. Again, $S$ and $T$ may or may not be sets.

\item Implement a function
\begin{minted}{c++}
       bool isSubsetOfDoublePowerSet(Object S, Object T);
\end{minted}
that takes as input two \mintinline{c++}{Objects} $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(\wp(T))$. Again, $S$ and $T$ may or may not be sets.

\end{enumerate}

To submit your work, upload your edited starter files to GradeScope. You'll get immediate feedback on your score from our autograder, and you're allowed to resubmit as many times as you'd like.

\begin{shaded}
Submit your edited $\mathsf{SetTheory.cpp}$ file through GradeScope under ``Coding Problems for Problem Set One''.
\end{shaded}

\section{Describing the World in Set Theory}

The notation of set theory (e.g. $\cup, \cap, \wp, \subseteq, \in$, etc.) is a great tool for describing the real world. Answer
each of the following questions by writing an expression using set theory notation, but \textit{\textbf{without}} using
plain English, \textit{\textbf{without}} using set-builder notation, \textit{\textbf{without}} introducing any new variables, and \textit{\textbf{without}} using propositional or first-order logic (which we'll cover next week).

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Let's have $C$ be the set of US citizens, $S$ the set of people who live in a US state, $M$ be the set of
all people eighteen and older, and $V$ be the set of people who are allowed to vote in US presidential
elections. Write an expression that says that every US citizen age eighteen and older who
lives in a US state can vote in a US presidential election.

\textit{\textcolor{blue}{Once you've written up your answer to this problem, take a minute to \textbf{type-check} it. As an example, suppose
that you have the following answer: 
\begin{equation*}
(C \in M) \cap (V \in M)
\end{equation*}
This expression can't possibly be right, and here's one way to see this. The expression $C \in M$ is of type
boolean -- either $C \in M$ is true or it isn't -- and the same is true of $V \in M$. However, the intersection operator
$\cap$ can only be applied to sets. The expression therefore contains a type error: it tries to apply an operator that only works on sets to boolean values. }}

\begin{shaded}
Write your answer here.
\end{shaded}

\item Suppose you're on an exciting first date. Let $Y$ represent your hobbies and $D$ represent your
date's hobbies. Write an expression that says that you have a hobby that your date doesn't have.

\textit{\textcolor{blue}{You can type-check this answer in a different way. For example, suppose you came up with this expression:
\begin{equation*}
Y \cup D
\end{equation*}
Here, $Y$ and $D$ are sets, so it's perfectly fine to write $Y \cup D$, which evaluates to an object of type set. But
notice that the statement here asks you to write an expression that says ``you have a hobby that your date
doesn't have,'' and that statement is essentially of type boolean (you either do or do not have a hobby your
date doesn't have). Therefore. $Y \cup D$ can't possibly be an expression with the right meaning, since the type
of the expression (set) doesn't match the type of the statement (boolean). }}

\begin{shaded}
Write your answer here.
\end{shaded}

\item The song ``I am Moana'' from the movie \textit{Moana} starts off with the following lyrics: 
\begin{center}
    ``I know a girl from an island / She stands apart from the crowd.''
\end{center}
Let $K$ be the set of all people I know, $G$ be the set of all girls, $I$ be the set of all people from an island, and $C$ be the set of all people who stand apart from the crowd. Write an expression that expresses the above lyric using the notation of set theory. 

\begin{shaded}
Write your answer here.
\end{shaded}

\item Let's say that a \textit{\textbf{committee}} is a group of people, which we can think of as being represented by the set of people that comprise it. Let's have $S$ represent the set of all students at Stanford and let $F$ represent the set of all faculty at Stanford. Write an expression representing the set of all committees you can make from Stanford students and faculty that contain at least one student and at least one faculty member. You can assume no one is both a student and a faculty member.

\textit{\textcolor{blue}{Something to think about: how would you say ``all committees made purely of students?'' }}

\begin{shaded}
Write your answer here.
\end{shaded}

\end{enumerate}

\section{Proof Critiques}

One of the best ways to improve your proof \textit{writing} is to do some proof \textit{reading}. In doing so, you'll get a much better perspective on why certain stylistic conventions matter, both in the positive sense, (``wow, that's so easy to read!'') and in the negative sense (``I can't make heads or tails of this!''). You'll also get practice tracing through mathematical arguments, which will help expand your repertoire of techniques and give you a better sense of what details to focus on in your own reasoning. 

We've curated three proofs for you to review. Read these proofs, and for each one, do the following: 
\begin{itemize}
    \item \textit{\textbf{Critique its style.}} Our Proofwriting Checklist contains specific details to review in any proof. Go through the checklist one item at a time, identifying any style errors and explaining each. 
    \item \textit{\textbf{Critique its reasoning.}} Are the arguments given by these proofs correct? If there are logic errors, point them out and demonstrate why they're incorrect. Then, determine whether the theorem being proved is even true in the first place. After all, you can prove anything using faulty logic!
    \item \textit{\textbf{If possible, rewrite the proof.}} You now have a list of issues. Based on what you've found, do one of the following:
    \begin{itemize}
        \item If the reasoning is correct but the proof has poor style, simply rewrite the proof to improve its style, keeping the core argument intact.
        \item If the reasoning is \textit{incorrect} but the statement being proved is still true, write a new proof of the overall theorem. Try to modify the original argument as little as possible.
        \item If the reasoning is \textit{incorrect} and the statement being proved isn't even true to begin with, briefly explain why the statement isn't true, though no formal disproof is required.
    \end{itemize}
\end{itemize}

You should submit both your notes from the initial critique and your newly-revised proofs.

\pagebreak

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Critique this proof about parities (the \textit{\textbf{parity}} of a number is whether it's even or odd.)
    \begin{thm}
     The sum of an even integer and an odd integer is odd.
    \end{thm}
    \begin{prf}
    This proof will talk about adding together different kinds of numbers. An even integer is an integer that can be written as $2k$ for some integer $k$. Therefore, $m = 2k$. Similarly, an odd integer is one that can be written as $2k+1$ for some integer $k$. So $n = 2k+1$. $m + n = 2k + 2k + 1 = 4k + 1$. Therefore $m + n$ is odd.
    \end{prf}
    
    \begin{shaded}
    Write your critique and newly-revised proof here.
    \end{shaded}

    \item Critique this proof about natural numbers.
    \begin{thm}
    Every natural number is odd.
    \end{thm}
    \begin{prf}
    Assume for the sake of contradiction that every natural number is even. In particular, that would mean that 137 is even. Since $137 = 2 \cdot 68 + 1$ and 68 is a natural number, we see that 137 is odd. We know that there is no integer $n$ where $n$ is both odd and even. However, $n = 137$ is both even and odd. This is impossible. We've reached a contradiction, so our assumption must have been wrong. Therefore, every natural number is odd.
    \end{prf}
    
    \begin{shaded}
    Write your critique and newly-revised proof here.
    \end{shaded}

    \item Critique this proof about modular arithmetic. 
    \begin{thm}
     If $n$ is an integer and $n \equiv_2 0$, then $n \equiv_4 0$.
    \end{thm}
    \begin{prf}
    We will prove the contrapositive of this statement and show that if $n$ is an integer where $n \equiv_4 0$, then $n \equiv_2 0$. Since $n \equiv_4 0$, we know $n = 0 + 4q$. This in turn tells us that $n = 2(2q)$, so there is an integer $m$ such that $n = 2m$. Consequently, we see that $n = 0 + 2m$, and so $n \equiv_2 0$, as required.
    \end{prf}

    \begin{shaded}
    Write your critique and newly-revised proof here.
    \end{shaded}

\end{enumerate}

\section{Modular Arithmetic, Part II}

The modular congruence relation you saw in the checkpoint problem has a lot of nice properties. As you saw, in many ways, it acts like regular old equality. How far does that connection extend?

Below are two statements. For each true statement, write a proof that the statement is true. For each false statement, write a disproof of the statement (take a look at the Proofwriting Checklist for information about how to write a disproof.) You can use any proof techniques you'd like. 

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Prove or disprove: for any integers $x, y, z$, and $k$, if $x \equiv_k y$ then $xz \equiv_k yz$.

\textit{\textcolor{blue}{This is your first example of a ``prove or disprove'' problem. Your first task is to figure out whether it's true or false, since if it's true you'll want to prove it and if it's false you'll want to disprove it.}}

\textit{\textcolor{blue}{Here are two strategies for approaching problems like these. First, try out a lot of examples! You'll want to get a feel for what the symbolic expression above ``feels'' like in practice. Second, get a sheet of scratch paper and write out both the statement and its negation. One of those statements is true, and your task is to figure out which one it is. Once you have those two statements, think about what you would need to do to prove each of them. In each case, what would you be assuming? What would you need to prove? If you can answer those questions, you can explore both options and seeing which one ends up panning out.}}

\textit{\textcolor{blue}{Finally, remember to call back to definitions! Regardless of whether you're proving or disproving this, you'll want to refer to the formal definition of modular congruence from the checkpoint problem.}}

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\item Prove or disprove: for any integers $x, y, z$ and $k$, if $z \neq 0$ and $xz \equiv_k yz$, then $x \equiv_k y$.


\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\end{enumerate}

\section{Properties of Sets}

For each of these statements about sets, decide whether that statement is true or false. Prove each true statement, and disprove each false statement. \\

We \emph{strongly} recommend reading the Guide to Set Theory Proofs before starting this problem.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Prove or disprove: for all sets $A$, $B$, and $C$,
if $A \in B$ and $B \in C$, then $A \in C$.

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\item Prove or disprove: if $A$, $B$, and $C$ are sets where $A - C = B - C$, then $A = B$.

\textit{\textcolor{blue}{A question you should be able to answer before starting this problem: how do you prove that two sets are equal to one another? Based on that, how do you prove that two sets are not equal to one another? Check the Guide to Proofs on Sets for details.}}

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\item Prove or disprove: if $A$ and $B$ are sets where $\wp(A) = \wp(B)$, then $A = B$.

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\item Prove or disprove: if $A$, $B$, and $C$ are sets where $A \Delta C = B \Delta C$, then $A = B$.

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\end{enumerate}

\textit{\textcolor{blue}{ Before you turn in these proofs, read over the Proofwriting Checklist and the Guide to Proofs on Sets and
confirm that your proof meets our style criteria. Here are a few specific things to look for:
\begin{itemize}
\item Make sure that the structures of your proofs match the definitions of the relevant terms. To prove $S \subseteq T$, pick an arbitrary $x \in S$, then prove $x \in T$ by making claims about $x$. To prove $S = T$, prove $S \subseteq T$ and $T \subseteq S$.
\item However, avoid restating definitions in the abstract. For example, rather than writing
\begin{center}
``We know that $S \subseteq T$ if every element of $S$ is an element of $T$. \\
Therefore, since we know that $A \subseteq B$ and $x \in A$, we see that $x \in B$.''
\end{center}
instead remove that first sentence and just write something like this:
\begin{center}
``Since $x \in A$ and $A \subseteq B$, we see that $x \in B$.''
\end{center}
Whoever is reading your proof knows all the relevant definitions. They're more interested in seeing
\textbf{how those definitions interact with one another} than \textbf{what those definitions are}.
\item Make sure you clearly indicate what each variable means and whether it's chosen arbitrarily or
chosen to have a specific value. For example, if you refer to variables like A, B,
or C, you should clearly indicate whether they're chosen arbitrarily or refer to specific values.
\item When talking about an arbitrary set A, it's tempting to list off the elements of A by
writing something like $A = \{ x_1, x_2, \ldots, x_n \}$. The problem is that writing
$A = \{ x_1, x_2, \ldots, x_n \}$ implicitly says that the set $A$ is finite, since you're saying it only
has $n$ elements in it. This is a problem if $A$ is infinite. In fact, if $A$ is infinite, because of
Cantor's theorem, you can't necessarily even write $A = \{ x_1, x_2, x_3, \ldots \}$, since you might run out of
natural numbers with which to name the elements of $A$!
\end{itemize}
}}

\section{Tiling with Polyominoes}

The game \textit{Tetris} involves working with seven shapes of tiles, each of which is made from exactly four squares. The pieces are shown here:

\begin{figure}[H]
\OMINO{
+-+\\
|x|\\
|-|.+---+.+-+...+-+...\\
|x|.|x|x|.|x|...|x|...\\
|-|.|-+-+.|-+-+.|-|.....+---+.+---+...+---+\\
|x|.|x|...|x|x|.|x|.....|x|x|.|x|x|...|x|x|\\
|-|.|-|...|-+-+.|-+-+.+-+-|-+.+-+-+-+.|---|\\
|x|.|x|...|x|...|x|x|.|x|x|.....|x|x|.|x|x|\\
+-+.+-+...+-+...+---+.+---+.....+---+.+---+\\
}
\end{figure}

We can use the Tetris pieces to \emph{tile} various geometric figures. In the context of recreational mathematics (yes, that's a thing!), ``tiling'' refers to covering up some underlying figure using tiles drawn from some collection of shapes. You're allowed to rotate and flip the tiles however you'd like, and you can assume you have as many copies of each tile as you need. You don't even need to use all the tiles. However, the tiles must cover the entire underlying figure, the tiles can't hang off of the original figure, and the tiles aren't allowed to overlap. For example, here's how we'd tile a $3 \times 4$ chessboard, a $4 \times 6$ chessboard, and a $5 \times 8$ chessboard with Tetris pieces:

\begin{figure}[H]
\OMINO{
........................+-+-----+-----+-+\\
........................|x|xxxxx|xxxxx|x|\\
..........+---+-------+.|x+---+x+-+x+-+x|\\
..........|xxx|xxxxxxx|.|x|xxx|x|x|x|xxx|\\
+---+---+.|x+-+-+-----+.|x+-+x+-+x+-+-+x|\\
|xxx|xxx|.|x|xxx|xxxxx|.|xxx|xxx|xxx|x|x|\\
|x+-+-+x+.|x+-+x+-+x+-+.+---+-----+x|x+-+\\
|x|xxx|x|.|x|x|xxx|x|x|.|xxx|xxxxx|x|xxx|\\
|x|xxx|x|.+-+x+---+-+x+.|xxx|x+---+-+-+x|\\
|x|xxx|x|.|xxxxx|xxxxx|.|xxx|x|xxxxxxx|x|\\
+-+---+-+.+-----+-----+.+---+-+-------+-+
}
\end{figure}

Mathematicians and computer scientists have spent a lot of time thinking about what sorts of tilings are possible, and what sorts of tilings are impossible. For example, in the \href{http://web.stanford.edu/class/cs103//handouts/Mathematical\%20Foundations\%20of\%20Computing.pdf#page=60}{course notes} (pages 60 - 61), there's a proof that it's impossible to tile an $8 \times 8$ chessboard missing two opposite corners using $2 \times 1$ tiles.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Prove or disprove: it's possible to tile a $9 \times 10$ chessboard with Tetris pieces.

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\end{enumerate}

Up to this point, we've assumed you have as many copies of each Tetris piece as you'd like. There's a more restricted kind of tiling called a perfect tiling in which you get exactly one copy of each tile, and you're required to form a tiling using exactly one copy of each tile. None of the above tilings are perfect.

\begin{enumerate}[resume*]

\item Prove or disprove: it's possible to perfectly tile a $4 \times 7$ chessboard with the seven Tetris pieces.

\begin{shaded}
Provide a proof or disproof here.
\end{shaded}

\end{enumerate}

\section{Yablo's Paradox}

A \emph{logical paradox} is a statement that results in a contradiction
regardless of whether it's true or false.
One of the simplest paradoxes is the \emph{Liar's paradox},
which is the following:
\begin{center}
\emph{This statement is false.}
\end{center}
If this statement is true,
then by its own admission, it must be false -- a contradiction!
On the other hand, if the above statement is false, then the statement ``This statement is false'' is false, and therefore the
statement ``This statement is false'' is true -- a contradiction!
Since this statement results in a contradiction regardless of whether
it's true or false, it's a paradox. \\

Paradoxes often arise as a result of self-reference.
In the Liar's Paradox,
the paradox arises because the statement itself directly refers to itself.
However, it's not the only paradox that can arise from self-reference.
This problem explores a paradox called \emph{Yablo's paradox}. \\

Consider the following collection of infinitely many statements numbered
$S_0, S_1, S_2,\dots,$ where there is a statement $S_n$ for each
natural number $n$.
These statements are ordered in a list as follows:

\begin{mdframed}[backgroundcolor=yellow!20] 
\begin{center}
$(S_0)$: All statements in this list after this one are false. \\
$(S_1)$: All statements in this list after this one are false. \\
$(S_2)$: All statements in this list after this one are false. \\
$\cdots$
\end{center}
\end{mdframed}

More generally, for each $n \in \N$, the statement $(S_n)$ is
\begin{center}
$(S_n)$: All statements in this list after this one are false.
\end{center}
Surprisingly,
the interplay between these statements makes every statement in the list
a paradox.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

\item Prove that if any statement in this list is true, it results in a contradiction.

\end{enumerate}

\textit{\textcolor{blue}{Your result needs to work for any choice of statement in the list, not just one of them. Follow the template for proving a universally-quantified statement}}

\begin{shaded}
Provide a proof here.
\end{shaded}

\begin{enumerate}[resume*]

\item Prove that every statement in this list is a paradox. 

\end{enumerate}

\textit{\textcolor{blue}{Something to ponder: how do you negate a universally-quantified statement?}} \\

\begin{shaded}
Provide a proof here.
\end{shaded}

Now, consider the following modification to this list.
Instead of infinitely many statements,
suppose that there are ``only'' $10,000,000,000$ statements.
Specifically, suppose we have these statements:
\begin{mdframed}[backgroundcolor=yellow!20] 
\begin{center}
$(T_0)$: All statements in this list after this one are false. \\
$(T_1)$: All statements in this list after this one are false. \\
$(T_2)$: All statements in this list after this one are false. \\
$\cdots$ \\
$(T_{9,999,999,999})$: All statements in this list after this one are false.
\end{center}
\end{mdframed}
There's still a lot of statements here,
but not infinitely many of them.
Interestingly,
these statements are all perfectly consistent with one another and do not
result in any paradoxes.

\begin{enumerate}[resume*]

\item For each statement in the above list,
determine whether it's true or false and explain why
your choices are consistent with one another.

\begin{shaded}
Write your answer here.
\end{shaded}

\end{enumerate}

Going forward, don't worry about paradoxical statements in CS103.
We won't talk about any more statements like these.
\smiley

\section{The Star-Drawing Saga, Part II}

On Problem Set 0, you got to play around with star drawing and discovered that certain combinations of a number of points p and a step size s led to simple stars (for example, the \{7 / 2\} and \{8 / 3\} stars), while other combinations did not (for example, the \{8 / 2\} or \{12 / 3\} stars). Why exactly is this? Over the course of the next several problem sets, you'll discover exactly why! \\

The main insight that we'll use in analyzing stars is to recognize a connection between star-drawing, which you saw on Problem Set Zero, and modular congruence, which you explored in this problem set. Imagine that you set out to draw a $p$-pointed star by drawing $p$ points around a circle. Let's number those points $0, 1, 2, \dots, p - 1$, going clockwise around the circle. (Of course we're using zero-indexing - we're computer scientists!) We'll then draw the star by starting at position 0, then drawing a line to the point $s$ positions clockwise from us, then drawing a line from there to the point $s$ positions clockwise from that, etc. until we end back up at position 0. 

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Let's suppose we're following the above procedure and stop after drawing $t$ total lines and end up on point $n$ on the star. Explain, intuitively, why $n \equiv_p s \cdot t$.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
\end{enumerate}

\annotate{Mathematicians conventionally use single-letter variable names for everything, which can lead to really dense formulas. Computer scientists love to use longer variable names to improve readability. If you're having trouble interpreting that above formula, consider writing a ``cheat sheet'' that lists each variable along with a more verbose description of what it represents.} \\
\pagebreak

If we pick a number of points $p$ and a step size $s$, we end up with a simple star if we end up passing through each of the $p$ points before ending back at our starting point. The modular equation you just saw in part (i) of this problem tells us where on the star we'll be at each point in time. Putting these two ideas together gives us this fundamental fact about stars:
\begin{center}
    \emph{Simple Star Criterion}: A $p$-point star with a step size of $s$ is a simple star if and only if for every natural number $n$, there is a natural number $t$ such that $n \equiv_p s \cdot t$.
\end{center}
This statement is slightly dense, and like all mathematically dense statements, one of the best ways to get a handle on what it says is to try it out in some specific cases.

\begin{enumerate}[resume*]
    \item Consider a star polygon with five points and a step size of two (the \{5 / 2\} star, or the standard 5-pointed star). This is an example of a simple star -- you are able to hit all 5 points before ending up back at your starting point. \\
    
    Now consider the \{7 / 2\} star, \{9 / 2\} star, and \{11 / 2\} star. Show that these stars also meet the simple star criterion by filling in the table below, listing off values of $t$ such that $n \equiv_p s \cdot t$. We have filled in the first row for the \{5 / 2\} star for you.

\begin{shaded}
\begin{center}
\begin{tabular}{rlllllllllll}
\emph{n} & \emph{0} & \emph{1} & \emph{2} & \emph{3} & \emph{4} & \emph{5} & \emph{6} & \emph{7} & \emph{8} & \emph{9} & \emph{10} \\ \cline{2-12} 
\multicolumn{1}{l|}{\emph{Value of $t$ where $n \equiv_5 2 \cdot t$}} & \multicolumn{1}{l|}{0} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{4} & \multicolumn{1}{l|}{2} & \multicolumn{6}{l|}{\cellcolor{gray}{}} \\ \cline{2-12} 
\multicolumn{1}{l|}{\emph{Value of $t$ where $n \equiv_7 2 \cdot t$}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{4}{l|}{\cellcolor{gray}{}} \\ \cline{2-12} 
\multicolumn{1}{l|}{\emph{Value of $t$ where $n \equiv_9 2 \cdot t$}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{2}{l|}{\cellcolor{gray}{}} \\ \cline{2-12} 
\multicolumn{1}{l|}{\emph{Value of $t$ where $n \equiv_{11} 2 \cdot t$}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \cline{2-12} 
\end{tabular}
\end{center}
\end{shaded}

\end{enumerate}

\annotate{It's somewhat tricky to fill this table in purely by eyeballing the mathematical formula and trying to guess numbers. Instead, think back to the intuition behind this formula. You might want to try drawing the star and seeing whether that gives you any new insights.} \\

One observation you may have made between Problem Set 0 and filling out the table above is that if you have an odd number of points, you can always form a simple star by taking steps of size two.

\begin{enumerate}[resume*]
    \item Using the simple star criterion, prove that \{$p$ / 2\} is a simple star for any odd natural number $p$.
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

\annotate{This result is a generalization of what you did in part (ii) of this problem, since that question asked you to work out the math for $p = 7, 9, 11$ and this question asks for a more general argument. You might want to try solving this problem by looking at the table you've generated and seeing if you spot a pattern. Feel free to try other concrete values of $p$ as well. Once you have the pattern, formalize your reasoning by writing it up as a proof.}

\pagebreak

\annotate{On each problem set, we'll provide some optional fun problems for extra credit. These are problems that can be solved purely using the techniques you've learned so far, but which will require some thought. Each problem, in our opinion, has a beautiful solution that will give you a much deeper understanding of core concepts, so we strongly encourage you to play around with them if you get the chance. Please feel free to work on as many of these problem as you'd like, though please only submit a solution to at most one of the optional fun problems on each problem set.} \\

\annotate{When we compute final grades at the end of the quarter, we compute the grading curve without any extra credit factored in, then recompute grades a second time to factor in extra credit. This way, you're not at any disadvantage if you decide not to work through these problems. If you do complete the extra credit problems, you may get a slight boost to your overall grade.} \\

\annotate{As a matter of course policy, we don't provide any hints on the extra credit problems -- after all, they're supposed to be challenge problems! However, we're happy to chat about them after the problem sets come due.}

\section*{Optional Fun Problem One : Hat Colors}

You and nine of your friends are brought into a room together. The CS103 TAs go around and place a hat on everyone's head. There are ten different colors of hats -- red, orange, yellow, green, blue, magenta, black, white, gray, and gold. It's possible that everyone gets a hat of a different color. It's possible that everyone gets a hat of the same color. In fact, aside from the restriction that each hat is one of the ten colors mentioned earlier, there are no restrictions about how many hats there are of each color. \\

You and your friends can all look around to see what color hats everyone else is wearing, but no one can see their own hat color. The staff will then go around and ask everyone to write down a guess of what color their hat is. We'll then collect those guesses and reveal them all at once. You and your friends succeed if at least one of you is able to correctly guess their own hat color. You and your friends all lose if no one correctly guesses their own hat color. \\

Before we place hats on everyone, we'll allow you and your friends to work out a strategy about how you're going to guess, but once the hats are on no communication of any kind - whether explicit or implicit - is permitted between the group. Devise a strategy that \textit{guarantees} at least one person will correctly guess their own hat color, even if we know what strategy you'll be using. Then, using the mathematical notation and tools you've learned so far in this course, formally prove that your strategy works. For example, here are a few strategies you could choose from that \textit{don't} work: 
\begin{itemize}
    \item Everyone could pick which color they're going to guess before going into the room, and then write down that guess regardless of what color hats they see on everyone else. If we assign hats randomly, then the probability that this works is approximately $1 - e^{-1}$ (take CS109 if you're curious why this is!) However, if we overhear your discussion, we could be mean and deliberately give everyone the wrong hat color, making your probability of success exactly 0.
    
    \item Everyone could arrange themselves in a circle, then guess the color of the hat of the person immediately to their left. If we choose hat colors randomly, then there's a decent probability that someone will correctly guess their own hat color. But if we know that this is what you're going to do, we can just give everyone a different hat color and you're guaranteed to lose
    
\end{itemize}

\annotate{I first heard this problem from Michelle McGhee, CS major (theory track), storyteller, and Ultimate Frisbee player, when she was helping staff Girl Code @Stanford in 2018. Her senior project was a program that generated freestyle rap lyrics.}

\begin{shaded}
Provide a description of your strategy and a proof that it works here.
\end{shaded}

\section*{Optional Fun Problem Two: Infinite Deviation}

In our first class meeting, we sketched out a proof of Cantor's theorem. If you'll recall, this proof worked by assuming there was a pairing between the elements of a set $S$ and the subsets of that set $S$, then constructing a set that was different in at least one position from each of the paired sets. \\

Suppose you try to pair off the elements of $\mathbb{N}$ with the subsets of $\mathbb{N}$. Show that, no matter how you do this, there's always at least one set $X \subseteq \mathbb{N}$ that differs in infinitely many positions from each of the paired sets. Justify your answer, but no formal proof is necessary.

\begin{shaded}
Write your answer here.
\end{shaded}

\end{document}