PUMaC 2023 · 团队赛 · 第 12 题

PUMaC 2023 — Team Round — Problem 12

What is the sum of all possible subject to the restrictions that i ≥ 10 , j ≥ 0, and i + j ≤ 20? j 10 Count different i, j that yield the same value separately - for example, count both and 1 10 . 9

解析

What is the sum of all possible subject to the restrictions that i ≥ 10 , j ≥ 0, and i + j ≤ 20? j 10 Count different i, j that yield the same value separately - for example, count both and 1 10 . 9 Proposed by Nathan Bergman Answer: 27633 We refer to Pascal’s triangle. Here, we’ll solve the general case and plug in 10 , 20 at the end. It’s tempting to look at this as rows with decreasing numbers of elements, but it is better to i look at columns. To do so, change the problem to find the sum of all possible values of j n subject to the restrictions that i, j ≥ 0 and i + j ≤ n . This new problem has a sum of 2 − 1 (sum of Pascal’s triangle rows below row n ) larger than the previous problem, so we must subtract that at the end. Arranging this carefully, by looking at a sum of columns, we get: n 2 n − i X X j i i =0 j = i 5 Using the hockey stick identity, we can turn this into n X 2 n + 1 − i i + 1 i =0 Letting k = i + 1, we can rewrite this as n +1 X 2 n + 2 − k k k =1 By the Fibonacci identity for Pascal’s triangle, we know n +1 X 2 n + 2 − k = F 2 n +3 k k =0 Here, F = 0 , F = 1 , F = F + F for m ≥ 2. Applying the Fibonacci Identity to 0 1 m m − 1 m − 2 n Pascal’s Triangle gives our sum is F − 1. Subtracting our initial 2 − 1 gives a final answer 2 n +3 n of F − 2 . 2 n +3 10 Lastly, the problem asks for n = 10, so the answer is F − 2 = 28657 − 1024 = 27633. 23