CEMC Banner

Problem of the Week
Problem D and Solution
Teacher Road Trip 2


To help pass time on a long bus ride, a group of math teachers created a sequence of numbers, with each teacher saying one term in the sequence. The first and second teachers each said a non-negative integer, and every teacher after that said the sum of all of the previous terms in the sequence.

For example, if the first teacher said the number \(2\) and the second teacher said the number \(8\), then

How many possible sequences could the teachers have said if the first teacher said the number \(3\) and another teacher said the number \(3072\)?


We know how to construct the sequence, and we know that the first term is \(3\), but where is the term whose value is \(3072\)?

We could continue in this way until we discover all possible sequences that are formed according to the given rules with first term \(3\) and \(3072\) somewhere in the sequence. However, if we look at the prime factorization of \(3072\) we see that the highest power of \(2\) that divides \(3072\) is \(1024\) (or \(2^{10}\)), since \(3072=2^{10}\times 3\). In fact, dividing \(3072\) by \(1024\) would produce a third term that would be \(3\). The second term would then be \(0\), a non-negative integer, and the resulting sequence would be \(3,~0,~3,~6,~12,~24,~48,~96,~192,~384,~768,~1536,~3072,~6144,\ldots\).

If we divide \(3072\) by any integral power of \(2\) from \(2^0=1\) to \(2^{10}=1024\), the resulting third term would be an integer greater than or equal to \(3\), and \(3072\) would appear in each of these sequences. There are \(11\) such sequences. The number \(3072\) would appear somewhere from term \(3\) to term \(13\) in the acceptable sequence. However, \(3072\) can also appear as the second term, so there are a total of \(12\) possible sequences.

Could \(3072\) be the fourteenth term? From the fourteenth term to the third term we would need to divide \(3072\) by \(2^{11}\). The resulting third term would be \(\frac{3}{2}\). This would mean the second term is not an integer and so the sequence is not possible.

Therefore, there are a total of \(12\) such sequences.