Uncovering Squares with Odd CoordinatesDate: 12/24/2003 at 10:35:29 From: Danny Subject: The (2n + 1) x (2n + 1) chessboard covered by dominoes How is it possible to prove the following? Let a chessboard with dimensions (2k + 1) x (2k + 1) be covered by dominoes, where each domino covers 2 cells joined by a common edge), such that one of the four corner cells is uncovered. By sliding dominoes around, we can uncover any cell whose coordinates are both odd, regardless of the initial layout of the dominoes. Date: 12/26/2003 at 05:19:12 From: Doctor Jacques Subject: Re: The (2n + 1) x (2n + 1) chessboard covered by dominoes Hi Danny, I understand that you want to slide dominoes until the empty square is located on a pre-assigned square with odd coordinates. To make things shorter, let us call "red" the squares with both coordinates odd, and "green" the other squares. We will also draw arrows on the board between adjacent red squares. Each (red) square, except the empty one in a corner, is covered by exactly one domino, and we draw an arrow from that square to the square just after the other square of the domino. For example, if we have three squares A,B,C, with A and C red, like this: A B C and the domino covering A is in position (AB), we draw and arrow from A to C. Each non-empty red square will have exactly one arrow emanating from it. Assume that we are given a target square, and we want to know how to get there. We could try to solve the problem in reverse. For example, with the above square, if we can get to C without disturbing the domino AB, we can get to A at the next move by sliding AB to the right. This means that we would get to A via C, and the arrow A->C means that C should come just before A in the path. We can then start from A and draw a path by following the arrows. As there is only one arrow starting from each non-empty red square, there is only one way to do this. Now, two things can happen: (1) We end up in the empty square. (2) We come back to a previously visited square, and, from that point on, the path cycles forever. In case (1) we can follow the arrows in reverse, starting from the empty square, and this will lead us to the target square. Note that, since the path does not cross itself, every domino on the path will be moved once. So, if we are in case (1), the square is reachable. If there is an unreachable red square, it means that the above procedure must fail, i.e., we must be in case (2). This means that there is a closed path in the patterns of arrows. We must show that this is not possible. Let us assume that such a closed path exists. This path forms a polygon on the board, and the vertices of that polygon are on red squares. For the lack of a better word, let us define a "special polygon" as a polygon that satisfies the following conditions: * The sides are either horizontal or vertical * The vertices are on the centers of red squares Note that a closed arrow path is a particular case of a special polygon. We consider that the squares covered by the edges are part of the polygon, and we want to show that the area (the number of board squares) of such a polygon is odd. This may seem obvious, but we must still be careful, since the polygon can have odd shapes like this: +--+ +--+ | | | | | | | | + +--+ + | | +--+--+--+ We proceed by induction on the area of the polygon. The smallest possible special polygon is a 3*3 square, and its area is odd. Assume that P is a special polygon with even area and has the smallest possible area. As P is greater than 3 by 3, we can draw a horizontal or vertical line, starting and ending in red squares, that divides P into two parts Q and R. Note that that line covers an odd number of squares, since both ends are red squares. As Q and R are smaller than P, their area is odd, by the induction hypothesis. Now, the area of P is equal to: (area of Q) + (area of R) - (area of line) and this is odd, which leads to a contradiction. The conclusion is that all special polygons have an odd area. If we consider now the special polygon defined by a closed arrow path, we note that the perimeter is completely covered by dominoes (because of the ways arrows are defined). Therefore the perimeter covers an even area, and the area of the inside is odd. As the perimeter is covered by dominoes, no domino in the inside area can have a square on the perimeter--such dominoes are wholly contained in the inside area, and, obviously, they cover an even area. The conclusion is that the emtpy square must be inside the polygon, which contradicts the fact that the empty square is in a corner. This means that no closed arrow path exists, and the procedure described above will always end in case (1)--by using that procedure, we can effectively find a way to move the empty square to any given red square. We have also shown that we can do this without moving any domino more than once. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/