Path on chessboard

23 Nov 2011

There is a NxN board. Alice starts first by marking a cell. Next, Bob must marks a cell that is adjacent to the previous cell. Each player takes turn. If someone cannot mark a cell anymore, then that person loses. Is there a winning strategy?

I am not good at this kind of problems. It is difficult to find an analysis, when players take turns with many possible choices.

I cannot come up with a solution, but this solution is very interesting.

Since 2 players takes 2 turns at one round, this means we can tile the whole chessboard with many dominos.

For 4x4, the dominos are tiled into a chessboard perfectly. This means that if Bob always complete a piece of the domino, Bob always wins.

For 3x3, the dominos are tiled into a chessboard with one cell left. Therefore, Alice, in turn, is the one who completes every piece of a domino and always wins.

That's it.

In Retrospec

Probably the tiling technique can always solve this kind of problem.

Each round would compose a shape, and we can tile those shapes into a board. And that's gonna be the critical point to the answer.

Give it a kudos