HMMT 二月 2016 · 冲刺赛 · 第 6 题
HMMT February 2016 — Guts Round — Problem 6
题目详情
英文原题
- [ 6 ] Consider a 2 × n grid of points and a path consisting of 2 n − 1 straight line segments connectingall these 2 n points, starting from the bottom left corner and ending at the upper right corner. Sucha path is called efficient if each point is only passed through once and no two line segments intersect.
How many efficient paths are there when n = 2016?
解析
英文解析
- [ 6 ] Consider a 2 × n grid of points and a path consisting of 2 n − 1 straight line segments connectingall these 2 n points, starting from the bottom left corner and ending at the upper right corner. Sucha path is called efficient if each point is only passed through once and no two line segments intersect.
How many efficient paths are there when n = 2016?
Proposed by: Casey Fu
( )
4030
Answer:
2015
( )
2( n − 1)
The general answer is : Simply note that the points in each column must be taken in order,
n − 1
and anything satisfying this avoids intersections, so just choose the steps during which to be in the first column.