I will show you only two combinations("x" means stone, that was
killed at last lead).
1). Those you can kill three stones
    oo   xo   oo   ox
    oo  oo   ox    o
    oo  oo   o     o

2). Those you can kill six stones
              o     oo    ox    o
    oooo   ooox   oox    oo    oo   ox   o
    oooo   ooo    oo     oo     xo   oo  ox

This are all you need to get AC. (But I cannot prove that
 if (M Mod 3 = 0) or (N Mod 3 = 0) answer is 2, I can only show how
make it)
P.S. Sorry for bad English.

cannot get it....

BTW, you also need that if you have only one row or column, you can only take half of the stones

Interesting. But I also can't proove it! How to get this idea more formally? Let's talk about this.

Thank you

if n or m is divided by 3 we can prove that we can leave only 3x3 stones. and than its easy to finish game with 2 stones.

assume that m is divided by 3.so we can divide rectangle into m/3 parts and reduce each's "n" to 3. than reduce m to 3 and we'll get cube with dimensions 3x3.


Edited by author 16.04.2007 22:24

I still can't get it,especially for your graph,I hope you can explain it more clear.
Thanks.

Here comes the proof of why you can't remove all stones but one if M or N is divisible by 3.
Let us paint all the grid nodes for which the sum of their coordinates is divisible by 3 ((x + y) mod 3 = 0) in red, all ones meeting the (x + y) mod 3 = 1 condition in green, and the rest in blue. Let us also denote the amount of stones placed in red, green and blue nodes as R, G and B respectively.
Obviously, each turn two stones lying on nodes of different colors turn into one stone lying on the third color. So, two of the R, G and B values get decreased by 1, and the third one gets increased by 1.
This process has an invariant: parities of (R - G), (R - B) and (G - B) don't change! At the start of the game with M or N being divisible by 3 R, G and B are equal. So all the three differences listed above stay even till the very end, and it's impossible to get the (1,0,0), (0,1,0) and (0,0,1) combinations of R,G,B, therefore the game can't be finished with only one stone. Q.E.D.
P.S. My English could have some flaws, i know.