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.
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.