HMMT 十一月 2024 · 冲刺赛 · 第 17 题

HMMT November 2024 — Guts Round — Problem 17

[10] Compute the number of ways to shade in some subset of the 16 cells in a 4 × 4 grid such that each of the 25 vertices of the grid is a corner of at least one shaded cell.

解析

[10] Compute the number of ways to shade in some subset of the 16 cells in a 4 × 4 grid such that each of the 25 vertices of the grid is a corner of at least one shaded cell. Proposed by: Linus Yifeng Tang Answer: 1215 Solution: 3 ways 15 ways 3 ways 3 ways 3 ways Observe that every corner cell must be shaded, as they are the only cells incident to the four corners of the grid. Furthermore, for each side of the grid, the midpoint of that side is incident to exactly two cells; at least one must be shaded. Finally, at least one of the four central cells must be shaded to hit the central vertex of the grid. We claim these conditions are also sufficient for a valid coloring. Let us give the points of the grid coordinates from (0 , 0) to (4 , 4). Then, the corner cells cover every vertex except for those of the form (2 , x ) or ( x, 2) for 0 ≤ x ≤ 4. Whichever cell covers (2 , 0) must also cover (2 , 1), and likewise the cells covering (0 , 2), (2 , 4), and (4 , 2) cover (1 , 2), (2 , 3), and (3 , 2) respectively. This leaves the center (2 , 2), which is also covered by assumption. Observe that for each side of the grid, of the two cells incident to its midpoint, there are 3 ways to 4 color at least one of them. Of the 4 central cells, there are 2 − 1 = 15 ways to color at least one. 4 Thus, the number of colorings is 3 · 15 = 1215 .