HMMT 二月 2008 · TEAM1 赛 · 第 1 题

英文解析

1. [ 20 ] Determine the number of ways of walking from (0 , 0) to (5 , 5) using only up and right unitsteps 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 theforbidden 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