Track / Stage 4 / 99 of 340 #839 of 2444

Problem 839

AMC 12 late, AIME early

Combinatorics Difficulty 4.6 Find the answer HMMT February · United States

Consider a $2 \times n$ grid of points and a path consisting of $2n-1$ straight line segments connecting all these $2n$ 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$ ?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

Solution:

The general answer is $\binom{2(n-1)}{n-1}$ : Simply note that the points in each column must be taken in order, and anything satisfying this avoids intersections, so just choose the steps during which to be in the first column.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.