Problem:
The tree diagram below has nodes labeled with rational numbers. The top node, at level 0, is 21β. Each node baβ sprouts two nodes in the level below it, a+baβ and a+bbβ. For example, level 1 has nodes 1+21β=31β and 1+22β=32β.
At what level does the node 2720β appear in the diagram?
Answer Choices:
A. 5
B. 8
C. 12
D. 26
E. The node 2720β does not appear in the diagram.
Solution:
We work backwards from 2720β to the top of the tree.
Observations.
- Every node is less than 1: the top node is 21β, and both children a+baβ and a+bbβ of any node are less than 1.
- Every node is in lowest terms: if gcd(a,b)=1, then gcd(a,a+b)=gcd(b,a+b)=1.
So a node qpβ (in lowest terms) has denominator q=a+b and numerator a or b, where its parent is baβ. The parent is therefore qβppβ or pqβpβ, and since the parent must be less than 1, it is whichever of these two is less than 1:
parent of qpβ=max(p,qβp)min(p,qβp)β.
Applying this repeatedly,
2720ββΆ207ββΆ137ββΆ76ββΆ61ββΆ51ββΆ41ββΆ31ββΆ21β.
Reaching the top node 21β (level 0) takes 8 steps, so 2720β is at level 8.
Check (going down). 21ββ31ββ41ββ51ββ61ββ76ββ137ββ207ββ2720β, where each step uses one of the two rules baββ¦a+baβ or baββ¦a+bbβ.
The answer is (B) 8.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions