% % 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 % Updated for Fall 2019 by Joshua Spayd % Updated for Winter 2020 by Cynthia Lee \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[hidelinks]{hyperref} \usepackage{mathrsfs} \usepackage{colortbl} \usepackage{fourier} \usepackage{makecell} \title{CS 103: Mathematical Foundations of Computing\\Problem Set \#5} \author{Your Name(s) Here} \date{\today} % Running author based on https://tex.stackexchange.com/a/68310 \makeatletter \let\runauthor\@author \makeatother \lhead{\runauthor} \chead{Problem Set \#5} \rhead{\today} \lfoot{} \cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2020} \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} \newtheorem*{wrongthm}{(Incorrect!) Theorem} \newenvironment{wrongproof}{\paragraph{\it{(Incorrect!) Proof.}}} {\hfill\qedsymbol} \renewcommand{\headrulewidth}{0.4pt} \renewcommand{\footrulewidth}{0.4pt} \setlength{\parskip}{6pt} \setlength{\parindent}{0pt} \pagestyle{fancy} \renewcommand{\thefootnote}{\fnsymbol{footnote}} \definecolor{incorrect}{RGB}{182,0,12} % 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 way of defining an infinitely long sequence of numbers. A recurrence relation specifies the value of the first term or terms of the sequence, then defines the remaining entries from the previous terms. For example, here's a simple recurrence relation: \begin{align*} a_0 = 1 && a_{n+1} = 2a_n \end{align*} The first terms of this sequence are given as follows: \begin{itemize}[noitemsep,topsep=0pt] \item $a_0 = 1$, since that's what the first rule says. \item $a_1 = 2$, since the second rule says that $a_1 = 2a_0 = 2 \cdot 1 = 2$. \item $a_2 = 4$, since the second rule says that $a_2 = 2a_1 = 2 \cdot 2 = 4$. \item $a_3 = 8$, since the second rule says that $a_3 = 2a_2 = 2 \cdot 4 = 8$. \end{itemize} Extending further, this sequence starts off with the numbers $$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, \dots, $$ which all 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 \label{p:powinduct} 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:} \vspace{-18pt} \begin{alltt}\textcolor{blue}{ int a(int n) \{ if (n == 0) return 1; return 2 * a(n - 1); \}} \end{alltt} \vspace{-18pt} \annotate{For any $n \in \N$, you can compute \texttt{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 \texttt{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} \pagebreak Perhaps the most famous recurrence relation is the \emph{Fibonacci sequence}, which is defined as follows: \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 given as follows: \begin{itemize}[noitemsep,topsep=0pt] \item $F_0 = 0$, since that's what the first rule says. \item $F_1 = 1$, since that's what the second rule says. \item $F_2 = 1$, since the third rule says that $F_2 = F_0 + F_1 = 0 + 1 = 1$. \item $F_3 = 2$, since the third rule says that $F_3 = F_1 + F_2 = 1 + 1 = 2$. \item $F_4 = 3$, since the third rule says that $F_4 = F_2 + F_3 = 1 + 2 = 3$. \end{itemize} The first ten terms of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. \textit{(Make sure you see why!)} If you pull out a calculator and compute ratios of consecutive Fibonacci numbers, you'll find that the ratio tends toward 1.6180339\dots~. This number is the \emph{golden ratio}, denoted $\boldsymbol{\varphi}$ (the Greek letter phi). Its exact value is $\varphi = \frac{1+\sqrt{5}}{2}$, and $\varphi$ is the positive solution to the quadratic equation $x^2 = 1 + x$. There's a deep connection between Fibonacci numbers and the golden ratio. \begin{enumerate}[resume*] \item \label{p:fibinduct} Prove, by induction, that $\varphi^{n+1} = \varphi \cdot F_{n+1} + F_n$ for all natural numbers $n$. \annotate{While you can solve this problem by substituting $\varphi = \frac{1+\sqrt{5}}{2}$ and doing a bunch of algebra, you might find it more useful to use the fact that $\varphi$ is a solution to the equation $x^2 = x + 1$.} \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} \pagebreak \pagebreak \section{The Circle Game} You have a circle with $2n$ arbitrarily-chosen points on its circumference for some natural number $n \ge 1$. Of the $2n$ points, $n$ 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 a game you can play. Pick one of the $2n$ points as your starting point, then move clockwise around the circle. You lose the game if at any point on you pass through more $-1$ points than $+1$ points. You win the game if you get all the way back to your starting point without losing. For example, if you start at point A, the game would go like this: \begin{minipage}[t]{.65\textwidth} \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} 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{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: \\ \begin{tabular}{m{.25in}|p{\linewidth-.5in-6\tabcolsep}|m{.25in}} \arrayrulecolor{incorrect}\cline{2-2} \makecell[c]{\\[1.75in]\textcolor{incorrect}\danger} & \vspace{-3.25\baselineskip} \begin{wrongthm} The sum of any number of real numbers is even. \end{wrongthm} \begin{wrongproof} 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{wrongproof} \newline & \makecell[c]{\\[1.75in]\textcolor{incorrect}\danger} \\ \arrayrulecolor{incorrect}\cline{2-2} \end{tabular} 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 question, then, is where the proof breaks down. \begin{enumerate}[label=\roman*.,ref=(\roman*)] \item The proof defines a predicate $P(n)$, then uses complete induction to prove $P(n)$ holds for all $n \in \N$. Is $P(n)$ actually a predicate? Does it pass the Induction Proofwriting Checklist? Is it actually the case that, if $P(n)$ is true for all $n \in \N$, then the theorem in question is true? If any of your answers are ``no,'' explain why, pointing out, specifically, what the proof does wrong. \begin{shaded} Write your answer here. \end{shaded} \pagebreak \item Is $P(0)$ true? Is the base case of this proof written correctly? If not, point out a specific claim it makes that's incorrect and explain why it's incorrect. \annotate{We aren't looking for ``sins of omission'' here in the sense of ``the proof should have also done X in addition to what it already did.'' Rather, we're looking for ``sins of commission'' in sense of ``the proof does X, and X is incorrect.''} \begin{shaded} Write your answer here. \end{shaded} \pagebreak \item Is $P(1)$ true? Is the inductive step of this proof written correctly? If not, point out a specific claim it makes that's incorrect and explain why it's incorrect. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \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;'' induction is the proper way to formalize those sorts of ideas.} \annotate{Something to think about -- you know that the number of stones in each pile will be decreasing. Can you say how much that number will decrease by? Based on that, what style of proof should you use here?} \begin{shaded} Provide a proof here. \end{shaded} \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 \begin{wrapfigure}{r}{.35\textwidth} \begin{flushright} \vspace{-2em} \begin{tikzpicture}[scale=0.3] \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{flushright} \end{wrapfigure} \begin{itemize}[noitemsep,topsep=0pt] \item all triominoes are contained purely within the grid and don't hang off the sides, \item every square in the grid is completely covered by triominoes, and \item no triominoes overlap. \end{itemize} It's, unfortunately, never possible to perfectly tile such a board, but, amazingly, it turns out that it is always possible to tile any $2^n \times 2^n$ grid that's missing exactly one square. It doesn't matter what $n$ is or which square is removed; there is always a solution to the problem. To the right is a diagram showing how to do this for all $4 \times 4$ grids. 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{As a note, the fact that a $2^n \times 2^n$ grid missing a square has $4^n - 1$ total squares is true but mostly irrelevant here. A grid of dimension $(4^n - 1) \times 1$ also has $4^n - 1$ squares in it, but that grid, in general, can't be tiled by right triominoes because they're only one square wide. In other words, you can't prove this result simply by counting squares in the grid; the arrangement of those squares matters!} \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 \underline{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.} \annotate{Also, is this an ``induct up'' problem, or an ``induct down'' problem?} \begin{shaded} Provide a proof here. \end{shaded} \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 \emph{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 \emph{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}