PUMaC 2010 · 组合（A 组） · 第 8 题
PUMaC 2010 — Combinatorics (Division A) — Problem 8
题目详情
- Let N be the sum of all binomial coefficients such that a and b are nonnegative integers b and a + b is an even integer less than 100. Find the remainder when N is divided by 144. ( ) ( ) a 0 (Note: = 0 if a < b , and = 1.) b 0 2
解析
- Let N be the sum of all binomial coefficients such that a and b are nonnegative integers b and a + b is an even integer less than 100. Find the remainder when N is divided by 144. ( ) ( ) a 0 (Note: = 0 if a < b , and = 1.) b 0 Answer: 3 Solution: Group the binomial coefficients by a + b . Then ( ) 49 n ∑ ∑ 2 n − k N = k n =0 k =0 The key step is to notice that the inner sum is the 2 n -th Fibonacci number F , where F is 2 n defined by F = F = 1 and F = F + F for all positive integers i . This can be proved 0 1 i +1 i i − 1 by induction. Alternatively, consider partitioning a row of 2 n squares into segments, each consisting of 1 or 2 squares. If there are k segments of 2 squares, then there are 2 n − k total segments, and ( ) 2 n − k therefore such partitions. As k varies through all possible values, the inner sum above k counts all such partitions. Therefore, the inner sum above is the number of partitions of a row of 2 n squares into segments of 1 or 2 squares. But the number of partitions of a row of m squares into segments of 1 or 2 squares is F . m Clearly we can partition a row of 0 or 1 squares just 1 way, and the number of partitions of a row of m squares is equal to the number of partitions ending in a 1-square segment, which is the number of partitions of a row of m − 1 squares, plus the number of partitions ending in a 2-square segment, which is the number of partitions of a row of m − 2 squares. Therefore the numbers of partitions of rows of squares satisfies the Fibonacci recursion and has the same initial values, so the number of partitions of a row of m squares into segments of 1 or 2 squares 7 is F . Therefore the inner sum is F . m 2 n Then N = F + F + · · · + F 0 2 98 = F + ( F + F + · · · + F ) 1 2 4 98 = F + ( F + F + · · · + F ) 3 4 6 98 . . . = F + ( F ) 97 98 = F 99 Now we want to evaluate F (mod 144). Note that F = 89 and F = 144. Therefore, 99 10 11 F ≡ 0 (mod 144), F ≡ 89 (mod 144), and F ≡ 89 (mod 144). Then F ≡ 89 F 11 12 13 12 0 (mod 144) and F ≡ 89 F (mod 144). Therefore, we find inductively that F ≡ 89 F 13 1 i +12 i (mod 144) for all nonnegative integers i . 8 8 Therefore, since 99 = 8 · 12 + 3, we have F ≡ 89 F ≡ 3 · 89 (mod 144). By the Chinese 99 3 Remainder Theorem, it is sufficient to calculate F modulo 16 and 9. We have 99 8 4 F ≡ 3 · 9 ≡ 3 · 81 ≡ 3 (mod 16) 99 8 F ≡ 3 · ( − 1) ≡ 3 (mod 9) 99 Therefore, by the Chinese Remainder Theorem, F ≡ 3 (mod 144), so the answer is 3 . 99 8