HMMT 二月 2018 · COMB 赛 · 第 4 题
HMMT February 2018 — COMB Round — Problem 4
题目详情
- How many ways are there for Nick to travel from (0 , 0) to (16 , 16) in the coordinate plane by moving one unit in the positive x or y direction at a time, such that Nick changes direction an odd number of times?
解析
- How many ways are there for Nick to travel from (0 , 0) to (16 , 16) in the coordinate plane by moving one unit in the positive x or y direction at a time, such that Nick changes direction an odd number of times? Proposed by: Huaiyu Wu ( ) 30 Answer: 2 · = 310235040 15 This condition is equivalent to the first and last step being in different directions, as if you switch directions an odd number of times, you must end in a different direction than you started. If the first step is in the x direction and the last step is in the y direction, it suffices to count the number of paths ( ) 30 from (1 , 0) to (16 , 15), of which there are . Similarly, in the other case, it suffices to count the 15 ( ) 30 number of paths from (0 , 1) to (15 , 16), of which there are also . Therefore the total number of 15 ( ) 30 paths is 2 · . 15