HMMT 二月 2008 · TEAM1 赛 · 第 2 题

HMMT February 2008 — TEAM1 Round — Problem 2

[ 20 ] Let n > 2 be a positive integer. Prove that there are ( n − 2)( n + 1) ways to walk from 2 (0 , 0) to ( n, 2) using only up and right unit steps such that the walk never visits the line y = x after it leaves the origin.

解析

[ 20 ] Let n > 2 be a positive integer. Prove that there are ( n − 2)( n + 1) ways to walk from 2 (0 , 0) to ( n, 2) using only up and right unit steps such that the walk never visits the line y = x 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). ( ) n There are ways to walk from (2 , 0) to ( n, 2), and exactly one of those paths passes through 2 ( ) n 1 1 the 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 ) a using only up and right unit steps. This is true because there are a + b steps, and we need to choose a of them to be right steps, and the rest up steps.