HMMT 十一月 2024 · 冲刺赛 · 第 30 题
HMMT November 2024 — Guts Round — Problem 30
题目详情
- [15] Compute the number of ways to shade exactly 4 distinct cells of a 4 × 4 grid such that no two shaded cells share one or more vertices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2024, November 09, 2024 — GUTS ROUND Organization Team Team ID#
解析
- [15] Compute the number of ways to shade exactly 4 distinct cells of a 4 × 4 grid such that no two shaded cells share one or more vertices. Proposed by: Jacob Paltrowitz Answer: 79 Solution: Assign coordinates to the cells of the grid so that the bottom-left, bottom-right, and top- right corners are (0 , 0), (3 , 0), and (3 , 3) respectively. Observe that for each quadrant of the grid, all four cells of that quadrant share a vertex. Thus, any valid coloring must have exactly one shaded cell in each quadrant. Let A = ( a , a ), B = ( b , b ), 1 2 1 2 C = ( c , c ) and D = ( d , d ) denote the shaded cells in the bottom-left, bottom-right, top-left, and 1 2 1 2 top-right quadrants, respectively, so that 0 ≤ a , a , b , c ≤ 1 and 2 ≤ b , c , d , d ≤ 3. 1 2 2 1 1 2 1 2 Observe that A and B share a vertex if and only if | b − a | ≤ 1 and | b − a | ≤ 1. The latter is always 1 1 2 2 true, and the former holds precisely when a = 1 and b = 2. We conclude that in a valid coloring, 1 1 ( a , b ) must be one of (0 , 2), (0 , 3), or (1 , 3). We can similarly deduce the same holds for ( c , d ), 1 1 1 1 ( a , c ), and ( b , d ). 2 2 2 2 Suppose the coordinates are chosen according to those constraints. Then, we are guaranteed the pairs of cells ( A, B ), ( C, D ), ( A, C ), and ( B, D ) do not share any vertices. The only way we get an invalid coloring is if A and D share a vertex, or B and C share a vertex. C D C D A B A B 3 3 C C C C 2 D D 2 D D 1 1 A A 0 0 A B A B B B 0 1 2 3 0 1 2 3 Suppose A and D share a vertex. Then we must have a = a = 1 and d = d = 2, which implies 1 2 1 2 b = c = 3 and b = c = 0. Thus, there is exactly one way to choose coordinates in the manner above 1 2 2 1 so that A and D share a vertex (as depicted in the figure on the right). Likewise, there is exactly one way for B and C to share a vertex. 4 There are 3 = 81 ways to choose the coordinates, so the answer is 81 − 2 = 79 .