Let be the rectangle in the Cartesian plane with vertices at , and . 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?
Solution
We break this into cases. First, if the middle edge is not included, then there are 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 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.