HMMT 十一月 2008 · GEN2 赛 · 第 5 题

英文解析

5. [ 7 ] Suppose that at some point Joe B. has placed 2 black knights on the original board, but gets boredof chess. He now decides to cover the 34 remaining squares with 17 dominos so that no two overlapand the dominos cover the entire rest of the board. For how many initial arrangements of the twopieces is this possible?
   Answer: 324 Color the squares of the board red and blue in a checkerboard pattern, and observethat any domino will cover exactly one red square and one blue square. Therefore, if the two knightscover squares of the same color, this is impossible. We now claim that it is always possible if theycover squares of opposite colors, which will give an answer of 18 = 324. Consider the rectangle R with 2
   the knights at its corners. Because the knights cover differently colored squares, R must have one sidelength odd and one side length even. Therefore, the 4 lines bounding R cut the original board into Rand up to 8 other rectangles, which can be put together into rectangles with at least one side even.
   These rectangles can be tiled, and it is easy to see that R can be tiled, proving the claim.
   Note: Chess is a game played with pieces of two colors, black and white, that players can move between squares on a rectangular grid. Some of the piecesmove in the following ways:
   • Bishop: This piece can move any number of squares diagonally if there are no other pieces along its path.
   • Rook: This piece can move any number of squares either vertically or horizontally if there are no other pieces along its path.
   • Knight: This piece can move either two squares along a row and one square along a column or two squares along a column and one square along arow.
   • King: This piece can move to any open adjacent square (including diagonally).
   If a piece can move to a square occupied by a king of the opposite color, we say that it is checking the king.
   If a piece moves to a square occupied by another piece, this is called attacking . 2