Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Uncovering Squares with Odd Coordinates

Date: 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/ 
Associated Topics:
College Discrete Math

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/