PUMaC 2013 · 团队赛 · 第 2 题

PUMaC 2013 — Team Round — Problem 2

(Following question 1) Now instead consider an infinite strip of squares, labeled with the integers 0, 1, 2, ... in that order. You start at the square labeled 0. You want to end up at the square labeled 3. In how many ways can this be done in exactly 15 moves? 2

解析

(Following question 1) Now instead consider an infinite strip of squares, labeled with the integers 0, 1, 2, ... in that order. You start at the square labeled 0. You want to end up at the square labeled 3. In how many ways can this be done in exactly 15 moves? SOLUTION: One can directly observe that the question is equivalent to the following: Starting from (0 , 0) in the cartesian plane, one can move a unit up and right; In how many ways can we go to end up in (9 , 6), without crossing the line y = x ? This rephrasing rings the bell: Catalan. We can carefully construct an identical argument. ( ) 15 The number of ways to get from (0 , 0) to (9 , 6) is = 5005. 9 For the paths that cross y = x , consider the first moment they go ”above” y = x . They should be then on the line y = x + 1. Flip the rest of the path with respect to y = x + 1 → we have a path from (0 , 0) to (5 , 10). One can see that this mapping is bijective because an inverse map is well-defined: all paths from (0 , 0) to (5 , 10) cross y = x + 1 and we can flip the path from the point it first meets y = x + 1. Thus, (the number of paths that go above y = x ) = (number of paths from (0 , 0) to (5 , 10) = ( ) 15 = 3003. 5 Thus the answer is 5005 − 3003 = 2002. ANSWER: 2002 2