HMMT 二月 2025 · COMB 赛 · 第 6 题
HMMT February 2025 — COMB Round — Problem 6
题目详情
- Compute the number of ways to pick two rectangles in a 5 × 5 grid of squares such that the edges of the rectangles lie on the lines of the grid and the rectangles do not overlap at their interiors, edges, or vertices. The order in which the rectangles are chosen does not matter.
解析
- Compute the number of ways to pick two rectangles in a 5 × 5 grid of squares such that the edges of the rectangles lie on the lines of the grid and the rectangles do not overlap at their interiors, edges, or vertices. The order in which the rectangles are chosen does not matter. Proposed by: Jacob Paltrowitz Answer: 6300 Solution: A rectangle can be specified by two intervals, one specifying its horizontal extent ( x - coordinates of left and right sides) and one specifying its vertical extent ( y -coordinates of bottom and top sides). For the rectangles to not overlap, we need either the horizontal intervals or the vertical intervals to be disjoint (possibly both). First, we will count the number of ways for the horizontal intervals to be disjoint. Let these intervals be [ a, b ] and [ c, d ]. As the order of the rectangles does not matter, we can assume without loss of 6 generality that a < c , so a < b < c < d . Then there are choices for a , b , c , and d . There are no 4 2 6 restrictions on the vertical intervals, so the number of ways to choose them is . Thus, the total 2 2 6 6 number of pairs of rectangles for which the horizontal intervals are disjoint is . 4 2 By symmetry, the total number of pairs of rectangles for which the vertical intervals are disjoint is the same. It remains to count the number of ways for both the horizontal and vertical intervals to be disjoint. Again, let the horizontal intervals be [ a, b ] and [ c, d ], and let the vertical intervals be [ e, f ] 6 and [ g, h ]. We can assume a < b < c < d without loss of generality, so there are ways to choose the 4 horizontal intervals. However, the cases e < f < g < h and g < h < e < f are now distinct, so there 2 6 6 are 2 ways to choose the vertical intervals. Therefore, there are 2 pairs of rectangles for which 4 4 both the horizontal and vertical intervals are disjoint. Through inclusion-exclusion, we get the final answer of 2 2 6 6 6 2 · − 2 · = 6300 . 4 2 4