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

英文解析

4. 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 rcolumns to the left of the initial 1; adding over all r = 1 , 2 , . . . , n gives
   ( )
   n − 1
   ∑
   n − 1
   ( s + 1)
   s =0 s
   ( )
   n − 1
   since the term occurs for the s + 1 values r = 1 , 2 , . . . , s + 1. But this sum equalssn − 2
   ( n + 1)2 . For example, add the sum to itself and reverse the terms of the secondsum to get
   ( ) ( )
   n − 1 n − 1
   ∑ ∑
   n − 1 n − 1
   ( s + 1) + ([ n − 1 − s ] + 1)
   s n − 1 − ss =0 s =0
   ( ) ( )
   n − 1 n − 1
   ∑ ∑
   n − 1 n − 1
   n − 1 = ( n + 1) = ( n + 1) = ( n + 1)2 ,
   s ss =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 (Problemn − 1
   1), gives our upper bound of ( n + 2)2 for the sum of all the numbers in the row.
   A pair of successive numbers in the same row is called a switch pair if one number in the 2
   pair is even and the other is odd.