Question

25. A sequence of positive integers with 2020 terms is called an FT sequence if each term

after the second is the sum of the previous two terms. For example, if the first two
terms of an FT sequence are 8 and 7, the sequence would begin 8,7,15,22,37,....
For some positive integer m, there are exactly 2415 FT sequences where the first two
terms are each less than 2m and the number of odd-valued terms is more than twice
the number of even-valued terms. What is the value of m?
(A) 21
(B) 69 (C) 115 (D) 35 (E) 105

Answer 1

The first term in the sequence is odd-valued and so there are m choices for it.2020 Gauss Contest Solutions Page 19

The second term in the sequence is even-valued and so there are m − 1 choices for it.

Thus, there are a total of m × (m − 1) FT sequences that begin with an odd-valued term

followed by an even-valued term.

Finally, we consider the FT sequences that begin with an even-valued term followed by an

odd-valued term (Parity #4).

Again, there are exactly twice as many odd-valued terms as there are even-valued terms in the

first 2019 terms (since the pattern repeats even, odd, odd).

However in this case, the 2020th term is even and so there are fewer than twice as many odd valued terms as there are even-valued terms.

Thus, there are m2 + m × (m − 1) FT sequences that satisfy the required conditions.

Since there are 2415 such FT sequences, we may solve m2 + m × (m − 1) = 2415 by trial and

error.

Evaluating m2 + m × (m − 1) when m = 30, we get 302 + 30 × 29 = 1770, and so m is greater

than 30.

When m = 33, we get 332 + 33 × 32 = 2145.

When m = 34, we get 342 + 34 × 33 = 2278.

When m = 35, we get 352 + 35 × 34 = 2415, as required.

Answer: (D)

Explanation: