% % 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 Fall 2018 by Michael Zhu \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{wrapfig} \usepackage{hyperref} \usepackage{mathrsfs} \title{CS 103: Mathematical Foundations of Computing\\Problem Set \#5} \author{Your Name(s) Here} \date{\today} \lhead{Your Name(s) Here} \chead{Problem Set \#5} \rhead{\today} \lfoot{} \cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 2018} \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 \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. \pagebreak \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. \begin{enumerate}[resume*] \item Draw a picture of a figure made of squares where the number of squares is a multiple of three, yet the figure cannot be tiled with right triominoes. Briefly justify your answer; no formal proof is necessary. \begin{shaded} Draw your answer and provide justification here. \end{shaded} \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{It'll All Even Out} Our very first proof by induction was the proof that for any natural number $n$, we have that \begin{equation*} 2^0 + 2^1 + 2^2 + \ldots + 2^{n-1} = 2^n - 1. \end{equation*} This result is still true for the case where $n = 0$, since in that case the sum on the left-hand side of the equation is the \textit{empty sum} of zero numbers, which is by definition equal to zero. It's also true for the case where $n = 1$; in that case, the sum on the left-hand side of the equality just has a single term in it ($2^0$) and the right-hand side has the same value. \\ Below is a proof by complete induction of an incorrect statement about what happens when you sum up zero or more real numbers: \vspace{-2em} \begin{quote} \begin{thm} The sum of any number of real numbers is even. \end{thm} \begin{prf} Let $P(n)$ be the statement ``the sum of any $n$ real numbers is even.'' We will prove by complete induction that $P(n)$ holds for all $n \in \N$, from which the theorem follows. As a base case, we prove $P(0)$, that the sum of any 0 real numbers is even. The sum of any zero numbers is the empty sum and is by definition equal to 0, which is even. Thus $P(0)$ holds. For our inductive step, assume for some arbitrary $k \in \N$ that $P(0), \ldots,$ and $P(k)$ are true. We will prove that $P(k+1)$ is true, meaning that the sum of any $k+1$ real numbers is even. To do so, let $x_1, x_, \ldots, x_k$, and $x_{k+1}$ be arbitrary real numbers and consider the sum \begin{equation*} x_1 + x_2 + \ldots + x_k + x_{k+1}. \end{equation*} We can group the first $k$ terms and the last term independently to see that \begin{equation*} x_1 + x_2 + \ldots + x_k + x_{k+1} = (x_1 + x_ + \ldots + x_k) + (x_{k+1}). \end{equation*} Now, consider the sum $x_1 + x_ + \ldots + x_k$ of the first $k$ terms. This is the sum of $k$ real numbers, so by our inductive hypothesis that $P(k)$ is true we know that this sum must be even. Similarly, consider the sum $x_{k+1}$ consisting of just the single term $x_{k+1}$. By our inductive hypothesis that $P(1)$ is true, we know that this sum must be even. Overall, we have shown that $x_1 + x_2 + \ldots + x_k + x_{k+1}$ can be written as the sum of two even numbers (namely, $x_1 + x_ + \ldots + x_k$ and $x_{k+1}$), so $x_1 + x_2 + \ldots + x_k + x_{k+1}$ is even. Thus $P(k+1)$ is true, completing the induction. \end{prf} \end{quote} Of course, this result has to be incorrect, since there are many sums of real numbers that don't evaluate to an even number. The sum $2 + 3 + 4$, for example, works out to 9, and the sum $\pi + 1$ doesn't even work out to an integer! \\ What's wrong with this proof? Be as specific as possible. For full credit, you should be able to identify a specific claim made in the proof that is not correct, along with an explanation as to why it's incorrect. \\ \annotate{Think about our ``induction as a machine'' analogy from lecture that explains why you can start with a base case and inductive step and end up with a proof that works for all natural numbers. See what happens if you try that out here.} \begin{shaded} Write your answer here. \end{shaded} \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.} \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} \pagebreak \section{Transitive Closures} Given a binary relation $R$ over a set $A$ and a natural number $n \geq 1$, we can define a new relation called the \emph{nth power of R}, denoted \emph{R}$^n$, over the same set $A$. This family of relations is defined as follows: \begin{minipage}[t]{.8\textwidth} \begin{alignat*}{3} &xR^1y \qquad &&\text{if} \qquad xRy. \\ &xR^{n+1}y &&\text{if} \qquad \exists z \in A. (xRz \land zR^ny). \end{alignat*} That definition might look like quite a mouthful, but it has a really nice intuition. \begin{enumerate}[label=\roman*.] \item To the right is a drawing of a binary relation $S$ over the set $\{a, b, c, d, e\}$. Draw a picture of $S^2$ and a picture of $S^3$. \end{enumerate} \end{minipage} \tikzset{every state/.style={inner sep=1pt,minimum size=20pt}} \begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}] \node[state] (a) at (234:2) {a}; \node[state] (b) at (162:2) {b}; \node[state] (c) at (90:2) {c}; \node[state] (d) at (18:2) {d}; \node[state] (e) at (306:2) {e}; \path[->] (a) edge node {} (c) (c) edge node {} (e) (e) edge node {} (b) (b) edge node {} (d) (d) edge node {} (a); \end{tikzpicture} \begin{shaded} Place your pictures here. \end{shaded} The notation in powers of relations looks like the notation for exponentiation, and for good reason. Here's a useful lemma about powers of relations that we're going to ask you to prove: \begin{center} \textbf{Lemma}: For any positive natural numbers $m$ and $n$, if $aR^mb$ and $bR^nc$, then $aR^{m+n}c$. \end{center} The lemma shown above concerns natural numbers, and so it's a candidate for a proof by induction. However, unlike the other induction results you've seen so far, this one involves two natural numbers, not one. It's still possible to use induction to prove this result, though. \begin{enumerate}[resume*] \item Consider the predicate $P(m)$ defined below: \begin{center} $P(m)$ is ``for any natural number $n > 0$ and any $a, b, c \in A$, if $aR^mb$ and $bR^nc$, then $aR^{m+n}c$.'' \end{center} Suppose we prove $P(m)$ holds for all $m > 0$ using a proof by induction. Explain why this proves the above lemma. \begin{shaded} Write your answer here. \end{shaded} \item Let $R$ be some binary relation over a set $A$ (not necessarily a transitive relation). Prove by induction on $m$ that if $aR^mb$ and $bR^nc$, then $aR^{m+n}c$. \annotate{There are a lot of variables to keep track of here in the course of this proof, so be extremely careful to scope and introduce your variables properly. The inductive step of this problem, in particular, would be a great place to write out two columns, one of the things you're assuming, and one of the things that you're proving.} \annotate{The most common class of mistake we tend to see on this problem is mixing up arbitrarily-chosen values with placeholders. One specific thing to keep an eye on: \emph{make specific claims about specific variables}, and, specifically, \emph{be very careful to make sure you aren't using placeholder variables}.} \annotate{Is this a problem where you'll induct up? Or induct down?} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} The \emph{transitive closure} of a binary relation $R$ over a set $A$, denoted \emph{R}$^+$, is a binary relation over $A$ defined as follows: $$xR^+y \qquad \text{if} \qquad \exists n \in \N. (n \geq 1 \land xR^ny).$$ \begin{enumerate}[resume*] \item Let $S$ be the relation over $\{a, b, c, d, e\}$ drawn above. Draw a picture of the relation $S^+$. \begin{shaded} Place your picture here. \end{shaded} \item Let $R$ be an arbitrary binary relation over a set $A$. Using your result from part (iii) of this problem, prove that $R^+$ is transitive. \annotate{Be sure to set this problem up properly. If you did everything correctly, the proof should be rather elegant and straightforward.} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} Transitive closures show up all the time in discrete mathematics. You'll see an example of them when we play around with context-free grammars next week. \pagebreak \section{The Star-Drawing Saga, Part IV: The Grand Finale} A powerful technique in any mathematician's toolbox is the concept of \emph{dual objects}. The formal definition of a dual object varies by context, but the key idea is to take an object made from two different parts, swap the meanings of those parts, and end up with a new object related to the one we started with. \\ \begin{minipage}[t]{.64\textwidth} Every star $\{p / s\}$ has an associated \emph{dual star} $\{s / p\}$. In other words, starting with a $p$-pointed star with a step size of $s$, we create a new star with $s$ points and a step size of $p$. That new star might have a step size that's much, much larger than its number of points, but that's nothing to worry about. It's still perfectly mathematically valid! For example, here's the $\{12 / 5\}$ star and its dual, the $\{5 / 12\}$ star. You might notice that the $\{5 / 12\}$ star looks a lot like the $\{5 / 2\}$ star -- more on that later -- but it is indeed $\{5 / 12\}$. \end{minipage} \begin{minipage}[t]{.16\textwidth} \begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}] \coordinate (0) at (0:2); \coordinate (1) at (30:2); \coordinate (2) at (60:2); \coordinate (3) at (90:2); \coordinate (4) at (120:2); \coordinate (5) at (150:2); \coordinate (6) at (180:2); \coordinate (7) at (210:2); \coordinate (8) at (240:2); \coordinate (9) at (270:2); \coordinate (10) at (300:2); \coordinate (11) at (330:2); \draw[-,violet] (0) -- (5) -- (10) -- (3) -- (8) -- (1) -- (6) -- (11) -- (4) -- (9) -- (2) -- (7) -- (0); \end{tikzpicture} \end{minipage} \begin{minipage}[t]{.16\textwidth} \begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}] \coordinate (4) at (234:2); \coordinate (3) at (162:2); \coordinate (2) at (90:2); \coordinate (1) at (18:2); \coordinate (0) at (306:2); \draw[-,violet] (0) -- (2) -- (4) -- (1) -- (3) -- (0); \end{tikzpicture} \end{minipage} \\ On Problem Set Two, you proved that $\{p / s\}$ is simple if and only if there is an integer $t$ where $1 \equiv_p st$. Technically, you only proved this theorem in the case where $p > 0$, but for the purposes of this problem, we're going to extend this theorem and assume it holds for all natural numbers $p$, not just positive ones. \begin{enumerate}[label=\roman*.] \item Using the above theorem, prove that if $p$ and $s$ are natural numbers, then $\{p / s\}$ is simple if and only if its dual star is simple. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} You might have noticed that the $\{5 / 12\}$ star looks a lot like the $\{5 / 2\}$ star. To formalize why this is, we'll need to use the \emph{division algorithm}, which, despite the CS-sounding name, isn't actually an algorithm. It's the following fact about natural numbers: \begin{center} \emph{The Division Algorithm}: For any natural numbers $m$ and $n$ where $n \neq 0$, \\ there exist unique natural numbers $q$ and $r$ where $m = nq + r$ and $r < n$. \end{center} This is the fancy mathematical way of saying ``you can divide $m$ by $n$ to get a quotient ($q$) and a remainder ($r$), and the remainder $r$ is always less than $n$.'' I find it amusing that we have such a weighty name for something so simple, but hey, that's the convention. \begin{enumerate}[resume*] \item Let $p$ and $s$ be natural numbers where $s > 0$ and let $r$ be the remainder you get via the division algorithm when dividing $p$ by $s$. Explain, intuitively, why $\{s / p\}$ and $\{s / r\}$ are the same star. \annotate{Note that the roles of the variables $s$ and $p$ are reversed from their normal arrangement in this problem.} \begin{shaded} Write your answer here. \end{shaded} \item Let $p$ and $s$ be natural numbers where $s > 0$ and let $r$ be the remainder you get via the division algorithm when dividing $p$ by $s$. Prove that $\{p / s\}$ is simple if and only if $\{s / r\}$ is simple. \annotate{We're looking for a rigorous proof here involving modular congruence, so while the intuition from part (ii) might come in handy here, you still need to use a rigorous proof.} \begin{shaded} Provide a proof here. \end{shaded} \item Using your result from part (iii), prove or disprove: $\{5,480 / 411\}$ is simple. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} And now the grand finale. Under what circumstances is a star simple? You know from Problem Set Two that if $\{p / s\}$ is a simple star, then $p$ and $s$ are coprime. And based on what you've seen above, you now have enough to prove the converse of this statement. \begin{enumerate}[resume*] \item Prove by induction on $s$ that if $p$ and $s$ are coprime natural numbers, then $\{p / s\}$ is a simple star. Feel free to use the fact that the only natural number coprime with 0 is 1. \annotate{Problem Seven asked you to do a proof by induction involving multiple variables. Use the same idea here. Hint: at some point this involves that proving that $k+1$ and $r$ (where $r$ = $p$\%$s$) are coprime.} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} You've come quite a long way since you first tried drawing a simple 7-pointed star! You've explored modular arithmetic, coprimality, and now the division algorithm and induction! There are so many other questions you could ask about stars. Although $\{8 / 2\}$ isn't a simple star, you can draw an eight-pointed star as two copies of the $\{4 / 1\}$ star. Is there some rule about how many copies of simple stars you'd need for a general $\{p / s\}$, or what those simple stars would be? If you keep on exploring these questions -- which we hope you do! -- you'll quickly run into concepts from group theory, number theory, and abstract algebra. For more on this, check out Math 120, Math 152, and CS255! \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}