HMMT 二月 2003 · GEN1 赛 · 第 10 题

HMMT February 2003 — GEN1 Round — Problem 10

Bessie the cow is trying to navigate her way through a field. She can travel only from lattice point to adjacent lattice point, can turn only at lattice points, and can travel only to the east or north. (A lattice point is a point whose coordinates are both integers.) (0 , 0) is the southwest corner of the field. (5 , 5) is the northeast corner of the field. Due to large rocks, Bessie is unable to walk on the points (1 , 1), (2 , 3), or (3 , 2). How many ways are there for Bessie to travel from (0 , 0) to (5 , 5) under these constraints? 1

解析

Bessie the cow is trying to navigate her way through a field. She can travel only from lattice point to adjacent lattice point, can turn only at lattice points, and can travel only to the east or north. (A lattice point is a point whose coordinates are both integers.) (0 , 0) is the southwest corner of the field. (5 , 5) is the northeast corner of the field. Due to large rocks, Bessie is unable to walk on the points (1 , 1), (2 , 3), or (3 , 2). How many ways are there for Bessie to travel from (0 , 0) to (5 , 5) under these constraints? Solution: 32 In the figure, each point is labeled with the number of ways to reach that point. The numbers are successively computed as follows: The point (0 , 0) can trivially be reached in 1 way. When Bessie reaches any subsequent point ( x, y ) (other than a rock), she can arrive either via a northward or an eastward step, so the number of ways she can reach that point equals the number of ways of reaching ( x − 1 , y ) plus the number of ways of reaching ( x, y − 1). By iterating this calculation, we eventually find that (5 , 5) can be reached in 32 ways. (5,5) 1 4 7 10 16 32 1 3 3 3 6 16 1 2 0 3 10 1 1 2 3 7 1 1 2 3 4 1 1 1 1 1 1 (0,0) 3