Hello everyone,
Today espr1t gave us the following game theory problem. Elly and Kriss are playing a game on a table with size NxM (1<=N,M<=10^9). The player to take a move chooses a cell from the table (R,C) and removes row R and column C and this way she splits the board in 4 parts of sizes (R-1)x(C-1), (R-1)x(M-C), (N-R)x(C-1), (N-R)x(M-C). The one who can't make a move loses. We are to find out who the winner will be. The idea was to use SG numbers in order to find some pattern which has complexity O(N^2*M^2) and it turned out that the only boards for which the first player loses had sizes 2x2, 4x4, 4x6, 8x12 and 10x10. However, we (also espr1t himself) can't prove that this works for every board, we have only checked that for N and M up to 2000.
Please, help us :D
Interesting problem. All I can come up with is that if either N or M is odd then it's an obvious win for the first player due to symmetrical play. Would be nice to see some proof for even grids.
Isn't it a simple N*M sg??? You can check numbers 1 to 100000.
The sg solution is O(N^2 * M^2). If you have an O(nm) one then please elaborate, even though that wouldn't be a proof.
E pa naistina li bre
The same problem on SPOJ, but with smaller constraints.
Yes, I know how to solve it for small values but I need a proof that those are the only tables for which the second player wins :)