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 theinduction 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. Sothe result follows by induction. Finally, in the case r = 1, the quantity in question isn − 1
just 2 , and the result holds by Problem 1.
n − 1
- S ( n − 1 , r ) equals