HMMT 十一月 2008 · GEN2 赛 · 第 5 题
HMMT November 2008 — GEN2 Round — Problem 5
题目详情
- [ 7 ] Suppose that at some point Joe B. has placed 2 black knights on the original board, but gets bored of chess. He now decides to cover the 34 remaining squares with 17 dominos so that no two overlap and the dominos cover the entire rest of the board. For how many initial arrangements of the two pieces is this possible? 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 pieces move 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 a row. • 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 . 1
解析
- [ 7 ] Suppose that at some point Joe B. has placed 2 black knights on the original board, but gets bored of chess. He now decides to cover the 34 remaining squares with 17 dominos so that no two overlap and the dominos cover the entire rest of the board. For how many initial arrangements of the two pieces is this possible? Answer: 324 Color the squares of the board red and blue in a checkerboard pattern, and observe that any domino will cover exactly one red square and one blue square. Therefore, if the two knights cover squares of the same color, this is impossible. We now claim that it is always possible if they 2 cover squares of opposite colors, which will give an answer of 18 = 324. Consider the rectangle R with the knights at its corners. Because the knights cover differently colored squares, R must have one side length odd and one side length even. Therefore, the 4 lines bounding R cut the original board into R and 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 pieces move 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 a row. • 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