2023 AMC 10B Problem 6

P1-10~2 minPrint

Modular Arithmetic Sequences & Series Use an invariant, parity, or coloring argument Compute small cases, spot the pattern, generalize

Let $L_1 = 1$ , $L_2 = 3$ , and $L_{n+2} = L_{n+1}+L_n$ for $n \geq 1$ . How many terms in the sequence $L_1, L_2, L_3, \cdots, L_{2023}$ are even?

Show solution without answering

Key insight

Look only at odd or even. The terms go odd, odd, even, and that pattern repeats, so a term is even exactly when its position is a multiple of 3.

Solution

The terms get huge fast, but we only care whether each one is odd or even. Adding two numbers, whether the answer is odd or even depends only on whether the two numbers were odd or even.

1. Write out the first few terms.
$1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ \ldots$
2. Mark odd (O) and even (E).

position	1	2	3	4	5	6	7	8	9
term	1	3	4	7	11	18	29	47	76
odd/even	O	O	E	O	O	E	O	O	E

3. See why the pattern keeps going. Each term is the sum of the two before it:
- odd $+$ odd $=$ even,
- odd $+$ even $=$ odd,
- even $+$ odd $=$ odd,

and then we are back to "odd, odd", so the same three steps happen again. The pattern O, O, E repeats forever.
4. So a term is even exactly when its position is a multiple of $3$ .
5. Count the multiples of $3$ from $1$ to $2023$ . They are $3, 6, 9, \ldots, 2022$ . Since $2022 = 3 \times 674$ , there are $674$ of them. ( $2023$ itself is not a multiple of $3$ .)

The answer is $\boxed{\textbf{(E)}\ 674}$ .

Why this works

In a sequence where each term is built from the terms just before it, "odd or even" also follows a rule that depends only on the terms just before it. There are only a few possible odd/even pairs, so the pattern has to repeat. Once you find the repeating block, the question becomes counting positions, which is easy even for a far-away term like number $2023$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Only parity matters, and the parity of each term is determined by the parities of the two before it. The first few terms are
$1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ \dots$
with parities odd, odd, even, odd, odd, even, $\dots$ Because odd $+$ odd $=$ even, odd $+$ even $=$ odd, and even $+$ odd $=$ odd, the pattern (odd, odd, even) repeats forever with period $3$ .

So $L_n$ is even exactly when $n$ is a multiple of $3$ . The multiples of $3$ from $1$ to $2023$ are $3, 6, \dots, 2022$ , and there are
$\left\lfloor \frac{2023}{3} \right\rfloor = 674$
of them.

The answer is $\boxed{\textbf{(E)}\ 674}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Introduction to Algebra, Chapter 21: Sequences & Series (§21.1, §21.2, §21.3, §21.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Number Theory, Chapter 10: Units Digits