ko_osaga's blog

An interesting chessboard game
By ko_osaga, history, 7 years ago, In English

In a n x m chessboard with cells labeled (i, j) for 1 ≤ i ≤ N, 1 ≤ j ≤ M, there is a stone at (1, 1). A and B is playing a game.

A starts first, and they alternately move stone to adjacent cell (north / west / south / east). It's okay to move stones to previously visited cells, but it's prohibited to move stones to previously visited "edges". For example, if someone wants to move stone from (1, 1) -> (1, 2), they shouldn't have a record of visiting (1, 1) / (1, 2) or (1, 2) / (1, 1) cells consecutively. Player unable to make a move loses.

Who is the winner? 1 ≤ n, m ≤ 106

About 1 month ago, me and other guys tried to solve this problem but failed. I also googled about this problem, but wasn't able to find any resources about it :/ Here are some observations to share.

Hint originally written in statement
Observation 1
Observation 2
Observation 3
Observation 4

Could anyone help me to solve this?

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

»
7 years ago, # |
  Vote: I like it +46 Vote: I do not like it

this is a complete guess (of course, I'll try to dis/prove it), but it just fits all your observations and some additional cases I checked (3 rows, 1-4 columns):

A wins if and only if gcd(N + 1, M + 1) = 1?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    Sorry, here was some wrong info, because I had a bug in the code =(

    But it seems that your idea is true, at least for all (N, M), that (N-1)*M < 36

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +15 Vote: I do not like it

      Are you sure? I wrote a program and it yields the exact opposite from what you said. (4, 9) B wins, (3, 12) A wins, (3, 14) A wins. (it took like 30 seconds on (3, 14), though I didn't compile with optimization flags). So it's either my code is wrong, or you're wrong. Here's the code, I'll try to find if it has any bugs:

      int n, m;

bool calc(int step, int x, int y, vector<vector<bool>> &hor, vector<vector<bool>> &vert) {
	bool rtn;
	if (step & 1) { // B's turn
		rtn = true;
		if (x < n - 1 && !hor[x][y]) {
			hor[x][y] = true;
			rtn = rtn && calc(step ^ 1, x + 1, y, hor, vert);
			hor[x][y] = false;
		}
		if (x > 0 && !hor[x - 1][y]) {
			hor[x - 1][y] = true;
			rtn = rtn && calc(step ^ 1, x - 1, y, hor, vert);
			hor[x - 1][y] = false;
		}
		if (y < m - 1 && !vert[x][y]) {
			vert[x][y] = true;
			rtn = rtn && calc(step ^ 1, x, y + 1, hor, vert);
			vert[x][y] = false;
		}
		if (y > 0 && !vert[x][y - 1]) {
			vert[x][y - 1] = true;
			rtn = rtn && calc(step ^ 1, x, y - 1, hor, vert);
			vert[x][y - 1] = false;
		}
	}
	else {
		rtn = false;
		if (x < n - 1 && !hor[x][y]) {
			hor[x][y] = true;
			rtn = rtn || calc(step ^ 1, x + 1, y, hor, vert);
			hor[x][y] = false;
		}
		if (x > 0 && !hor[x - 1][y]) {
			hor[x - 1][y] = true;
			rtn = rtn || calc(step ^ 1, x - 1, y, hor, vert);
			hor[x - 1][y] = false;
		}
		if (y < m - 1 && !vert[x][y]) {
			vert[x][y] = true;
			rtn = rtn || calc(step ^ 1, x, y + 1, hor, vert);
			vert[x][y] = false;
		}
		if (y > 0 && !vert[x][y - 1]) {
			vert[x][y - 1] = true;
			rtn = rtn || calc(step ^ 1, x, y - 1, hor, vert);
			vert[x][y - 1] = false;
		}
	}
	return rtn;
}

int main() {
	fast;
	while (1) {
		cin >> n >> m;
		vector<vector<bool>> hor(n - 1, vector<bool>(m, false)), vert(n, vector<bool>(m - 1, false));
		cout << (calc(0, 0, 0, hor, vert) ? "A wins" : "B wins") << endl;
	}
}

      hor stands for the horizontal lines (whether I passed through one or not), and vert is for vertical ones. I can't attach a picture right now but I wrote the lines' indicies on paper, I'm sure you can find them too (used 0-indexing).

      Edit: while I wrote this comment you updated yours now to say it's not true. So it's my turn now :P

      → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +49 Vote: I do not like it

Here is one picture proof that A can win if gcd(N+1, M+1) = 1. I'm working on if it is sufficient that two are coprime for A winning!

Edit 1. I changed picture to (N=9, M=14)

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

    Wow, that's great...

    But you actually meant that it proves that if gcd(N + 1, M + 1) ≠ 1 then B can win, right? Not that if gcd(N + 1, M + 1) = 1 then A wins?

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

      It seems to me, it's not hard to show, that after the first move the next moves are easy to be determined, they looks like "right, down, right, down, right, down ..." and if someone will not stick this order, the other will force him to lose, returning by this way. So they will go with this pattern to next wall and there we can say that now they will play on field (N - (M + 1), M), and so on, until we get field (K, K) -> B wins, or (K + 1, K) -> A wins.

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

I believe this is a variant of FKMO 2009? Maybe this can be of use.

See https://artofproblemsolving.com/community/c6h496967p2790926 for an idea.

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

    Actually, I am trying mixing it with Euclidan algorithm but it is not working well :(

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

The general problem is called "Undirected edge geography". Here is the paper where I suppose the name originates from: http://www.sciencedirect.com/science/article/pii/030439759390026P.

Your case is covered by Theorem 4.2.

→ Reply