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 connecting all these 2 n points, starting from the bottom left corner and ending at the upper right corner. Such a 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 connecting all these 2 n points, starting from the bottom left corner and ending at the upper right corner. Such a 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.