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