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 movingone unit in the positive x or y direction at a time, such that Nick changes direction an odd number oftimes?
解析
英文解析
- How many ways are there for Nick to travel from (0 , 0) to (16 , 16) in the coordinate plane by movingone unit in the positive x or y direction at a time, such that Nick changes direction an odd number oftimes?
Proposed by: Huaiyu Wu
( )
Answer: 2 · = 31023504030
This condition is equivalent to the first and last step being in different directions, as if you switch 15
directions an odd number of times, you must end in a different direction than you started. If the firststep is in the x direction and the last step is in the y direction, it suffices to count the number of paths
( )
from (1 , 0) to (16 , 15), of which there are . Similarly, in the other case, it suffices to count the 30
( )15
number of paths from (0 , 1) to (15 , 16), of which there are also . Therefore the total number of 30
( )15
paths is 2 · .30
15