PUMaC 2023 · 组合（A 组） · 第 4 题
PUMaC 2023 — Combinatorics (Division A) — Problem 4
题目详情
- A sequence of integers a , a , . . . , a is said to be sub-Fibonacci if a = a = 1 and a ≤ 1 2 n 1 2 i a + a for all 3 ≤ i ≤ n . How many sub-Fibonacci sequences are there with 10 terms such i − 1 i − 2 that the last two terms are both 20?
解析
- A sequence of integers a , a , . . . , a is said to be sub-Fibonacci if a = a = 1 and a ≤ 1 2 n 1 2 i a + a for all 3 ≤ i ≤ n . How many sub-Fibonacci sequences are there with 10 terms such i − 1 i − 2 that the last two terms are both 20? Proposed by Daniel Carter Answer: 238 The number of sequences of length 10 that end in 20, 20 is just the number of sequences of length 9 which end in 20, since it is impossible for it to be the case that a < 0 and a = 20, 8 9 as the seventh Fibonacci number (i.e. the maximum possible value for a ) is only 13. 7 Let F be the Fibonacci numbers, where F = F = 1. Suppose we chose the maximum value n 1 2 a + a for every term a in our sequence except for some a , which we made k less than i − 1 i − 2 i j the maximum possible value. Then a = F − kF . This works similarly if we make n n n − j +1 multiple terms less than their maximum; if we define d = a − a − a , then we find i i i − 1 i − 2 P n a = F − d F . Since F = 34, the question is equivalent to asking for the number n n i n − i +1 9 i =3 P 9 of choices of d which make d F = 14. i i 10 − i i =3 In order to compute this, let’s define f ( k, t ) to be the number of choices of d such that i P t d F = k . By convention, f (0 , t ) = 1 for all t and f ( k, t ) = 0 if k is negative. We are i i i =1 looking for f (14 , 7). We have f ( k, t ) = f ( k, t − 1) + f ( k − F , t ), i.e. we either stop increasing t d and move on to smaller t or increment d . With this recurrence, we can quickly fill up a t t table of values for f until we hit f (14 , 7), which we find to be 238.