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?

Step-by-step explanation:

Consider the FT 0, 1, 1, 2, 3, 5, 8, 13, 21, 24,45,

The numbers are arranged in order of even, odd, odd, even, odd, odd, even, odd, odd, even,

Hence, the loop contains 3 elements. If the number of terms is 2020 terms, then we have 673 loops + 1 element. (That is 3* 673 +1 = 2020) The last element will start the new loop and it is an even number.

In the other hand with 2019 terms, we have number of odd = 2* number of even. But the last term is even. That makes number of odd < twice number of even and it contradicts with the condition.

Therefore, the first term must be an odd number.

Also, the loop is either (odd, odd, even) or (odd, even, odd).

if m =1, only (odd, odd, even) satisfies the condition of the first 2 terms each < 2m.

If m =2, both satisfy.

But we have exactly 2415 FT sequence, m must be 1073 (half of 2415 + 0.5)

here are 4 possibilities for the parities of the first two terms of an FT sequence.

The sequence could begin odd, odd, or even, even, or odd, even, or even, odd.

In the table below, we write the parity of the first few terms of the FT sequences that begin in

each of the 4 possible ways.

The FT sequence beginning odd, odd (Parity #1) continues to repeat odd, odd, even.

Since 2019 is a multiple of 3 (2019 = 3 × 673), 1

of the first 2019 terms will be even-valued and

3 will be odd-valued, and so there are twice as many odd-valued terms as there are even-valued

terms in the first 2019 terms.

The 2020th term is odd (since the pattern begins with an odd-valued term), and so there are

more than twice as many odd-valued terms as there are even-valued terms in every FT sequence

that begins odd, odd.

This is exactly the required condition for the FT sequences that we are interested in.

How many FT sequences begin with two odd-valued terms, each of which is a positive integer

less than 2m?

There are 2m − 1 positive integers less than 2m (these are 1, 2, 3, 4, . . . , 2m − 1).

Since m is a positive integer, 2m is always an even integer and so 2m − 1 is always odd.

Thus, the list of integers from 1 to 2m − 1 begins and ends with an odd integer, and so the list

contains m odd integers and m − 1 even integers.

The first term in the sequence is odd-valued and so there are m choices for it.

Similarly, the second term in the sequence is also odd-valued and so there are also m choices

for it.

Thus, there are a total of m × m or m2 FT sequences that begin with two odd-valued terms.

Do any of the other 3 types of FT seqences satisfy the required condition that there are more

than twice as many odd-valued terms as there are even-valued terms?

Clearly the FT sequence beginning even, even (Parity #2) does not satisfy the required condition since every term in the sequence is even-valued.

The FT sequence beginning odd, even (Parity #3) continues to repeat odd, even, odd.

That is, in each successive group of three terms beginning at the first term, one out of three

terms will be even and two out of three terms will be odd.

As we saw previously, 2019 is a multiple of 3 and so 1

3

of the first 2019 terms are even-valued

and 2

3

are odd-valued.

Thus there are twice as many odd-valued terms as there are even-valued terms in the first 2019

terms.

The 2020th term is odd (since the pattern begins with an odd-valued term), and so there are

more than twice as many odd-valued terms as there are even-valued terms in every FT sequence

that begins odd, even.

How many FT sequences begin with an odd-valued first term and an even-valued second term,

each being a positive integer less than 2m?

As we showed previously, the list of integers from 1 to 2m − 1 begins and ends with an oddvalued integer, and so the list contains m odd-valued integers and m − 1 even-valued integers.

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.

(D)

Step-by-step explanation:

let's fu(!

step-by-step explanation:

step-by-step explanation: