Problem Circle Solutions
Past Problem Circle Solutions
In the Problem Circle from the Autumn 2012 issue of MTCircular, Joshua Zucker posed the following problem:
Start with a list of the two numbers: 1, 1. Then, from that list, generate a new list by inserting the sum of each
pair of numbers between those two numbers. Continue to generate new lists in this way. Thus, the next lists are
1, 2, 1 and 1, 3, 2, 3, 1 and so on. How many 2012s are found in the 2012th list?
Page 17 of the Winter 2013 issue of MTCircular includes a description of work by Mary Fay-Zenk and Richard Grassl on this problem.
Joshua Zucker writes, "My favorite introduction to the magic of this sequence comes from Brent Yorgey's Math Less Traveled blog, which has a series of about a dozen posts on two of the most interesting aspects of this sequence. First, if you leave off the 1 at the end of each row, the nth number you encounter is the number of ways of writing n as the sum of at most 2 copies of each power of 2. For instance, the tenth number is 5 because 10 = 8 + 2 = 8 + 1 + 1 = 4 + 4 + 2 = 4 + 4 + 1 + 1 = 4 + 2 + 2 + 1 + 1 gives 5 such representations. Secondly, if you take the ratios of successive terms, you find that consecutive terms are relatively prime, and what's more, every positive rational appears exactly once!
"Because of this result, the number of columns of 2012s is given by the number of ways of writing 2012 as the sum of two relatively prime numbers, which is also equal to the number of simplified fractions with denominator 2012.
"For more, take a look at the links in the Online Encyclopedia of Integer Sequences. In particular, the amazing fraction result comes from a famous paper of Calkin and Wilf that is quite readable for nonmathematicians though it was written for a mathematical audience. There is also plenty of further reading (e.g., http://oeis.org/wiki/User:Peter_Luschny/SternsDiatomic and http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF) that could be done on this topic!"