HMMT 十一月 2024 · THM 赛 · 第 9 题
HMMT November 2024 — THM Round — Problem 9
题目详情
- Compute the number of ways to color each cell of an 18 × 18 square grid either ruby or sapphire such that each contiguous 3 × 3 subgrid has exactly 1 ruby cell. B C
解析
- Compute the number of ways to color each cell of an 18 × 18 square grid either ruby or sapphire such that each contiguous 3 × 3 subgrid has exactly 1 ruby cell. Proposed by: Jacob Paltrowitz Answer: 4365 Solution: Subdivide the grid into 36 subgrids of size 3 × 3. Each contains exactly one ruby cell. Consider four adjacent subgrids A B C D and the relative positions of the ruby cells within their respective 3 × 3 subgrids. Between A and C , we can check that the ruby cells differ by only a horizontal shift. Likewise, between A and B , the ruby cells differ by only a vertical shift. A B ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ C D The black star indicates the ruby in A , and the white stars indicate potential locations for rubies in B, C . It can further be checked that the shift between A, B is the same as between C, D , and likewise between A, C and B, D . Also, it cannot be the case that both a horizontal and a vertical shift is present, as some 3 × 3 subgrid will have an invalid number of ruby cells: A B A B ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ C D C D Now, in the original grid A B · · · C D · · · . . . . . . . . . we conclude that between each of the 5 pairs of adjacent columns of subgrids, there is some constant vertical shift, and that between each of the 5 pairs of adjacent rows of subgrids, there is some constant horizontal shift. However, if there exists both a pair of columns ( x , x ) with a nontrivial vertical shift 1 2 and also a pair of rows ( y , y ) with a nontrivial horizontal shift, the four subgrids at their intersection 1 2 ( x , x ) × ( y , y ) would violate our reasoning above. Hence, there are either only vertical shifts, only 1 2 1 2 horizontal shifts, or neither. Equivalently, all rubies are contained within either six equally spaced rows or six equally spaced columns. It can be checked that all such configurations are valid. To count the number of ways to place all rubies into six equally spaced rows, we have 3 choices for 7 which rows to choose, and 3 choices within each row for where the rubies are located. This gives 3 . 7 Symmetrically, there are 3 ways to place all rubies into six equally spaced columns. To adjust for overcounting, we note that there are 9 possibilities where all rubies are contained in six rows and six columns. The answer is 7 2 · 3 − 9 = 4365 . For completeness, examples of each of the three cases (no shifts, horizontal shifts only, vertical shifts only) is shown below. ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ No shifts Vertical shifts only ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ Horizontal shifts only