Problem

Source: Iranian National Olympiad (3rd Round) 2007

Tags: induction, algorithm, geometry, geometric transformation, number theory, Euclidean algorithm, relatively prime



Look at these fractions. At firs step we have 01 and 10, and at each step we write a+bc+d between ab and cd, and we do this forever 01100111100112112110011312231132213110 a) Prove that each of these fractions is irreducible. b) In the plane we have put infinitely many circles of diameter 1, over each integer on the real line, one circle. The inductively we put circles that each circle is tangent to two adjacent circles and real line, and we do this forever. Prove that points of tangency of these circles are exactly all the numbers in part a(except 10). c) Prove that in these two parts all of positive rational numbers appear. If you don't understand the numbers, look at here.