HMMT 二月 2008 · TEAM1 赛 · 第 1 题

HMMT February 2008 — TEAM1 Round — Problem 1

[ 20 ] Determine the number of ways of walking from (0 , 0) to (5 , 5) using only up and right unit steps such that the path does not pass through any of the following points: (1 , 1) , (1 , 4) , (4 , 1) , (4 , 4). 1

解析

[ 20 ] Determine the number of ways of walking from (0 , 0) to (5 , 5) using only up and right unit steps such that the path does not pass through any of the following points: (1 , 1) , (1 , 4) , (4 , 1) , (4 , 4). Answer: 34 Solution: In the following figure, each lattice point (with the bottom-left-most point (0 , 0)) is labeled with the number of ways of reaching there from (0 , 0). With the exception of the forbidden points, the labels satisfy the recursion formula f ( x, y ) = f ( x − 1 , y ) + f ( x, y − 1). We see from the diagram that there are 34 ways to reach (5 , 5). 1 1 5 17 17 34 1 0 4 12 0 17 1 2 4 8 12 17 1 1 2 4 4 5 1 0 1 2 0 1 1 1 1 1 1 1 1 1