PUMaC 2011 · 代数（A 组） · 第 2 题
PUMaC 2011 — Algebra (Division A) — Problem 2
题目详情
- [ 3 ] A function S ( m, n ) satisfies the initial conditions S (1 , n ) = n , S ( m, 1) = 1, and the recurrence S ( m, n ) = S ( m − 1 , n ) S ( m, n − 1) for m ≥ 2 , n ≥ 2. Find the largest integer k k such that 2 divides S (7 , 7).
解析
- We first define a new sequence P ( m, n ) such that P ( m, n ) is the largest power of 2 that divides S ( m, n ). The relation S ( m, n ) = S ( m − 1 , n ) S ( m, n − 1) implies that P ( m, n ) = P ( m, n − 1) + P ( m − 1 , n ), which reminds us of the Pascal recurrence. The initial conditions become P ( m, 1) = 0 , P (1 , 2 n + 1) = 0 , P (1 , 2) = 1 , P (1 , 4) = 2 , and P (1 , 6) = 1 . 2 Since the numbers are reasonable at this point, one could potentially write out all 7 or so entries for P ( m, n ) , 1 ≤ m, n ≤ 7 , fairly quickly, but there are more computationally-efficient methods. First Solution : Writing out the second row, P (2 , 2) = P (2 , 3) = 1 , P (2 , 4) = P (2 , 5) = 3 , P (2 , 6) = P (2 , 7) = 4. We take advantage of the fact that the Pascal recurrence is additive, in the sense that if P ( m, n ) = P ( m, n − 1) + P ( m − 1 , n ) for i = 1 , 2 , . . . , then any linear com- i i i ( ) ( ) ( ) m + n − 4 m + n − 4 m + n − 6 bination of the P ’s also satisfies the same recurrence. Notice that , , i m − 2 m − 2 m − 2 satisfy this recurrence, and that ( ) ( ) ( ) m + n − 4 m + n − 6 m + n − 8 P ( m, n ) = + 2 + m − 2 m − 2 m − 2 ( ) ( ) ( ) 10 8 6 for all 2 ≤ m, n ≤ 7 based on the initial conditions. Hence, P (7 , 7) = + 2 + = 370 . 5 5 5 Note that we only use the second row because the numbers are nicer. Essentially what we are doing here is writing the grid as a sum of multiple shifted copies of Pascal’s triangle. The second solution also uses the same technique, but uses shifted copies of Pascal’s triangles rooted at the diagonal entries P ( m, n ) where m + n = 9. Second Solution : Computing, we have P (7 , 7) = P (7 , 6) + P (6 , 7) = P (7 , 5) + 2 P (6 , 6) + P (7 , 5), and continuing in this manner (say by induction), we can express P (7 , 7) as a sum of 1 the product of elements of the 5th row of Pascal’s triangle and P ( k, 9 − k ). Thus P (7 , 7) = P (7 , 2) + 5 P (6 , 3) + 10 P (5 , 4) + 10 P (4 , 5) + 5 P (3 , 6) + P (2 , 7). We can calculate these diagonal entries P ( k, 9 − k ) fairly quickly from the inital conditions and the recurrence for P , and we obtain a final answer of 1 · 4 + 5 · 12 + 10 · 16 + 10 · 12 + 5 · 5 + 1 · 1 = 370 .