HMMT 二月 2020 · 冲刺赛 · 第 19 题

HMMT February 2020 — Guts Round — Problem 19

[10] The Fibonacci numbers are defined by F = 0 , F = 1, and F = F + F for n ≥ 2. There exist 0 1 n n − 1 n − 2 unique positive integers n , n , n , n , n , n such that 1 2 3 4 5 6 100 100 100 100 100 ∑ ∑ ∑ ∑ ∑ F = F − 5 F + 10 F − 10 F + 5 F − F . i + i + i + i + i n n n n n n 1 2 3 4 5 1 2 3 4 5 6 i =0 i =0 i =0 i =0 i =0 1 2 3 4 5 Find n + n + n + n + n + n . 1 2 3 4 5 6

解析

[10] The Fibonacci numbers are defined by F = 0 , F = 1, and F = F + F for n ≥ 2. There 0 1 n n − 1 n − 2 exist unique positive integers n , n , n , n , n , n such that 1 2 3 4 5 6 100 100 100 100 100 ∑ ∑ ∑ ∑ ∑ F = F − 5 F + 10 F − 10 F + 5 F − F . i + i + i + i + i n n n n n n 1 2 3 4 5 1 2 3 4 5 6 i =0 i =0 i =0 i =0 i =0 1 2 3 4 5 Find n + n + n + n + n + n . 1 2 3 4 5 6 Proposed by: Andrew Gu Answer: 1545 Solution: We make use of the identity ∑ F = F − 1 , i +2 i =0 (easily proven by induction) which implies ∑ F = F − F . i +2 k +1 i = k Applying this several times yields 100 100 100 100 100 ∑ ∑ ∑ ∑ ∑ F i + i + i + i + i 1 2 3 4 5 i =0 i =0 i =0 i =0 i =0 1 2 3 4 5 100 100 100 100 ∑ ∑ ∑ ∑ = ( F − F ) i + i + i + i +102 i + i + i + i +1 1 2 3 4 1 2 3 4 i =0 i =0 i =0 i =0 1 2 3 4 100 100 100 ∑ ∑ ∑ = ( F − 2 F + F ) i + i + i +204 i + i + i +103 i + i + i +2 1 2 3 1 2 3 1 2 3 i =0 i =0 i =0 1 2 3 100 100 ∑ ∑ = ( F − 3 F + 3 F − F ) i + i +306 i + i +205 i + i +104 i + i +3 1 2 1 2 1 2 1 2 i =0 i =0 1 2 100 ∑ = ( F − 4 F + 6 F − 4 F + F ) i +408 i +307 i +206 i +105 i +4 1 1 1 1 1 i =0 1 = F − 5 F + 10 F − 10 F + 5 F − F . 510 409 308 207 106 5 This representation is unique because the Fibonacci terms grow exponentially quickly, so e.g. the F 510 term dominates, forcing n = 510 and similarly for the other terms. The final answer is 1 510 + 409 + 308 + 207 + 106 + 5 = 1545 .