HMMT 二月 2004 · 团队赛 · 第 4 题

HMMT February 2004 — Team Round — Problem 4

[25] Show that the sum of all the numbers in row n is at most ( n + 2)2 . A pair of successive numbers in the same row is called a switch pair if one number in the pair is even and the other is odd.

解析

Show that the sum of all the numbers in row n is at most ( n + 2)2 . Solution: The previous problem gives an upper bound on the number located r columns to the left of the initial 1; adding over all r = 1 , 2 , . . . , n gives ( ) n − 1 ∑ n − 1 ( s + 1) s s =0 ( ) n − 1 since the term occurs for the s + 1 values r = 1 , 2 , . . . , s + 1. But this sum equals s n − 2 ( n + 1)2 . For example, add the sum to itself and reverse the terms of the second sum to get ( ) ( ) n − 1 n − 1 ∑ ∑ n − 1 n − 1 ( s + 1) + ([ n − 1 − s ] + 1) s n − 1 − s s =0 s =0 ( ) ( ) n − 1 n − 1 ∑ ∑ n − 1 n − 1 n − 1 = ( n + 1) = ( n + 1) = ( n + 1)2 , s s s =0 s =0 and our original sum is half of this. n − 2 So the sum of the terms in row n to the left of the central column is at most ( n +1)2 . n − 2 Similarly, the sum of the terms to the right of the central column is at most ( n +1)2 . n − 1 Adding these together, plus the upper bound of 2 for the central number (Problem n − 1 1), gives our upper bound of ( n + 2)2 for the sum of all the numbers in the row. 2 A pair of successive numbers in the same row is called a switch pair if one number in the pair is even and the other is odd.