|
|
| 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>
| |
