HMMT 二月 2016 · COMB 赛 · 第 4 题

英文解析

4. Let R be the rectangle in the Cartesian plane with vertices at (0 , 0) , (2 , 0) , (2 , 1) , and (0 , 1). R can bedivided 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 tochoose two distinct points for the figure to begin and end at. We could also allow the figure to includeall 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 consistingof only the edge parallel to the middle edge since it’s not connected). Similarly, of the three edges tothe right of the middle edge, there are 7 possible subsets we can include. In total, there are 49 possibleconnected figures that include the middle edge. Therefore, there are 32 + 49 = 81 possible connectedfigures.