PUMaC 2015 · 组合（B 组） · 第 8 题
PUMaC 2015 — Combinatorics (Division B) — Problem 8
题目详情
- [ 8 ] In how many ways can 9 cells of a 6-by-6 grid be painted black such that no two black cells share a corner or an edge with each other? 1
解析
- [ 8 ] In how many ways can 9 cells of a 6-by-6 grid be painted black such that no two black cells share a corner or an edge with each other? Solution: Clearly, each 2-by-2 subgrid can only contain one black cell, as otherwise, two black cells in the same 2-by-2 subgrid must share the center corner. We then split the grid into 9 2-by-2 subgrids with corners (2 a, 2 b ) , (2 a + 2 , 2 b ) , (2 a, 2 b + 2) , (2 a + 2 , 2 b + 2) for a, b ∈ { 0 , 1 , 2 } . Thus, each subgrid must contain exactly one black cell. The placement of each black cell in each 2-by-2 subgrid can be determined by two parameters: left or right and top or bottom. If subgrid ( a, b ) is right, then ( a + 1 , b ) must be right also, and 3 if ( a, b ) is left, then ( a − 1 , b ) must be left also, and similarly for the top/bottom parameters. Then, looking at the first right subgrid in a row and first bottom subgrid in a column, there 2 · 3 are (3 + 1) = 4096 potential placements of black cells. However, not all these placements satisfy the conditions, as two black cells in diagonally- adjacent subgrids can share a corner. If the corner (2 , 2) is shared, then there are (1 · 2 · 4) · 2 (1 · 2 · 4) = 8 placements where the top left and bottom right cells of the corner are black and 2 (2 · 1 · 4) · (2 · 1 · 4) = 8 where the top right and bottom left cells of the corner are black, giving a total of 128 invalid placements. Similarly, counting invalid placements where the corners (2 , 4) , (4 , 2) , (4 , 4) are shared, we count a total of 512 invalid placements. This overcounts a few invalid placements; namely, those where corners (2 , 4) and (4 , 2) or (2 , 2) and (4 , 4) are shared. For each of these pairs, there are 2 possible orientations (top left and 2 bottom right v. top right and bottom left) and 2 ways to place the rest of the black cells, giving a total of 16 overcounted invalid placements. By PIE, the total number of valid placements is then 4096 − 512 + 16 = 3600 . Author: Bill Huang 4