HMMT 二月 2021 · COMB 赛 · 第 8 题
HMMT February 2021 — COMB Round — Problem 8
题目详情
- Compute the number of ways to fill each cell in a 8 × 8 square grid with one of the letters H, M, or T such that every 2 × 2 square in the grid contains the letters H, M, M, T in some order.
解析
- Compute the number of ways to fill each cell in a 8 × 8 square grid with one of the letters H, M, or T such that every 2 × 2 square in the grid contains the letters H, M, M, T in some order. Proposed by: Sheldon Kieren Tan Answer: 1076 Solution: We solve the problem for general n × n boards where n even. Let the cell in the i -th row and j -th column be a . i,j Claim: In any valid configuration, either the rows (or columns) alternate between ( · · · , H, M, H, M, · · · ) and ( · · · , T, M, T, M, · · · ) or ( · · · , M, M, M, M, · · · ) and ( · · · , H, T, H, T, · · · ). Proof: First note that all configurations which follow the above criteria are valid. If the rows alternate as above we are done. Else there exists one of the below configurations in one of the rows, from which we can deduce the rest of the 3 columns as follows: ( a , a , a ) ( a , a , a ) ( a , a , a ) i,j − 1 i,j i,j +1 i +1 ,j − 1 i +1 ,j i +1 ,j +1 i +2 ,j − 1 i +2 ,j i +2 ,j +1 ( H, M, T ) ( T, M, H ) ( H, M, T ) ( T, M, H ) ( H, M, T ) ( T, M, H ) ( H, T, M ) ( M, M, H ) ( H, T, M ) ( M, T, H ) ( H, M, M ) ( M, T, H ) ( T, H, M ) ( M, M, T ) ( T, H, M ) ( M, H, T ) ( T, M, M ) ( M, H, T ) ( T, M, M ) ( M, H, T ) ( T, M, M ) ( M, M, T ) ( T, H, M ) ( M, M, T ) ( H, M, M ) ( M, T, H ) ( H, M, M ) ( M, M, H ) ( H, T, M ) ( M, M, H ) It can be noted that the configurations alternate as we move down/up the columns, implying that the 3 columns consist of alternating letters (or ( M, M, · · · )). We can now check that all columns obey the above form, and in particular, must alternate as stated in the claim. It now suffices to count the number of cases. When the rows alternate between ( · · · , H, M, H, M, · · · ) and ( · · · , T, M, T, M, · · · ), there are 2 ways to choose which one occupies the odd-numbered rows, n and 2 ways to alternate between the 2 letters in each row. When the rows alternate between ( · · · , H, T, H, T, · · · ) and ( · · · , M, M, M, M, · · · ), there are 2 ways to choose which occupies the odd- n 2 numbered rows, and 2 ways to alternate between the 2 letters in the rows. The number of cases for columns is the same. Finally, if both the rows and columns alternate as above, it suffices to fix the first 2 rows (then the 2 rest of the board is uniquely determined by extending the columns). There are 2 × 2 = 8 ways to do this if the rows are ( · · · , H, M, H, M, · · · ) and ( · · · , T, M, T, M, · · · ), and 2 × 2 = 4 ways to do this if the rows are ( · · · , M, M, M, M, · · · ) and ( · · · , H, T, H, T, · · · ). n n n +1 +1 n +2 +2 2 2 Hence the total number of configurations is 2(2 + 2 ) − 12 = 2 + 2 − 12.