2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner?

2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner. A domino which borders the hole along its short side may be slid one unit along its long side to cover the hole and open a new hole.



Show that the hole may be moved to any other corner by moves of this type?2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner?
the dominoes seems to be arranged spirally. that way. you can always move the outer parts anywhere, thus moving the hole to any corner2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner?
Keep moving all the dominoes in the same direction until it hits another corner then move the domino around the corner....

like so



#############

#############

#############

############

then to this



#############

#############

############

#############

then to this



#############

############

#############

#############

then to this



############

#############

#############

#############

Now its in another corner. To move it laterally, same principle
The dominoes occupy an even number of spaces, and since there is a single space unoccupied, there must be an odd number of total spaces. i.e. n and m are both odd. Since the hole can jump 2 spaces at a time, it can occupy a set of spaces (ri, ci) where ri and ci are both odd.

************



As long as there is a connected network of horizontal dominoes in odd numbered rows and vertical dominoes in odd numbered columns, then the hole can propagate through the rectangle along that network. We need to prove that this connected network exists and that it connects all the corners.



Let鈥檚 suppose that at any moment, the hole is at (ri,ci), where of course ri and rj are odd. The hole will NOT be able to propagate if one of the following occurs:

1)in row ri, all the vertical dominoes are in even numbered columns

2)in column ci all the horizontal dominoes are in even numbered rows



If case 1 were true, then between adjacent vertical dominoes, there would be an odd number of horizontal spaces, which means that all dominoes in between cannot be horizontal. There must be a vertical domino in an odd numbered column. So case 1 cannot occur, and by similar reasoning case 2 cannot occur. It follows that in any row (column), adjacent vertical (horizontal) dominoes cannot be on columns (rows) with the same odd/even parity.



In the row with the hole, an even number of dominoes must be vertical. In rows not containing the hole, an odd number of dominoes must be vertical (the first and last must be on odd numbered columns). Since the hole starts on a boundary row (row 1), row 1 must contain an even number of vertical dominoes all connecting to row 2. But row 2 must have an odd number of vertical dominoes, hence row 2 has an odd number of vertical dominoes connecting to row 3. We鈥檝e shown above that in a given row, adjacent verticals cannot be on columns with the same parity (otherwise horizontal dominoes will not be able to fit in between them). So there must be some vertical dominoes connecting row 2 and row 3 via an odd numbered column. The same arguments hold for the columns.

***********



Now let鈥檚 start with the hole in position (1,1). There must be an initial movement out of (1,1) vertically and/or horizontally. Let鈥檚 suppose the initial movement is horizontal along the row. If row 1 has no vertical dominoes, then it easily hops to corner (1,m). If row 1 has a non-zero even number of vertical dominoes, the first one must be on an even numbered column, 2k (connecting to row 2). This vertical domino actually blocks the hole at the column, 2k-1. So at this point the hole must find a vertical domino in row 2 connecting to row 3. Since there are an odd number of spaces from column 1 to column 2k-1, and since row 2 cannot have consecutive vertical dominoes on even columns, row 2 must have a vertical domino in an odd numbered column (鈮?2k-1) connecting to row 3. Thus the hole has a connected path from row 1 to row 3. Again the same arguments hold with the columns if the initial movement were vertical.



So far we鈥檝e shown that the hole can jump from the corner (1,1) to some internal space (ri,ci). It goes without saying that the hole can always jump back to the original corner. So at any allowable position (ri,ci), the hole has a connected path back to the original corner.



I still have to show that (ri,ci) is connected to the other corners.

************



Let's suppose the space (r1, c1) does not contain the hole. Then (r1, c1) has half a domino on it, which means it is accessible along the axis of the domino from an adjacent odd space (r2, c2). Similarly (r2, c2) is accessible via (r3, c3) and so on.



Let's suppose this progression forms a connected network (ri, ci). As long as all the (ri, ci) are unique, then every space on an odd numbered row and column will be accessible to the hole.



Now suppose the (ri, ci) are not all unique, i.e. the network loops back onto itself. But to arrange the dominoes in such a manner, there will be an odd number of spaces enclosed in the loop. An integral number of dominoes cannot fit in the enclosure, thus the hole must be trapped inside that enclosure.



But we already know that the hole is connected to the original corner, which means that the hole cannot be trapped inside any enclosure. Thus as long as the hole is connected to one corner, there can be no looped network, and hence the hole will be able to access every odd numbered (ri, ci) including all four corners.2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner?
Assume a rectangle is m spaces high by n spaces wide.



If there is a hole, both m and n must be odd numbers (or there would not be a hole)



Where ever the hole is, it can be transported to the adjacent corner by moving an entire row or column.



By repeating this two times, you can transport the hole to the opposite corner.
all i understand is the hole can move to the same color of checkered / chess board. since m and n are both odd (the only way a hole is to happen), all corners are on the same color.2x1 dominoes are used to tile an m x n rectangle, except for a single 1x1 hole at a corner?
Alternate phrasing would be there is at least one path connecting all of the other corners where the only way to travel is going along the long direction of the dominoes.



*This is the path you will travel. Each time you slide a piece, it will slide the long way. If you can create this path, you can get to that square.



As Dr. D pointed out, both M and N are odd.



Start at (1,1). When you move to fill an empty square by sliding a domino, the new open square will be another double odd number, say (1,3). Because you can only advance by "2s", all free squares must be a double odd number.



Further, because M and N are both odd, there will be at least one domino in column (2,-) that is oriented such that it spans column (2, x) and (3, x) where "x" is an odd number, and the domino and is connected to a straight path on column 1 to the free space. (The space 3,x) will end up being the next free space)



Repeating, you can show that you can make a path to advance to any double odd space. (Note: You may have to back track, i.e., go back to a previous column, but there will be a path)



Beats being a mouse and trying to eat a cake square by square.



%26gt;%26gt;%26gt;%26gt; Edit %26gt;%26gt;%26gt;%26gt;%26gt;



How is your greek mythology? Do you remember the monster Minotuar, slain by Theseus after he negotiated the labyrnith?



Will to negotiate the maze, Theseus always turned right. You can negotiate any simple maze by always following the right (or left) hand wall. If you come to a dead end, you will be forced to turn around, an you will find a new path on the right.



Here, you can make just such a path, and it will hit every odd, odd point in the rectangle before coming back to your starting point.