Fractions in Ancient Egypt

Question

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$

Answer 1

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.

Answer 2

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

Answer 3

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.