HMMT 二月 2008 · TEAM1 赛 · 第 2 题

英文解析

2. [ 20 ] Let n > 2 be a positive integer. Prove that there are ( n − 2)( n + 1) ways to walk from
   (0 , 0) to ( n, 2) using only up and right unit steps such that the walk never visits the line y = x 2
   after it leaves the origin.
   Solution: The first two steps can only go to the right. Then we need to compute the number of ways of walking from (2 , 0) to ( n, 2) which does not pass through the point (2 , 2).
   ( )
   There are ways to walk from (2 , 0) to ( n, 2), and exactly one of those paths passes throughn
   ( )2
   1 1 nthe point (2 , 2). So the number of valid paths is − 1 = n ( n − 1) − 1 = ( n − 2)( n + 1).
   2 2 2
   ( )
   a + b
   Remark: We used the well-known fact that there are ways to walk from (0 , 0) to ( a, b )
   using only up and right unit steps. This is true because there are a + b steps, and we need toachoose a of them to be right steps, and the rest up steps.