HMMT 二月 2004 · 团队赛 · 第 1 题
HMMT February 2004 — Team Round — Problem 1
题目详情
- [10] Show that any number in row n (for n > 0) is at most 2 .
解析
-
- S ( n − 1 , r ) equals (( ) ( )) (( ) ( )) n − 2 n − 2 n − 2 n − 2
-
-
-
- · · · r − 2 r − 1 r − 1 r (( ) ( )) ( ) n − 2 n − 2 n − 2 · · · + + + n − 3 n − 2 n − 2 ( ) ( ) ( ) n − 1 n − 1 n − 1 = + + · · · + = S ( n, r ) . r − 1 r n − 1 Now we can prove the main statement by induction on n . The base case n = 1 is clear. If the statement holds for n − 1, then first suppose r > 1. Then the number in row n , r columns to the left, is the sum of two of the three numbers above it, which, by the induction hypothesis, are at most S ( n − 1 , r − 1) , S ( n − 1 , r ) , S ( n − 1 , r +1) respectively. Since the first two of these are greater than the last (because the summation formula ( ) ( ) n − 1 n − 1 gives S ( n − 1 , r − 1) = S ( n − 1 , r ) + and S ( n − 1 , r ) = S ( n − 1 , r + 1) + ), r − 2 r − 1 we have an upper bound of S ( n − 1 , r − 1) + S ( n − 1 , r ) = S ( n, r ) by the above. So the result follows by induction. Finally, in the case r = 1, the quantity in question is n − 1 just 2 , and the result holds by Problem 1. n − 1
-
-