|
|
| Line 1: |
Line 1: |
| − | ==Problem==
| |
| − | Let <math>F_1 = F_2 = 1</math> and <math>F_n = F_{n-1} + F_{n-2}</math> for all <math>n\geq 2</math> be the Fibonacci numbers. If distinct positive integers <math>a_1, a_2, \dots a_n</math> satisfies <math>F_{a_1}+F_{a_2}+\dots+F_{a_n}=2023</math>, find the minimum possible value of <math>a_1+a_2+\dots+a_n.</math>
| |
| | | | |
| − | ==Solution==
| |
| − |
| |
| − | Suppose that <math>a_1 < a_2 < \dots < a_n</math> are taken such
| |
| − | <math>a_1 + a_2 + \dots + a_n</math> is minimal and
| |
| − | <cmath>
| |
| − | F_{a_1} + F_{a_2} + \dots + F_{a_n} = 2023
| |
| − | </cmath>
| |
| − |
| |
| − | Then, there are no consecutive <math>a_i</math> and <math>a_{i+1}</math> such
| |
| − | <math>a_i + 1 = a_{i+1}</math>.
| |
| − |
| |
| − | Generalize <math>2023</math> to any <math>k > 1</math>.
| |
| − | Let <math>a</math> be maximal such <math>F_a < k</math>
| |
| − | We claim that <math>a_n = a</math>.
| |
| − |
| |
| − | If <math>k</math> is a Fibonacci number the result follows.
| |
| − |
| |
| − | Note that
| |
| − | <cmath>
| |
| − | F_{2n+1} = F_{2n} + F_{2n-2} + \dots + F_2 + 1
| |
| − | </cmath>
| |
| − | and
| |
| − | <cmath>
| |
| − | F_{2n+2} = F_{2n+1} + F_{2n-1} + \dots + F_1
| |
| − | </cmath>
| |
| − | follow inductively.
| |
| − |
| |
| − | Thus, if <math>a_n \ne a</math> then
| |
| − | <cmath>
| |
| − | F_{a_1} + F_{a_2} + \dots + F_{a_n} \le F_a < k,
| |
| − | </cmath>
| |
| − | contradiction.
| |
| − |
| |
| − | Then, <math>a_n</math> be must maximal so we can reduce greedily to get
| |
| − | <cmath>
| |
| − | 2023 = F_{17} + F_{14} + F_9 + F_7 + F_3
| |
| − | </cmath>
| |
| − | and the answer is <math>17 + 14 + 9 + 7 + 3 = \boxed{50}</math>
| |
