Combinatorics: How many ways to cover the 2008 x 2009 rectangle with 1 x 2 dominoes after removal of 2 squares?

A 2008 x 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 x 2 dominoes?|||Holdm is right: the necessary and sufficient condition the remainder to be covered with 1x2 dominoes is the removed 2 squares to be of different colors (assuming a chessboard-like coloring). The necessity is obvious (each domino covers 1 black and 1 white squares), but I wouldn't say the sufficiency is that obvious.





Many years ago the American mathematician Ralph Gomory has proven that a standard 8x8 chessboard with any 2 different-colored squares removed, can be tiled with 31 dominoes. His proof is extremely elegant and goes also for a rectangle with at least one even-length side - the idea is to build "walls" in the rectangle, allowing to traverse it in a closed circuit - see the picture to get an idea how it can be done (rectangle 5x6):


http://farm7.static.flickr.com/6103/6280…





Now if any 2 different-colored squares are removed (red on the picture), the circuit breaks into 1 part (if the removed squares are adjacent) or into 2 (otherwise); each part beginning and ending with different-colored squares, now obviously being possible to be covered by dominoes. The same is true for a 2008x2009 rectangle - you can deduce how to build the walls.





Since any of the black 2008*2009/2 and any of the white 2008*2009/2 squares can be removed, the required number is 2008² * 2009²/4. You haven't specified whether some of the remainders are considered same, taking rotations and/or reflections into account, if that is the case, I'll leave the rest of the job to you as an easy exercise.





Did I earn a glass of Black %26amp; White for my answer?|||Imagine the circuit as a corridor with 2 obstacles, you are over the 1st and jump down. Begin walking - each step a square with right leg, left leg, right, left, etc. ending with left before the 2nd obstacle. Step over it, jump down and repeat right, left, etc. until returning to the start position.

Report Abuse

|||Each 2 consecutive steps = 1 domino, each uninterrupted sequence begins with right leg, ends with left, right?


Waiting for my drink!

Report Abuse

|||imagine that hte rectangle is marked like a chess board with alternating black and white squares. observe that any domino covers one black and one white square. a necessary and sufficient condition that the board can be covered with dominos is that the 2 squares removed are of different colors.


there are 1004 * 2009 squares of each color, so this squared is the number of ways.|||Which 2 squares are removed? From where?