HMMT 二月 2016 · COMB 赛 · 第 4 题

HMMT February 2016 — COMB Round — Problem 4

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?

解析

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 Answer: 81 We break this into cases. First, if the middle edge is not included, then there are 6 ∗ 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.