HMMT 二月 2023 · 冲刺赛 · 第 19 题
HMMT February 2023 — Guts Round — Problem 19
题目详情
- [16] Compute the number of ways to select 99 cells of a 19 × 19 square grid such that no two selected cells share an edge or vertex.
解析
- [16] Compute the number of ways to select 99 cells of a 19 × 19 square grid such that no two selected cells share an edge or vertex. Proposed by: Sean Li Answer: 1000 2 Solution: We claim the number of ways to select n − 1 such cells from a (2 n − 1) × (2 n − 1) grid is 3 exactly n , which implies the answer to this question is 1000. 2 Partition the board into n regions, as pictured. Also, shade red every cell in an odd row and column 2 red, so there are n red cells. Say a region is blank if it has no selected cell; normal if the selected cell is red; up-wack if the selected cell is above the red cell; and right-wack if the selected cell is to the right of the red cell. Note a 2 × 2 region could be both up-wack and right-wack. The key idea is that we have at most one blank region, which restricts things significantly. We have two cases: 2 • Case 1: no wack regions. Then we pick a region to be blank, of which we have n choices. • Case 2: some wack region. Note that (1) any region directly above an up-wack region must be either blank or up-wack; and (2) any region directly to the right of a right-wack region must be either blank or right-wack. In particular, there is at most one wack region (and we cannot have any up-wack and right-wack regions), since every wack region corresponds to at least one blank region. Suppose some region is up-wack. There are n columns that could contain this up-wack region, ( ) n +1 and ways to pick an up-wack region and, optionally, a blank region above it. Similarly, 2 ( ) ( ) n +1 n +1 there are n cases if there is some up-wack region, for a total of 2 n choices. 2 2 ( ) n +1 2 3 In total, we have n + 2 n = n possibilities, as desired. 2