Mathematics desk
< December 31	<< Dec \| January \| Feb >>	January 2 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 1

Graph Theory

I was solving problems from a Graph theory text book and came across this problem: (1) Prove that removing opposite corner squares from an 8 by 8 checkerboard leaves a subboard that cannot be partitioned into 1 by 2 and 2 by 1 rectangles. (I assume the problem asks for removing only 1 pair of corner squares). (2) Using the same argument, make a general statement about all bipartite graphs. Can someone help me with this please. Thanks -Shahab (talk) 14:29, 1 January 2011 (UTC)[reply]

Explicitly making this a question about a checkerboard (rather than an arbitrary 2n by 2n grid) actually makes it easier, since the checkerboard comes pre-equipped with a helpful colouring. Algebraist 14:33, 1 January 2011 (UTC)[reply]

I keep thinking of Ike somehow... --Stephan Schulz (talk) 14:42, 1 January 2011 (UTC)[reply]

You think he saw everything as black and white? ;-) Dmcq (talk) 15:22, 1 January 2011 (UTC)[reply]

To expand on Algebraist's comments:

1) Opposite corners come in the same color on an 8×8 checkerboard, and initially there are the same number of black squares as white (32 each).

2) Therefore, removing one opposite set leaves you with a color imbalance (30 white squares and 32 black or vice-versa).

3) Since removing a 1×2 rectangle will always remove both a black and a white square, that will maintain the color balance. So, after one rectangle is removed, a full checkerboard would have 31 black squares and 31 whites, for example.

4) If you do the math on removing 1×2 squares from a checkerboard with one pair of opposite corners removed, you find you eventualy end up with only two black squares or two whites, which can't posibly form a rectangle, due to the way the board is laid out.

OK, so how do we generalize this ?

A) The general rule appears to be that you can't remove balanced color rectangles (or squares) from a larger imbalanced-color square (or rectangle), and end up with nothing.

B) Note that this doesn't necessarily mean that you always can remove balanced color rectangles (or squares) from a larger balanced-color square (or rectangle), such as removing 6×1 rectangles from a chessboard. At a minimum, the larger product must be a multiple of the smaller product. So, in our example, the 62 squares we had left did divide evenly by the 2 squares we removed at a time, while it would not divide evenly by the 6 squares in a 6×1 removal scheme. Of course, being a multiple, alone, isn't sufficient to ensure that the configuration allows them to be removed exactly. There's the color imbalance issue, but also the problem of physically fitting the removal patches on the board so they don't overlap or fall off an edge.

C) Think of which rectangular or square boards have opposite corners the same color (it helps to have a checkerboard in front of you when you do this, so here's one: chessboard). Now, can you come up with a formula to describe the relationship between the X and Y directions that gives you opposite corners the same color ? Hint: It's more complex than just X=Y.

D) Similarly, think of squares or rectangles that can be removed which have "balanced color". Is there any square or rectangle that has more blacks than white or vice-versa ? (And, if so, is it always imbalanced in the same direction, or not ?).

StuRat (talk) 16:11, 1 January 2011 (UTC)[reply]