PUMaC 2008 · 组合（B 组） · 第 4 题
PUMaC 2008 — Combinatorics (Division B) — Problem 4
题目详情
- (3 points) A 2008 × 2009 rectangle is divided into unit squares. In how many ways can you remove a pair of squares such that the remainder can be covered with 1 × 2 dominoes?
解析
- A 2008 × 2009 rectangle is divided into unit squares. In how many ways can you remove a pair of squares such that the remainder can be covered with 1 × 2 dominoes? ( ) 2 2008 × 2009 ( ANS: , if you color the rectangle’s squares so that every white square only borders 2 black squares and vise-versa, you see that the two removed squares have to be on different colors. If they’re of different colors: Color the board like a checkerboard. It is clear that a domino covers one black square and one red, so the two pieces removed must be different colors. An m x 1 rectangle can be filled in by dominoes if m is even. Therefore an m by n rectangle can be filled in with dominoes if mn is even, by giving all dominoes the same orientation. Start with this tiling. Without loss of generality, say that the number of rows is even and that the dominoes are laid down 2 units tall and one unit wide. Given a path from one of the removed squares to the other, such that the path never crosses itself, and the first square of any domino in the path is consecutive with the second, we can create a new tiling. If the removed spaces are at different heights but on dominoes of the same height, then they are opposite corners of a 2 x odd rectangle, which with the two corners removed becomes two 1 x even rectangles, and the old tiling is easy to replace. If the removed tiles are at the same height, 1 Combinatorics then the two affected dominos and those in between now form two 1 x even rectangles and can be trivially filled in. Two spaces removed in the same column can be removed and the rest filled in with all vertical dominoes or two horizontal ones in that column and an adjacent column. Now, if the two affected dominoes are not on the same column or pair of rows, we can reduce to a few cases: Case 1: The removed spaces differ by an even number of rows. Then, WLOG, say both of the removed spaces are top halves of the dominoes of the original tiling, and we have a path moving down from the higher spot to the lower column and snakewise horizontally to the other. Case 2: They differ by an odd number of rows, and the higher domino is in the top half of its cell. Then a path exists by moving within the column from the lower domino to the height of higher one and then snakewise horizontally. Case 3: They differ by an even number of rows, and the higher domino is in the bottom half of its cell. Then shift horizontally one column from the remaining space of the affected domino in the direction of the other removed space, we have reduced to case 1. CB: AL12, IAF)