2022 SSMO Speed Round Problems/Problem 4

Problem

Let $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n\geq 2$ be the Fibonacci numbers. If distinct positive integers $a_1, a_2, \dots a_n$ satisfies $F_{a_1}+F_{a_2}+\dots+F_{a_n}=2023$ , find the minimum possible value of $a_1+a_2+\dots+a_n.$

Solution

Suppose that $a_1 < a_2 < \dots < a_n$ are taken such $a_1 + a_2 + \dots + a_n$ is minimal and $F_{a_1} + F_{a_2} + \dots + F_{a_n} = 2023$

Then, there are no consecutive $a_i$ and $a_{i+1}$ such $a_i + 1 = a_{i+1}$ .

Generalize $2023$ to any $k > 1$ . Let $a$ be maximal such $F_a < k$ We claim that $a_n = a$ .

If $k$ is a Fibonacci number the result follows.

Note that $F_{2n+1} = F_{2n} + F_{2n-2} + \dots + F_2 + 1$ and $F_{2n+2} = F_{2n+1} + F_{2n-1} + \dots + F_1$ follow inductively.

Thus, if $a_n \ne a$ then $F_{a_1} + F_{a_2} + \dots + F_{a_n} \le F_a < k,$ contradiction.

Then, $a_n$ be must maximal so we can reduce greedily to get $2023 = F_{17} + F_{14} + F_9 + F_7 + F_3$ and the answer is $17 + 14 + 9 + 7 + 3 = \boxed{50}$

Page

Toolbox

Search

2022 SSMO Speed Round Problems/Problem 4

Problem

Solution