The chess board problem

I'm going to copy the style of one of my best friends blog (http://mchouza.wordpress.com/). Today I bring to you a problem (not as difficult as the ones Mariano presents on his blog :-) ), it's the chess board problem (if it has another name sorry).

Imagine you have a chess board of 100 x 100 squares covered with 10000 black pawns. We play a game in which the only legal move is to change, in a single row or column, all the black pawns to white and all the withe to black. Is it possible in a finite number of moves to leave 1990 white paws on the board?

ok, think a few minutes before you continue :-).

This is the kind of problems that seems very difficult at the beginning but at the end we realize is quite simple.

From the statement we can deduce that the order in which the move are made is immaterial and the order of the selected rows and columns is also not important. So we can say that the selected columns and rows are the first ones. So we will have something like this:

So, the equation we need to solve is:

100 (R + C) -2 RC = 1990

Simple, right?. It’s is quite simple to see in that equation that is impossible to obtain an odd number of white pawns by this process. Further, it is now easy to generalize the problem, if the board is of side 2p and the required number of white pawns is 2n the equation is:

p(R + C) – RC = n

In order to solve this equation we revive certain memories of conics. We can remove the linear term from our equation by a change of the variable R = r + k and C = c + k

p(r + c + 2k) – (r + k)( c + k) = n

if k=p

rc = p.p – n

where

r = R- p and c = C - p

For out example we have p=50 and n=1990/2

So we have,

50 x 50 – 1990/2 = 1505 = 5 x 7 x 43

So our solutions are:

r = 5 x 7 , c= 43 => R =85, C = 93

r = -5x7, c=-43 => R= 15, C =7

Not to complicated right J, Hope you enjoy it!