HMMT 二月 2021 · COMB 赛 · 第 9 题
HMMT February 2021 — COMB Round — Problem 9
题目详情
- An up-right path between two lattice points P and Q is a path from P to Q that takes steps of length 1 unit either up or to the right. How many up-right paths from (0 , 0) to (7 , 7) , when drawn in the plane with the line y = x − 2 . 021 , enclose exactly one bounded region below that line?
解析
- An up-right path between two lattice points P and Q is a path from P to Q that takes steps of length 1 unit either up or to the right. How many up-right paths from (0 , 0) to (7 , 7) , when drawn in the plane with the line y = x − 2 . 021 , enclose exactly one bounded region below that line? Proposed by: Anders Olsen Answer: 637 Solution: We will make use of a sort of bijection which is typically used to prove the closed form 1 for the Catalan numbers. We will count these paths with complementary counting. Since both the starting and ending points are above the line x − 2 . 021 , any path which traverses below this line (and hence includes a point on the line y = x − 3) will enclose at least one region. In any such path, we can reflect the portion of the path after the first visit to the line y = x − 3 over that line to get a path from (0 , 0) to (10 , 4) . This process is reversible for any path to (10 , 4) , so the number of paths enclosing at ( ) 14 least one region is . 4 More difficult is to count the paths that enclose at least two regions. For any such path, consider the first and final times it intersects the line y = x − 3 . Since at least two regions are enclosed, there must be some point on the intermediate portion of the path on the line y = x − 2 . Then we can reflect only this portion of the path over the line y = x − 3 to get a new path containing a point on the line y = x − 4 . We can then do a similar reflection starting from the first such point to get a path from (0 , 0) to (11 , 3) . This process is reversible, so the number of paths which enclose at least two regions is ( ) ( ) ( ) 14 14 14 . Then the desired answer is just − = 637 . 3 4 3