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:
