% 
% 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.
%

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

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{Sachin Padmanabhan}
\date{\today}

\lhead{Sachin Padmanabhan}
\chead{Problem Set \#1}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 2017}
\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}}

\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

\section{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 &= \{1, 2, 3, 4\} \\
B &= \{2, 2, 2, 1, 4, 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}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}

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

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

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

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

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

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

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

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

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

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

\end{enumerate}

\section{The Power Set Revisited}

In our first lecture, we saw an operation called the power set that, given a set $S$, produces a set $\wp(S)$ consisting of all the subsets of the set $S$. Why didn't we introduce an operation that, given a set $S$, produces a set consisting of all the elements of $S$?

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

\section{Set Theory in C++}

\begin{shaded}
Submit your edited $\mathsf{SetTheory.cpp}$ file through GradeScope.
\end{shaded}

\section{Much Ado About Nothing}

\begin{shaded}
Submit your six $\mathsf{.object}$ files through GradeScope.
\end{shaded}

\section{Properties of Sets}

Here are some claims about properties of sets. Some of them are true and some of them are false. For each true statement, write a proof that the statement is true. For each false statement, write a disproof of the statement. You can use any proof techniques you'd like.
\\If you want to disprove a statement, you can structure your disproof like this:
\vspace{-2em}
\begin{quote}
\begin{claim}
[\textit{statement to disprove goes here}]
\end{claim}
\begin{proof}[Disproof]
We will show that the negation of this statement, namely, $\left[ \textit{fill this in} \right]$, is true. [\textit{Then go prove the negation of the statement}].
\end{proof}
\end{quote}
In particular, notice that you shouldn't call the statement you're disproving a theorem, since the term "theorem" specifically refers to a statement that you'll prove is true. Similarly, you shouldn't call the justification you're writing up a proof, since the term "proof" in mathematics means an argument that shows something is true, and that's precisely the opposite of what you'll be doing. Aside from these terminology differences, proofs and disproofs follow the same general structure: you'll give a line of reasoning establishing why some result happens to be true. The only difference is that in a disproof, you're proving that the negation of some statement is true.

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

\item 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 For all sets $A$ and $B$,
if $\wp(A) = \wp(B)$, then $A = B$.

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

\item For all sets $A$, $B$, and $C$, if $A \subseteq B$ and $A \subseteq C$, then $A \subseteq B \cap C$.

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

\item For all sets $A$, $B$, and $C$, if $A \subsetneq B$ and $A \subsetneq C$, then $A \subsetneq B \cap C$. (The notation $A \subsetneq B$ says that $A$ is a \textit{\textbf{strict subset}} of $B$, meaning that $A \subseteq B$ and $A \neq B$.)

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

\item There exists a set $A$ where $\wp(A) = \{A\}$.

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

\end{enumerate}

Some general notes on these above proofs:
\begin{itemize}
\item Make sure to call back to definitions. For example, if you're trying to prove that a set $S$ is a subset of a set $T$, follow the pattern from lecture: pick an arbitrary $x \in S$, then prove that $x \in T$.
\item Be careful with your variables. Make sure you clearly indicate what each variable means and whether it's chosen arbitrarily or chosen to have a specific value.
\end{itemize}


\section{Two Is Irrational?}

In lecture,
we proved that $\sqrt{2}$ is irrational,
and in the checkpoint problem you proved that $\sqrt{3}$
is irrational.
Below is a purported proof that $\sqrt{4}$ is irrational:
\vspace{-2em}
\begin{quote}
\begin{thm}
$\sqrt{4}$ is irrational.
\end{thm}
\begin{proof}
Assume for the sake of contradiction that $\sqrt{4}$ is rational.
Then there must exist integers $p$ and $q$ where $q \neq 0$,
where $p/q = \sqrt{4}$,
and where $p$ and $q$ have no common factors other than $1$ and $-1$. \\

Starting with $p/q = \sqrt{4}$ and squaring both sides tells us that
$p^2 / q^2 = 4$.
We can then cross-multiply by $q^2$ to see that $p^2 = 4q^2$.
Since $q^2$ is an integer and $p^2 = 4q^2$,
we see that $p^2$ is a multiple of four,
and therefore that $p$ is a multiple of four.
This tells us that $p = 4n$ for some integer $n$. \\

Since $4q^2 = p^2$ and $p = 4n$,
we can use some algebraic substitutions to show that
$4q^2 = (4n)^2 = 16n^2$,
so $q^2 = 4n^2$.
Since $n^2$ is an integer and $q^2 = 4n^2$,
we see that $q^2$ is a multiple of four,
so $q$ is a multiple of four as well.
But since both $p$ and $q$ are multiples o four,
we see that $p$ and $q$ share a common divisor other than $\pm 1$,
contradicting our initial assumption.
We have reached a contradiction,
so our assumption must have been incorrect.
Thus $\sqrt{4}$ is irrational.
\end{proof}
\end{quote}
This proof has to be wrong,
because $\sqrt{4} = 2 = 2/1$,
so it is indeed rational! \\

What error does this proof make that lets it conclude $\sqrt{4}$
is irrational?
Be specific.

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

\section{Piano Tuning}
At a first glance, irrational numbers can seem like a purely mathematical idea without any practical applications. It turns out, though, that irrational numbers have real-world implications.
\\Prove that $\sqrt[12]{2}$, the twelfth root of two, is irrational. Interestingly, this result means that it's impossible to tune a piano such that every half step, perfect fifth, perfect fourth, and octave are all properly in tune. If you're curious about why this is, there's a great Minute Physics video about the different ratios that arise in music and how this relates to them. It's online at $\href{https://youtu.be/1Hqm0dYKUx4}{https://youtu.be/1Hqm0dYKUx4}$.
\\As a hint, do \emph{not} attempt to prove this result by starting with the proof that $\sqrt{2}$ is irrational and making appropriate modifications - that will get really messy really fast. Instead, see if you can prove the following intermediary result, and build your proof around it:
\begin{center}
	If $\sqrt[12]{2}$ is rational, then $\sqrt{2}$ is rational.
\end{center}
You may want to check the Mathematical Prerequisites handout for a refresher on higher-order roots.

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

\section{Modular Arithmetic}

Different numbers can yield the same remainder when divided by some number.
For example,
the numbers $2$, $5$, $8$, $11$, and $14$ all leave a remainder of two
when divided by three,
while 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$ and that $8\equiv_3 11$. \\

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}
For example, $7 \equiv_3 4$ because $7 - 4 = 3 = 3 \cdot 1$,
and $13 \equiv_4 5$ because $13 - 5 = 8 = 4 \cdot 2$.
If $x \equiv_k y$,
we say that $x$ \emph{is coongruent to $y$ modulo $k$},
hence the terminology in the checkpoint problem.
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$.

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

\end{enumerate}

As you're working through the above proof, be careful not to assume what you need to prove. Don't start your proof off by assuming that there's a choice of $q$ where $x - x = kq$ and then solving for $q$. After all, if you assume there's an integer $q$ where $x - x = kq$, you're already assuming that $x \equiv_k x$! Instead, proceed along the lines of what we did in lecture when proving that if $n$ is even, then $n^2$ is even: manipulate the expression $x - x$ and see if you can find a way to express it as something of the form $kq$.

\begin{enumerate}[resume*]

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

\begin{shaded}
Provide a proof 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}
Provide a proof here.
\end{shaded}

\end{enumerate}

The three properties you have just proven show that modular congruence is
an \emph{equivalence relation}. Equivalence relations are important throughout mathematics, and we'll see more examples of them later in the quarter.

\section{Tiling a Chessboard}

Suppose you have a standard $8 \times 8$ chessboard with two opposite
corners removed, as shown here.

\begin{figure}[h!]
\centering
\begin{tikzpicture}[x=0.5cm,y=0.5cm]
    \foreach \x in {0,...,7} \foreach \y in {0,...,7}
    {
        \pgfmathparse{mod(\x+\y+1,2) ? "black" : "white"}
        \edef\colour{\pgfmathresult}
        \path[fill=\colour] (\x,\y) rectangle ++ (1,1);
    }
    \draw (0,0)--(7,0);
    \draw (8,1)--(8,8)--(1,8);
    \draw (0,7)--(0,0);
\end{tikzpicture}
\end{figure}

In the course notes (pages 60 -- 61),
there's a proof that it's impossible to tile this chessboard using
$2 \times 1$ dominoes.
This question considers what happens if you try to tile the chessboard
using \emph{right triominoes}, L-shaped tiles that look like this:

\begin{figure}[h!]
\centering
\begin{tikzpicture}[x=0.5cm,y=0.5cm]
\draw[fill=lightgray] (0,0) rectangle ++ (1,1);
\draw[fill=lightgray] (1,0) rectangle ++ (1,1);
\draw[fill=lightgray] (0,1) rectangle ++ (1,1);
\end{tikzpicture}
\end{figure}

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

\item Prove that it is impossible to tile an $8 \times 8$ chessboard missing
two opposite corners with right triominoes.

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

\item For $n \geq 3$,
is it \emph{ever} possible to tile an $n \times n$ chessboard missing
two opposite corners with right triominoes?
If so, find a number $n \geq 3$ such that it's possible and show how to tile
an $n \times n$ chessboard missing two opposite corners with right triominoes.
If not, prove that for every $n \geq 3$,
it's impossible to tile an $n \times n$ chessboard missing two opposite corners
with right triominoes.

\begin{shaded}
\begin{claim}
State your claim here.
\end{claim}
Provide a proof 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}
\textbf{\textit{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 statement is false, then it must be true --
a contradiction!
Since this statement results in a contradiction regardless of whether
it's true or false, its a paradox. \\

Paradoxes often arise as a result of \emph{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 \textbf{\textit{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{center}
\begin{framed}
$(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{framed}
\end{center}
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 every statement in this list is a paradox.
Some hints on this problem:
\begin{itemize}
\item We've asked you to prove a universal statement
(every element in this list is a paradox).
What is the general template for proving a universal statement?
\item Split your proof into two parts.
First, show that you get a contradiction
if any of the
statements in the list are true.
Then, show that you get a contradiction if any of the statements
in the list are false.
\item You should assume, as we've been doing in class,
that every statement is either true or false.
You don't need to worry about statements that are neither true nor false.
\end{itemize}

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

\end{enumerate}

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{center}
\begin{framed}
$(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{framed}
\end{center}
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}
\begin{answer}
Write your answer here.
\end{answer}
\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*{Extra Credit Problem: The Mouse and the Cheese
\footnote{Adapted from Problem 4E of \emph{A Course in Combinatorics,
Second Edition} by van Lint and Wilson.}}

On each problem set,
we'll provide an optional fun problem for extra credit.
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.
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. \\

Suppose that you have a $3" \times 3" \times 3"$ cube of cheese
subdivided into twenty-seven $1" \times 1" \times 1"$
smaller cubes of cheese.
A mouse wants to eat the entire cube of cheese and does so as follows:
she first picks any small cube to eat first,
then moves to an adjacent small cube of cheese
(i.e. a cube that
shares a face with the cube that was just eaten)
to eat next,
then repeats this process. \\

Prove that the mouse can't eat the centermost cube of cheese last.

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

\end{document}
