% 
% 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{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\usepackage{mathrsfs}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#4}
\author{Your Name(s) Here}
\date{\today}

\lhead{Your Name(s) Here}
\chead{Problem Set \#4}
\rhead{\today}
\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{\Q}{\mathbb{Q}}
\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.9}

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

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{minted}
\usepackage{mathtools}
\usepackage{alltt}
% end MZ

\begin{document}

\maketitle

\textbf{No checkpoint this week (or any subsequent week!)}

\textbf{All questions due Friday, July 26th at 3:00PM.} \\

This problem set - the last one purely on discrete mathematics - is designed as a cumulative review of the topics we've covered so far and a proving ground to try out your newfound skills with mathematical induction. The problems here span all sorts of topics - graph theory, tiling problems, games, and parallel computing - and we hope that it serves as a fitting coda to our whirlwind tour of discrete math! \\

Before beginning this problem set, we \emph{strongly} recommend reading over the following handouts:
\begin{itemize}
\item The ``Guide to Induction,'' contains a lot of useful advice about how to approach problems inductively, how to structure inductive proofs, and how to not fall into common inductive traps.
\item The ``Induction Proofwriting Checklist,'' which contains a list of specific things to watch for in your solutions before submitting.
\end{itemize}
As a note on this problem set - normally, you're welcome to use any proof technique you'd like to prove results in this course. On this problem set, we've specifically requested on some problems that you prove a result inductively. For those problems, you should prove those results using induction or complete induction, even if there is another way to prove the result. (If you'd like to use induction in conjunction with other techniques like proof by contradiction or proof by contrapositive, that's perfectly fine.) \\

Good luck, and have fun! 
\pagebreak

\section{Recurrence Relations}
A \emph{recurrence relation} is a recursive definition of the terms in a sequence. Typically, a recurrence relation specifies the value of the first few terms in a sequence, then defines the remaining terms from the previous terms. For example, the \emph{Fibonacci sequence} can be defined by the following recurrence relation:

\begin{align*}
F_0 &= 0 \\
F_1 &= 1 \\
F_{n+2} &= F_n + F_{n+1}
\end{align*}

The first terms of this sequence are $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8,$ etc. \\

Some recurrence relations define well-known sequences. For example, consider the following recurrence relation:

\begin{align*}
a_0 &= 1 \\
a_{n+1} &= 2a_n
\end{align*}

The first few terms of this sequence are $1, 2, 4, 8, 16, 32, \ldots,$ which happen to be powers of two. It turns out that this isn't a coincidence -- this recurrence relation perfectly describes the powers of two.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Prove by induction that for any $n \in \N$, we have $a_n = 2^n$. 
    
    \annotate{In case you're wondering what you're asked to prove here, you can think of this recurrence relation as a mathematical way of writing out this recursive function:}
    \begin{alltt}\textcolor{blue}{
    int a(int n) \{
        if (n == 0) return 1; 
        return 2 * a(n - 1);
    \}}
    \end{alltt}
    \annotate{For any natural number $n$, you can compute $a(n)$ by just running this code, and after doing some computation it will return the value of $a_n$. What we're asking you to do is the mathematical equivalent of showing that the value returned by $a(n)$ is always $2^n$. While it might help to think about things in terms of this analogy, your proof should not reference this code and should just use the definitions given in the problem statement.}

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

Minor changes to the recursive step in a recurrence relation can lead to enormous changes in what numbers are generated. Consider the following two recurrence relations, which are similar to the $a_n$ sequence defined above but with slight changes to the recursive step:
\begin{equation*}
  \begin{split}
    b_0 &= 1\\
    b_{n+1} &= 2b_n - 1
  \end{split}
  \quad\quad\quad\quad
  \begin{split}
    c_0 &= 1 \\
    c_{n+1} &= 2c_n + 1
  \end{split}
\end{equation*}

\begin{enumerate}[resume*]
    \item Find non-recursive definitions for $b_n$ and $c_n$, then prove by induction that your definitions are correct.
    
    \textit{\textcolor{blue}{ This one is hard to do just by eyeballing the recurrences. Try expanding out the first few terms of these sequences and see what you find. }}
    
    \begin{shaded}
    Write your answer and proof here.
    \end{shaded}
\end{enumerate}

Finding non-recursive definitions for recurrences (often called ``solving'' the recurrence) is useful in the design and analysis of algorithms. Commonly, when trying to analyze the runtime of a recursive algorithm, you will arrive at a recurrence relation describing the runtime on an input of size $n$ in terms of the runtime on inputs of smaller sizes. Solving the recurrence then lets you precisely determine the runtime. To learn more, take CS161, Math 108, or consider reading through the excellent textbook \textit{Concrete Mathematics} by Graham, Knuth, and Patashnik.

\section{Symmetries, Permutations, and Automorphisms}

One of the more beautiful concepts in mathematics is \textit{symmetry}. Chances are that you have some intuitive conception of what ``symmetry'' means, and not just in the binary relation sense. For example, the letter M looks like itself when you look at it in a mirror, and the number 8 looks like itself if you flip it horizontally or rotate it $180^\circ$. \\

Now that we're studying graphs, we can ask what it means for a graph to be symmetric. For example, consider the graph of the \{5 / 2\} star shown below. This graph has many symmetries -- if you flip it horizontally, or rotate it $72^\circ$, the resulting graph looks identical. But this notion of ``looks identical'' appeals to our human visual system, which, as you've probably experienced, is easily tricked. Is there a way to come up with a more rigorous definition of ``symmetry?'' \\

Let's begin by labeling the nodes of this graph in whatever way we'd like. For convenience, we'll use the numbers 0, 1, 2, 3, and 4, following our star-drawing convention. Now, take the graph shown below and rotate it one fifth of a revolution clockwise, as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \coordinate (a1) at (66:3);
  \coordinate (a2) at (138:3);
  \coordinate (a3) at (210:3);
  \coordinate (a4) at (282:3);
  \coordinate (a5) at (364:3);
  \coordinate (b1) at (42:3);
  \coordinate (b2) at (114:3);
  \coordinate (b3) at (186:3);
  \coordinate (b4) at (258:3);
  \coordinate (b5) at (340:3);
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
  \path[->,blue,line width=1mm] 
    (a1) edge [bend left=30] node {} (b1)
    (a2) edge [bend left=30] node {} (b2)
    (a3) edge [bend left=30] node {} (b3)
    (a4) edge [bend left=30] node {} (b4)
    (a5) edge [bend left=30] node {} (b5);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (162:3) {0};
  \node[state] (1) at (90:3) {1};
  \node[state] (2) at (18:3) {2};
  \node[state] (3) at (306:3) {3};
  \node[state] (4) at (234:3) {4};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

If you'll notice, this operation on the graph corresponds to finding a permutation of the labels on the nodes. Specifically, the node 0 ended up where the node 1 used to be, the node 1 ended up where the node 2 used to be, etc. And hey! We have a way of describing transformations like that.

\begin{enumerate}[label=\roman*.]
    \item Describe the permutation that the above rotation corresponds to using two-line notation. No justification is necessary.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak
Similarly, let's imagine that we mirror the graph horizontally, as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \coordinate (a) at (90:3.5);
  \coordinate (b) at (270:3);
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
  \path[-,thin,densely dotted]
    (a) edge node {} (b);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (4) at (234:3) {4};
  \node[state] (3) at (162:3) {3};
  \node[state] (2) at (90:3) {2};
  \node[state] (1) at (18:3) {1};
  \node[state] (0) at (306:3) {0};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

We can similarly think of this as a permutation. For example, node 1 maps to where node 3 used to be.

\begin{enumerate}[resume*]
    \item Describe the permutation that the above mirroring corresponds to using two-line notation. No justification is necessary.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

There are a number of other symmetries of this graph, and each one of them corresponds to a permutation of the nodes. However, not all node permutations correspond to symmetries. For example, imagine that we permute the nodes as shown here:

\begin{center}
\begin{minipage}{0.45\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (1) at (162:3) {1};
  \node[state] (2) at (90:3) {2};
  \node[state] (3) at (18:3) {3};
  \node[state] (4) at (306:3) {4};
  \path[-] 
    (0) edge node {} (2)
    (2) edge node {} (4)
    (4) edge node {} (1)
    (1) edge node {} (3)
    (3) edge node {} (0);
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill$\xRightarrow{\hphantom{-} ? \hphantom{-}}$\hfill
\begin{minipage}{0.45\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (234:3) {0};
  \node[state] (3) at (162:3) {3};
  \node[state] (1) at (90:3) {1};
  \node[state] (4) at (18:3) {4};
  \node[state] (2) at (306:3) {2};
  \path[-] 
    (0) edge node {} (1)
    (1) edge node {} (2)
    (2) edge node {} (3)
    (3) edge node {} (4)
    (4) edge node {} (0);
\end{tikzpicture}
\end{minipage}
\end{center}

Notice that, in the original graph, nodes 0 and 2 were adjacent, but after permuting the nodes they're no longer adjacent to one another. (Remember that \textit{adjacent} means ``directly linked by an edge;'' contrast this with \textit{connected}, which has a different meaning.) Similarly, in the original graph, nodes 0 and 1 were \textit{not} adjacent, but after applying the permutation they now are. \\

At this point, we've seen some positive examples of cases where we \textit{can} use permutations to model symmetries, along with a negative example of where we \textit{can't} use permutations to model symmetries. The question is, what was special about those original permutations? It's that they have the following property: those permutations keep adjacent nodes adjacent and keep non-adjacent nodes non-adjacent. \\

Formally speaking, let $G = (V, E)$ be a graph. A permutation $\sigma$ of the nodes of $V$ is called an \emph{automorphism} if the following is true about $\sigma$:
$$\forall u \in V. \forall v \in V . (\{u, v\} \in E \iff \{\sigma(u), \sigma(v)\} \in E)$$

The mathematical term ``automorphism'' (``self shape'') might seem really scary here, but it's just a fancy way of pinning down what we've been describing with the term ``symmetry.'' Restating the above in plain English, a permutation is an \emph{automorphism} of $G$ if
\begin{itemize}
    \item any two nodes that are adjacent in $G$ stay adjacent after applying $\sigma$, and
    \item any two nodes that aren't adjacent in $G$ stay nonadjacent after applying $\sigma$.
\end{itemize}

The permutations that you described in parts (i) and (ii) are automorphisms, while the permutation shown above on this page isn't. The rest of this question explores properties of automorphisms.

\begin{enumerate}[resume*]
    \item How many automorphisms does the graph of \{5 / 2\} have? Briefly describe what they are. No formal proof is needed.
    
    \annotate{Use your intuition behind what automorphisms are designed to formalize.}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
    \item Consider the graph shown below. It has two automorphisms. What are they? Express your answer using two-line notation.

    \begin{center}
    \begin{minipage}{0.5\textwidth}
    \tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
    \begin{tikzpicture}[node distance=2cm,on grid,auto,baseline={(current bounding box.north)}]
      \node[state] (1) {1};
      \node[state] (2) [right=of 1] {2};
      \node[state] (3) [right=of 2] {3};
      \node[state] (4) [right=of 3] {4};
      \path[-] 
        (1) edge node {} (2)
        (2) edge node {} (3)
        (3) edge node {} (4)
        (1) edge [bend left=50] node {} (3);
    \end{tikzpicture}
    \end{minipage}
    \end{center}
    
    A graph is just a pair of a set of nodes and a set of edges. We can draw a graph $G = (V, E)$ in two-dimensional space as a collection of circles and lines in lots of different ways. Sometimes, those drawings make it really easy to find symmetries. Sometimes, those drawings make it really hard to find symmetries.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
\end{enumerate}

To round out our discussion of automorphisms, we'd like you to prove one nice, formal result about them.

\begin{enumerate}[resume*]
    \item Let $G = (V, E)$ be a graph and let $\sigma$ and $\tau$ be two automorphisms of $G$. Prove that $\tau \circ \sigma$ is also an automorphism of $G$.
    
    \annotate{Write out the definition of an automorphism and make a list of what you'll need to show.}
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

\section{Chains and Antichains}
Let $A$ be an arbitrary set and $<_A$ be some strict order over $A$. A \textit{\textbf{chain in}} $\mathbf{<_A}$ is a series $x_1, \ldots , x_k$ of elements
drawn from $A$ such that 
\begin{equation*}
x_1 <_A x_2 <_A \ldots <_A x_k.
\end{equation*}
Intuitively, a chain is a series of values in ascending order according to the strict order $<_A$. The \textit{\textbf{length}} of a
chain is the number of elements in that chain.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the $\subsetneq$ relation over the set $\wp(\{a, b, c\})$, where $A \subsetneq B$ means that $A \subseteq B$ but $A \ne B$. Draw a diagram of this relation over this set by drawing a node for each element of $\wp(\{a, b, c\})$ and adding an arrow between two elements $S$ and $T$ if $S \subsetneq T$. \\ 

For simplicity, please omit any redundant arrows that can be inferred through transitivity. That is, if you've drawn something like this: 
\begin{center}
    \begin{minipage}{0.5\textwidth}
    \tikzset{every state/.style={inner sep=1pt,minimum size=1cm}}
    \begin{tikzpicture}[node distance=2cm,on grid,auto,baseline={(current bounding box.north)}]
      \node[state] (1) {S};
      \node[state] (2) [right=of 1] {T};
      \node[state] (3) [right=of 2] {U};
      \path[-{>[scale=2.5,
          length=3,
          width=3]}] 
        (1) edge node {} (2)
        (2) edge node {} (3)
        (1) edge [bend right=50] node {} (3);
    \end{tikzpicture}
    \end{minipage}
\end{center}
You should omit the arrow going from $S$ to $U$. As a sanity check, you should have 8 nodes and 12 arrows (if you've removed redundant arrows). 
\begin{shaded}
Provide a picture here.
\end{shaded}
    
\item Consider the $\subsetneq$ relation over the set $\wp(\{a, b, c\})$. What is the length of the longest chain in this strict order? Give an example of a chain with that length.
No justification is necessary. 

\textit{\textcolor{blue}{ Look at what you drew in part i. and see if you can find a visual intuition
for the definition of a chain. }}
\begin{shaded}
Write your answer here.
\end{shaded}
\end{enumerate}

Now, let's cover a new definition. An \textit{\textbf{antichain in $<_A$}} is a set $X \subseteq A$ such any two elements in $X$ are incomparable by the $<_A$ relation. In other words, a set $X \subseteq A$ is an antichain if
\begin{equation*}
\forall a \in X.\ \forall b \in X.\ (a \not<_A b \ \ \land \ \ b \not<_A a)
\end{equation*}
The \textit{\textbf{size}} of an antichain $X$ is the number of elements in $X$.

\begin{enumerate}[resume*]
\item Consider the $\subsetneq$ relation over the set $\wp(\{a, b, c\})$. What is the size of the largest antichain in this
strict order? Give an example of an antichain with that size. No justification is necessary.

\textit{\textcolor{blue}{ Look what you drew in part i. and see if you can find a visual intuition
for the definition of an antichain. }}
\begin{shaded}
Write your answer here.
\end{shaded}
\end{enumerate}
Given an arbitrary strictly ordered set, you can't say anything \textit{a priori} about the size of the largest chain or
antichain in that strict order. However, you can say that at least one of them must be relatively large relative
to the strictly ordered set. \\

Let $<_A$ be an arbitrary strict order over an arbitrary set $A$ containing exactly $n^2+1$ elements for some natural
number $n \ge 1$. We're going to ask you to prove the following result: either $A$ contains a chain of length
$n+1$ or an antichain of size $n+1$ (or both). Following the advice from the Guide to Proofs on Discrete Structures, 
we'll prove this by instead proving that if $A$ does \textit{not} contain a chain of length $n+1$ or greater, then $A$ 
must contain an antichain of size $n+1$ or greater.

\begin{enumerate}[resume*]
\item For each element $a \in A$, we'll say that the \textit{\textbf{height}} of $a$ is the length of the longest chain whose final
element is $a$. Prove that if $A$ does not contain a chain of length $n+1$ or greater, then there must be
at least $n+1$ elements of $A$ at the same height. 

\textit{\textcolor{blue}{ Something to think about: what's the smallest possible
height of an element of $A$?}}
\begin{shaded}
Provide a proof here.
\end{shaded}

\item Your result from part (iv) establishes that if $A$ does not contain a chain of length $n+1$ or greater,
there must be a collection of $n+1$ elements of $A$ at the same height as one another. Prove that if $A$
does not contain a chain of length $n+1$ or greater, then it contains an antichain of size $n+1$ or
greater. 

\textit{\textcolor{blue}{ Although the picture you drew in part i. is a great way to build an intuition for this problem, we are still
expecting this proof to follow the proofwriting standards we've seen so far in this class, eg. picking arbitrary variables
and reasoning about them. }}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}

Intuitively speaking, if $<_A$ is a strict order over $A$ that represents some prerequisite structure on a group of
tasks, a chain represents a series of tasks that have to be performed one after the other, and an antichain
represents a group of tasks that can all be performed in parallel (do you see why?) In the context of parallel
computing, the result you've proved states that if a group of tasks doesn't contain long dependency
chains, that group must have a good degree of parallelism. Take CS149 for more information!

\section{Tiling with Triominoes}

A \emph{right triomino} is an L-shaped tile that looks like this: 
\begin{center}
\begin{tikzpicture}[scale=0.65]
\fill[black!25] (0,0) rectangle (2,1);
\fill[black!25] (0,1) rectangle (1,-1);
\draw[very thick] (0,1) -- (2,1);
\draw[very thick] (2,1) -- (2,0);
\draw[very thick] (1,0) -- (2,0);
\draw[very thick] (1,0) -- (1,-1);
\draw[very thick] (0,-1) -- (1,-1);
\draw[very thick] (0,1) -- (0,-1);
\end{tikzpicture}
\end{center}
Suppose you're given a $2^n \times 2^n$ grid of squares and want to tile it with right triominoes by covering the grid with triominoes such that all triominoes are completely on the grid and no triominoes overlap. Here's an attempt to cover an $8 \times 8$ grid with triominoes, which doesn't manage to cover all squares: \\
\begin{center}
\begin{tikzpicture}[scale=0.4]
\foreach \x in {0,...,8} {
        \draw[thick] (\x, 0) -- (\x, 8);
        \draw[thick] (0, \x) -- (8, \x);
}
\end{tikzpicture}
\hspace{0.8cm}
\begin{tikzpicture}[scale=0.4]
\draw [fill=black!25] (0, 0) rectangle (8, 8);
\foreach \x in {1,...,3} {
       \draw[thick] (2*\x, 0) -- (2*\x, 8);
       \draw[thick] (0, 2*\x) -- (8, 2*\x);
}
\draw [fill=black!25] (1, 1) rectangle (3, 3);
\draw [fill=black!25] (1, 5) rectangle (3, 7);
\draw [fill=black!25] (5, 5) rectangle (7, 7);
\draw [fill=black!25] (2, 2) rectangle (4, 4);
\draw [fill=black!25] (2, 4) rectangle (4, 6);
\draw [fill=black!25] (4, 4) rectangle (6, 6);
\draw [fill=black!25] (3, 3) rectangle (5, 5);
\draw [fill=black!25] (4, 2) rectangle (6, 4);
\draw [fill=black!25] (5, 1) rectangle (7, 3);
\draw [fill=white] (6,2) rectangle (7,3);
\end{tikzpicture}
\end{center}

Amazingly, it turns out that it is always possible to tile any $2^n \times 2^n$ grid that's missing exactly one square with right triominoes. It doesn't matter what $n$ is or which square is removed; there is always a solution to the problem. For example, here are all the ways to tile a $4 \times 4$ grid that has a square missing: \\

\begin{center}
\begin{tikzpicture}[scale=0.4]
\foreach \x in {0,...,3} \foreach \y in {0,...,3} {
        \draw [fill=black!25] (5*\x+1, 5*\y+1) rectangle (5*\x+5, 5*\y+5);
        \draw[thick] (5*\x+3, 5*\y+1) -- (5*\x+3, 5*\y+5);
        \draw[thick] (5*\x+1, 5*\y+3) -- (5*\x+5, 5*\y+3);
        \draw [fill=black!25] (5*\x+2, 5*\y+2) rectangle (5*\x+4, 5*\y+4);
        \draw [fill=white] (6*\x+1, 6*\y+1) rectangle (6*\x+2, 6*\y+2);
}
\foreach \x in {0,...,1} \foreach \y in {0,...,1} {
	\draw [fill=black!25] (5*\x+1, 5*\y+1) rectangle (5*\x+3, 5*\y+3);
	\draw [fill=black!25] (5*\x+1, 5*\y+13) rectangle (5*\x+3, 5*\y+15);
	\draw [fill=black!25] (5*\x+13, 5*\y+1) rectangle (5*\x+15, 5*\y+3);
	\draw [fill=black!25] (5*\x+13, 5*\y+13) rectangle (5*\x+15, 5*\y+15);
}
\foreach \x in {0,...,3} \foreach \y in {0,...,3} {
        \draw [fill=white] (6*\x+1, 6*\y+1) rectangle (6*\x+2, 6*\y+2);
}
\end{tikzpicture}
\end{center}

This question explores why this is the case.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Prove, by induction, that $4^n - 1$ is a multiple of three for any $n \in \N$ (An integer $n$ is a multiple of three if there is an integer $k$ such that $n = 3k$).
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

Any $2^n \times 2^n$ grid missing a square has a number of squares has exactly $4^n - 1$ squares, and so its number of squares is a multiple of three. Although you \textit{can} show that a figure \textit{can't} be tiled with triominoes by showing that its number of squares isn't a multiple of three, you \textit{can't} show that a figure \textit{can} be tiled with triominoes purely by showing that its number of squares is a multiple of three. The arrangement matters. \\

To convince yourself of this, can you think of an example of a grid made of squares where the number of squares \textit{is} a multiple of three, yet the figure cannot be tiled with right triominoes? This shows that your result from part i) is \textit{not} sufficient to prove that any $2^n \times 2^n$ grid that's missing exactly one square can be tiled with right triominoes.

\begin{enumerate}[resume*]
    \item Prove by induction that for any natural number $n$, any $2^n \times 2^n$ grid with any one square removed can be tiled by right triominoes. \\

    \annotate{Before you write this proof, try seeing if you can  find a nice recursive pattern you can follow that will let you fully tile any such board. You should be able to easily tile any $8 \times 8$ chessboard missing a square with right triominoes before you attempt to write up your answer. Once you can do this, formalize your idea in your answer. You may want to think about how to start with a larger board and subdivide it into some number of smaller boards.}
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section{The Circle Game}

Here's a game you can play. Suppose that you have a circle with $2n$ arbitrarily-chosen points on its circumference. Of these $2n$ points, $n$ of these points are labeled $+1$, and the remaining $n$ are labeled $-1$. One sample circle with eight points, of which four are labeled $+1$ and four are labeled $-1$, is shown below. \\

Here's the rules of the game. First, choose one of the $2n$ points as your starting point. Then, start moving clockwise around the circle. As you go, you'll pass through some number of $+1$ points and some number of $-1$ points. You lose the game if at any point on your journey you pass through more $-1$ points than $+1$ points. You win the game if you get all the way back around to your starting point without losing. \\

\begin{minipage}[t]{.65\textwidth}
For example, if you started at point A, the game would go like this: 
\begin{center}
\parbox{5cm}{
Start at A: +1. \\
Pass through B: +2.\\
Pass through C: +1.\\
Pass through D: 0.\\
Pass through E: -1. \textit{(You lose.)}
}
\end{center}
If you started at point G, the game would go like this:
\begin{center}
\parbox{5cm}{
Start at G: -1 \textit{(You lose.)}
}
\end{center}
However, if you started at point F, the game would go like this: 
\begin{center}
\parbox{5cm}{
Start at F: +1. \\
Pass through G: 0. \\
Pass through H: +1. \\
Pass through A: +2. \\
Pass through B: +3. \\
Pass through C: +2. \\
Pass through D: +1. \\
Pass through E: +0. \\
Return to F. \textit{(You win!)}
}
\end{center}
\end{minipage}
\tikzset{every node/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[x=1.5cm, y=1.5cm, baseline={(current bounding box.north)}]
\node[draw, circle, fill=black, text=white, label={0:-1}] (C) at (1.5, 0) {\textbf{C}};
\node[draw, circle, fill=black, text=white, label={45:+1}] (B) at (1.06, 1.06) {\textbf{B}};
\node[draw, circle, fill=black, text=white, label={90:+1}] (A) at (0,1.5) {\textbf{A}};
\node[draw, circle, fill=black, text=white, label={135:+1}] (H) at (-1.06, 1.06) {\textbf{H}};
\node[draw, circle, fill=black, text=white, label={180:-1}] (G) at (-1.5, 0) {\textbf{G}};
\node[draw, circle, fill=black, text=white, label={225:+1}] (F) at (-1.06, -1.06) {\textbf{F}};
\node[draw, circle, fill=black, text=white, label={270:-1}] (E) at (0, -1.5) {\textbf{E}};
\node[draw, circle, fill=black, text=white, label={315:-1}] (D) at (1.06, -1.06) {\textbf{D}};
\path[-] (A) edge [bend left=15] (B);
\path[-] (B) edge [bend left=15] (C);
\path[-] (C) edge [bend left=15] (D);
\path[-] (D) edge [bend left=15] (E);
\path[-] (E) edge [bend left=15] (F);
\path[-] (F) edge [bend left=15] (G);
\path[-] (G) edge [bend left=15] (H);
\path[-] (H) edge [bend left=15] (A);
\end{tikzpicture} \\

Interestingly, it turns out that no matter which $n$ points are labeled $+1$ and which $n$ points are labeled $-1$,
there is always at least one point you can start at to win the game. \\

Prove, by induction, that the above fact is true for any $n \ge 1$. \\

\annotate{Check the Guide to Induction and Inductive Proofwriting Checklist before starting this one. In particular, what's the quantifier in the statement we're trying to prove? Based on that, should we be trying to ``build up'' (take a smaller game and add nodes) or ``build down'' (take a larger game and remove nodes)?}

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

\pagebreak

\section{Nim}

\emph{Nim} is a family of games played by two players. The game begins with several piles of stones, each of which has zero or more stones in it, shared between the two players. Players alternate taking turns removing any nonzero number of stones from any single pile of their choice. If at the start of a player's turn all the piles are empty, then that player loses the game. \\

Prove, by induction, that if the game is played with just two piles of stones, each of which begins with exactly the same number of stones, then the second player can always win the game if she plays correctly. \\

\annotate{Play this game with a partner until you can find a winning strategy. Once you spot the pattern, see if you can find a way to formalize it using induction. Be wary of writing statements of the form ``and so on'' or ``by repeating this;'' those aren't rigorous ways to formalize that a process will eventually do something.}

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

\section{Bipartite Graphs}

There are a few famous families of graphs that come up over and over again. One of the most important types of graphs in computer science is the \textit{bipartite graph}, which is the focus of this problem. \\

Let's begin with a formal definition of bipartite graphs. An undirected graph $G = (V, E)$ is called \emph{bipartite} if there exists two sets $V_1$ and $V_2$ such that
\begin{itemize}
\item every node $v \in V$ belongs to exactly one of $V_1$ and $V_2$,
and
\item every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.
\end{itemize}

The sets $V_1$ and $V_2$ here are called the \textit{\textbf{bipartite classes}} of $G$. To help you get a better sense for why bipartite graphs are important and where they show up, let's work through a couple of examples. 

\begin{enumerate}[label=\roman*]
    \item Consider a graph where each node represents a square on a chessboard and where there's an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right). Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.

    \annotate{Draw lots of pictures!}
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

Bipartite graphs have many interesting properties. One of the most fundamental is this one:
\begin{center}
\emph{Theorem:} An undirected graph is bipartite if and only if it contains no cycles of odd length.
\end{center}

The forward direction of this implication has a nice intuition.

\begin{enumerate}[resume*]
    \item Explain, intuitively, why if $G$ is bipartite, then it has no cycles of odd length. Specifically, give us a brief, informal explanation as to why every cycle in $G$ has to have even length.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
\end{enumerate}

The reverse direction of this implication -- that if $G$ has no cycles of odd length, then $G$ is bipartite -- requires a different sort of argument. \\

Let's pick some arbitrary graph $G = (V, E)$ that has no cycles of odd length. For simplicity's sake, we'll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as individual graphs. \textit{(Do you see why?)} \\

Now, choose any node $v \in V$. Using node $v$ as an ``anchor point,'' we can define two sets $V_1$ and $V_2$ that we'll need for the remainder of this argument:
\begin{gather*}
V_1 = \{ x \in V \mid \text{there is an odd-length path from $v$ to $x$} \} \\
V_2 = \{ x \in V \mid \text{there is an even-length path from $v$ to $x$} \}
\end{gather*}
This turns out to be a really useful way to group the nodes of $G$.

\begin{enumerate}[resume*]
\item Given the choices of $G$ and $v$ from above, prove that $V_1$ and $V_2$ have no nodes in common.

\annotate{Remember that there might be multiple different paths of 
different lengths from v to some other node x, so
be careful not to talk about ``the'' path between v and x. Also note that these \emph{do not} have to be \emph{simple} paths.}

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

\item Using your result from part (iii), prove that $G$ is bipartite.

\annotate{The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. So start off by writing down a list of what you need to prove, then address each part in turn.}

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

\end{enumerate}

\pagebreak

\section*{Optional Fun Problem: Egyptian Fractions (Extra Credit)}

The Fibonacci sequence mentioned in Problem One is named after Leonardo Fibonacci, an eleventh-century Italian mathematician who is credited with introducing Hindu-Arabic numerals (the number system we use today) to Europe in his book \textit{Liber Abaci}. This book also contained an early description of the Fibonacci sequence, from which the sequence takes its name. \textit{Liber Abaci} also described a method of writing out fractions called \emph{Egyptian fractions}, which has been employed since ancient times; the Rhind Mathematical Papyrus, composed about 3,500 years ago in Thebes, includes several tables of fractions written out this way. \\

An Egyptian fraction is a sum of \emph{distinct} fractions whose numerators are all one (these fractions are called \textit{unit fractions}). For example, here are several Egyptian fraction representations of rational numbers:
\begin{alignat*}{3}
& \frac{2}{3} = \frac{1}{2} + \frac{1}{6} \qquad\qquad\qquad && \frac{2}{15} = \frac{1}{10} + \frac{1}{30} \\
& \frac{7}{15} = \frac{1}{3} + \frac{1}{8} + \frac{1}{120} && \frac{2}{85} = \frac{1}{51} + \frac{1}{255}
\end{alignat*}

Egyptian fractions are useful for divvying up objects fairly. For example, suppose you have two cakes to distribute to fifteen people -- that is, everyone should get a $\frac{2}{15}$ fraction of those cakes. Begin by slicing each cake into tenths and giving each person one ($\frac{1}{10}$). Now, take the remaining tenths you haven't distributed and cut them into thirds, giving thirtieths of the original cake. Each person then takes one of those ($\frac{1}{30}$). Because $\frac{1}{10} + \frac{1}{30} = \frac{2}{15}$, everyone gets their fair share. Pretty cool, isn't it? \\

One way of finding an Egyptian fraction representation of a rational number is to use a \textit{greedy algorithm} that works by finding the largest unit fraction at any point that can be subtracted out from the rational number. For example, to compute the fraction for $\frac{42}{137}$, we would start off by noting that $\frac{1}{4}$ is the largest unit fraction less than $\frac{42}{137}$. We then say that
$$\frac{42}{137} = \frac{1}{4} + \left(\frac{42}{137} - \frac{1}{4}\right) = \frac{1}{4} + \frac{31}{548}$$
We then repeat this process by finding the largest unit fraction less than $\frac{31}{548}$ and subtracting it out. This number is $\frac{1}{18}$, so we get
$$\frac{42}{137} = \frac{1}{4} + \left(\frac{42}{137} - \frac{1}{4}\right) = \frac{1}{4} + \frac{1}{18} + \left(\frac{31}{548} - \frac{1}{18}\right) = \frac{1}{4} + \frac{1}{18} + \frac{5}{4,932}$$
The largest unit fraction we can subtract from $\frac{5}{4,932}$ is $\frac{1}{987}$:
$$\frac{42}{137} = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} + \left(\frac{5}{4,932} - \frac{1}{987}\right) = \frac{1}{4} + \frac{1}{18} + \frac{1}{987} + \frac{1}{1,622,628}$$
And at this point we're done, because the leftover fraction is itself a unit fraction. \\

Prove that the greedy algorithm for Egyptian fractions always terminates for any rational number $r$ in the range $0 < r < 1$ and always produces a valid Egyptian fraction. (A \emph{rational number} is a real number that can be written as $r = \frac{p}{q}$ for some integers $p$ and $q$ where $q \neq 0$.) That is, the sum of the unit fractions should be the original number, and no unit fraction should be repeated. This shows that every rational number in the range $0 < r < 1$ has at least one Egyptian fraction representation.
\begin{shaded}
Provide a proof here.
\end{shaded}

\end{document}