#### Special Topic: Egyptian Fractions our normal fractions today, e.g. $\frac{5}{6}$ The Egyptian fractions: only have unit-fraction $\frac{1}{2}$, or $\frac{1}{5}$, etc. Rarely $\frac{2}{3}$ How do they express $\frac{5}{6}$? $\frac{5}{6} = \frac{1}{2} + \frac{1}{3}$ --- Let say we have 5 breads and 5 workers. We want to share breads equally to 5 workers, Easy! every one get 1 bread. Now we have 6 workers, 5 breads, How to share? - Using normal fraction, we say each of them get $\frac{5}{6}$. But how many cuts we need to share these 5 breads? With the worst situation, each bread 5 cuts, so 5 breads 25 cuts --- How about Egyptian Fraction? - $\frac{5}{6} = \frac{1}{2} + \frac{1}{3}$ - So for 5 breads, 3 of 5, we cut them half, 2 of 5, we cut it into 3 parts. How many cuts we need in total? - $3\times 1 + 2\times 2 = 7cuts$ - Significantly more efficient! --- Now how to transfer from normal fractions to Egyptian fractions? -Greedy Algorithm --- E.g. $\frac{7}{9}$ Step 1: is it larger than $\frac{1}{2}$? Yes, then $\frac{7}{9} - \frac{1}{2} = \frac{5}{18}$ Step 2: what is the largest unit fraction smaller than $\frac{5}{18}$? A good guess, $\frac{1}{4}$, then $\frac{5}{18} - \frac{1}{4} = \frac{1}{36}$ Step 3. Lucky! $\frac{7}{9} = \frac{1}{2} + \frac{1}{4} + \frac{1}{36}$