HMMT 十一月 2024 · 团队赛 · 第 7 题
HMMT November 2024 — Team Round — Problem 7
题目详情
- [50] A weird checkerboard is a coloring of an 8 × 8 grid constructed by making some (possibly none or all) of the following 14 cuts: • the 7 vertical cuts along a gridline through the entire height of the board, • and the 7 horizontal cuts along a gridline through the entire width of the board. The divided rectangles are then colored black and white such that the bot- tom left corner of the grid is black, and no two rectangles adjacent by an edge share a color. Compute the number of weird checkerboards that have an equal amount of area colored black and white.
解析
- [50] A weird checkerboard is a coloring of an 8 × 8 grid constructed by making some (possibly none or all) of the following 14 cuts: • the 7 vertical cuts along a gridline through the entire height of the board, • and the 7 horizontal cuts along a gridline through the entire width of the board. The divided rectangles are then colored black and white such that the bottom left corner of the grid is black, and no two rectangles adjacent by an edge share a color. Compute the number of weird checkerboards that have an equal amount of area colored black and white. Proposed by: Sebastian Attlan Answer: 7735 Solution: We can focus on only the black cells of the grid, which we need 32 of. Moreover, the number of black squares in the bottom row and leftmost column uniquely determine the total number of black squares. Suppose that there are x black cells in the bottom row and y black cells in the leftmost column. Then, each of the x rows with black leftmost cell is identical to the bottom row and has y black cells, while the remaining 8 − x rows are inverted and have 8 − y black cells, so the total number of black cells is (8 − x )(8 − y ) + xy = 32 . This rearranges as 2( x − 4)( y − 4) = 0 , which tells us we have 32 black cells exactly when either the bottom row or leftmost column (or both) contains 4 black cells. 7 The bottom-left corner is already black. There are ways to choose three more cells in the bottom 3 7 row or leftmost column to be black, and 2 ways to color the remaining cells in the bottom row or 7 7 leftmost column with no restrictions. Hence, there are 2 ways for the bottom row to have 4 black 3 2 7 7 7 cells, 2 ways for the leftmost column to have 4 black cells, and ways for both to occur. The 3 3 answer is 2 7 7 7 2(2 ) − = 7735 . 3 3