Fractions in Ancient Egypt In ancient Egypt, fractions were written as sums of fractions with numerator 1. For instance,$ \frac{3}{5}=\frac{1}{2}+\frac{1}{10}$. Consider the following algorithm for writing a fraction $\frac{m}{n}$ in this form$(1\leq m < n)$: write the fraction $\frac{1}{\lceil n/m\rceil}$ , calculate the fraction $\frac{m}{n}-\frac{1}{\lceil n/m \rceil}$ , and if it is nonzero repeat the same step. Prove that this algorithm always finishes in a finite number of steps.
Note:if $ n\in \mathbf{Z} $ and $n-1<x\leq n ,  \lceil x\rceil=n$
 A: We proceed by induction on $m\in \Bbb{N}$.
Base Case: When $m=1$, $\dfrac{m}{n}$ is already in the desired form, so terminate.
Induction Hypothesis: Assume that for all $m \in \{1,...,k\}$ (where $k \geq 1$), the algorithm will terminate when its input is $\dfrac{m}{n}$.
It remains to prove the claim true for $m=k+1$. After one step of the algorithm, we obtain the new fraction:
$$
\dfrac{k+1}{n}-\dfrac{1}{\left\lceil \frac{n}{k+1} \right\rceil}
= \dfrac{\left\lceil \frac{n}{k+1} \right\rceil(k+1)-n}{\left\lceil \frac{n}{k+1} \right\rceil n}
$$
Now observe that:
$$ \begin{align*}
\left\lceil \frac{n}{k+1} \right\rceil(k+1)-n
&= \left( \left\lfloor \frac{n-1}{k+1} \right\rfloor+1 \right)(k+1) -n \\
&\leq \left( \frac{n-1}{k+1} +1 \right)(k+1) -n \\
&= (n-1)+(k+1) -n \\
&= k
\end{align*} $$
Hence, by the induction hypothesis, the algorithm must terminate. This completes the induction.
A: HINT: Use the division algorithm to write $n=mq+r$, where $q$ and $r$ are non-negative integers, and $0\le r<m$. I’ll leave the case $r=0$ to you. If $r>0$, then $$\frac1{\lceil n/m\rceil}=\frac1{q+1}\;,$$ so
$$\frac{m}n-\frac{1}{\lceil n/m\rceil}=\frac{m}{mq+r}-\frac1{q+1}=\frac{m-r}{(mq+r)(q+1)}\;.$$
Let this fraction be $\dfrac{a}b$ in lowest terms. Then $a\le m-r<m$.
A: One can always show that any fraction can be written as a sum of finite fractions, by the factorial rule.  That is for $\frac mn$, if $n \mid  f!$ then any $\frac mn$ can be written in no more than $f-1$ steps.
For the greedy algorithm, a fraction $\frac mn$, for being greater than $\frac 1a$, will leave a difference $\frac {am-n}{na}$
Suppose you have $\frac 1c \le \frac mn \le \frac 1{c-1}$.  Multiply the limits by $\frac mm$ to get the denominators $cm > n > cm-c$, and thence put $n = cm-x$, where $x \lt m$.
Then subtract $\frac 1c$ to get $\frac {cm}{c(cm-x)} - \frac {cm-x}{c(cm-x)} = \frac x{c(cm-x)}$.  Since $x<m$, each iteration produces a smaller $x$, which must ultimately divide the denominator.
