P_Nyagolov's blog

Game Theory Proof
By P_Nyagolov, history, 8 years ago, In English

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

  • Vote: I like it
  • +83
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Isn't it a simple N*M sg??? You can check numbers 1 to 100000.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The same problem on SPOJ, but with smaller constraints.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply