Library / /127 of 1394

, 2016

Combinatorics Difficulty 4.8 AIME Find the answer United States

Problem:
Let $R$ be the rectangle in the Cartesian plane with vertices at $(0,0)$ , $(2,0)$ , $(2,1)$ , and $(0,1)$ . $R$ can be divided into two unit squares, as shown; the resulting figure has seven edges.

How many subsets of these seven edges form a connected figure?
Proposed by: Joy Zheng

Your answer

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

Solution

Solution:
We break this into cases. First, if the middle edge is not included, then there are $6 \times 5 = 30$ ways to choose two distinct points for the figure to begin and end at. We could also allow the figure to include all or none of the six remaining edges, for a total of $32$ connected figures not including the middle edge.

Now let's assume we are including the middle edge. Of the three edges to the left of the middle edge, there are $7$ possible subsets we can include ( $8$ total subsets, but we subtract off the subset consisting of only the edge parallel to the middle edge since it's not connected). Similarly, of the three edges to the right of the middle edge, there are $7$ possible subsets we can include. In total, there are $49$ possible connected figures that include the middle edge.

Therefore, there are $32 + 49 = 81$ possible connected figures.

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.