Chessboard

• December 3rd 2009, 06:45 AM
kirschplunder
Chessboard
Hey all,

I got to proof:
http://i45.tinypic.com/14dgj8h.png
I am sorry for not typing this with LaTeX formatting, the backslash on my computer does not work (neither on the keyboard nor copied :s)

I see that
(n+(x*2n))*(m+(y*2m) where x,y in N & n,m are odd always gives an odd answer (odd*odd=odd)
That odd number is an even number + 1; hence 2x + 1, where 2x always give a black and a white square, and the one remaining is the one in the corner (white one)

Also I see that from any n/m to the next n/m is a step of 2 squares (black AND white), so there is still one more white than black square (since the first one is white.

But I cannot write this in formal language; and I got to.. Any Idea?
• December 3rd 2009, 07:07 AM
lvleph
I think you could do a mapping where white squares are considered odd numbers and black squares are considered even numbers. Now you need to figure out how to count how many odd indices there are in a $n\times m$ matrix and then compare that to the number of even indices.

Base case is extremely easy since we can take $m=n=1$ and so the number indices altogether would be one. Thus there is 1 white square and 0 black squares, i.e., one more white than black.

Now assume there is one more white square than black squares for a $n \times m$ board. What happens when you add two more rows and two more columns? Remember the rows and columns must remain odd.
• December 3rd 2009, 07:38 AM
Unenlightened
This is by no means a proof by induction, and probably not even a mathematical proof, but I thought it an interesting question, so I've thrown my two cents in...

You have n rows and m columns, where both m and n are odd.
Allow me to use $n_i$ to represent which row, and $m_j$ to represent which column we are on.

If you remove the $n_n$ row, then you are left with an m x n-1 board.
This board can then be divided into m strips, of length n-1, where n-1 is an even number.
You can then further subdivide each of these strips into (n-1)/2 smaller strips containing one black tile and one white tile each. Therefore our m x n-1 board has the same number of black and white tiles.
So all we have to focus on now is our $n_n$strip which we discarded initially.

This row is of length m, which is odd. The end tiles are both white, as they are corner tiles. This strip can also be subdivided into smaller strips of one white tile and one black tile, but with one tile left over at the end. Since no matter which tile you start with, the tile at the end of the strip is going to be white, our left-over tile is white...

That's probably of no help, but I enjoyed thinking through it, so thank you for the problem :)
• December 3rd 2009, 10:16 AM
kirschplunder
I think that's a very interesting think you said, I'll get that on paper and take a look on it once I finished my meal :)

That proving by induction is necessary.. I know you can do it different but that's what they ask :(