HMMT 二月 2008 · TEAM1 赛 · 第 3 题

HMMT February 2008 — TEAM1 Round — Problem 3

[ 20 ] Let n > 4 be a positive integer. Determine the number of ways to walk from (0 , 0) to ( n, 2) using only up and right unit steps such that the path does not meet the lines y = x or y = x − n + 2 except at the start and at the end.

解析

[ 20 ] Let n > 4 be a positive integer. Determine the number of ways to walk from (0 , 0) to ( n, 2) using only up and right unit steps such that the path does not meet the lines y = x or y = x − n + 2 except at the start and at the end. 1 1 2 Answer: ( n − 5 n + 2) 2 Solution: It is easy to see the the first two steps and the last two steps must all be right steps. So we need to compute the number of walks from (2 , 0) to ( n − 2 , 0) that does not pass ( ) n − 2 through (2 , 2) and ( n − 2 , 0). There are paths from (2 , 0) to ( n − 2 , 0), and exactly two 2 ( ) n − 2 1 1 2 of them are invalid. So the answer is − 2 = ( n − 2)( n − 3) − 2 = ( n − 5 n + 2). 2 2 2