Fractions on a Binary Tree
Let a/b be a fraction in lowest terms, where a and b are positive integers, a < b. Place it at the root of a binary tree. Next form its two children a/(a+b) and b/(a+b). Continue this process indefinitely to obtain the following tree diagram.
Find a and b such that the diagram starting with a/b contains all positive fractions less than 1.
- J. Cofman, What To Solve?, Oxford Science Publications, 1996.
- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Euclid's Game
- Binary Euclid's Algorithm>
- gcd and the Fundamental Theorem of Arithmetic
- Extension of Euclid's Algorithm
- Stern-Brocot Tree
- Farey series
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Equivalence relations
- A real life story
Let's first show that if the diagram contains all positive fractions, then a/b must be equal to 1/2. Assume, on the contrary, that 1/2 appears somewhere inside the tree. This means that for some p and q either
The algorithm has the property that successors of a fraction in lowest terms are automatically in lowest terms as well. If
Assume now that a/b = 1/2 and let p/q be a positive fraction in lowest terms less than 1. We want to show that p/q belongs to the tree.
- p/q < 1/2
- p/q > 1/2
In general, for positive fractions r/s less than 1 define the ancestor function A in the following manner: if r/s < 1/2 let
Starting with r/s, form a sequence of fractions:
|(1)||p/q, A(p/q), A(A(p/q)), ...|
Observe that the sequence of denominators is decreasing. Therefore, (1) is a finite sequence. Let An(p/q) be the last fraction in (1). Its denominator must be 2, for, otherwise, we would be able to continue. So the fraction is 1/2. The function A is called ancestor because it reverses the algorithm that defines the tree. Going backwards, in n steps, we'll get from 1/2 to p/q. Therefore, p/q is on the tree.
In the discussion on the Stern-Brocot tree we defined two functions:
However, by definition,
|(2)||1/fR(r/s) = fL(s/r).|
Recollect an observation we made in the discussion on the Stern-Brocot tree: fL transforms a row into the left half of the next row, fR transforms a row into the right half of the next row. From this remark and (2), it follows that the algorithm fills up the left side of the Stern-Brocot tree, a row at a time. The order of the fractions is, of course, all screwed up. For example, the 4th row will appear as 1/5, 4/5, 3/7, 4/7, 2/7, 5/7, 3/8, 5/8.
An upshot of having two solutions to the problem is that we can interpret Solution 1 as it applies to the Stern-Brocot tree. Unwittingly, we got a second proof that all fractions on the Stern-Brocot tree emerge in lowest terms. We also got a second proof of the fact that the Stern-Brocot tree contains all positive fractions.
Copyright © 1996-2018 Alexander Bogomolny