Competition problem — Combinatorics

Library / /23 of 1394

Combinatorics Difficulty 4.6 AIME Find the answer United States

Problem:

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.

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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