HMMT 二月 2003 · GEN1 赛 · 第 10 题

英文解析

10. Bessie the cow is trying to navigate her way through a field. She can travel onlyfrom lattice point to adjacent lattice point, can turn only at lattice points, and cantravel only to the east or north. (A lattice point is a point whose coordinates are bothintegers.) (0 , 0) is the southwest corner of the field. (5 , 5) is the northeast corner ofthe 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 theseconstraints?
    Solution: 32
    In the figure, each point is labeled with the number of ways to reach that point. Thenumbers are successively computed as follows: The point (0 , 0) can trivially be reachedin 1 way. When Bessie reaches any subsequent point ( x, y ) (other than a rock), shecan arrive either via a northward or an eastward step, so the number of ways she canreach that point equals the number of ways of reaching ( x − 1 , y ) plus the number ofways 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