February 2008 riddle

Consider the following game, played on an n by n board, with n being an even number.

The game starts with each cell on the board having a number assigned to it. The numbers range between 1 and n2, each number appearing exactly once.

The game is played by two players taking alternate turns. Each player, in his turn, removes a number from the board. The number removed must be in a position adjacent to an empty cell (meaning that an empty cell should be immediately above it, below it or directly at its left or right). Because in the beginning there are no empty cells, the first player, in her first move, is allowed to pick any of the n2 possible cells.

The score given to each player is the sum of the numbers he or she removed from the board. The player with the higher sum when the board empties out is the winner.

The question this month has to do with how to cheat in this game. In particular, your role is that of the person choosing the initial permutation of numbers on the board, and the question is regarding what you can do to favor either one of the players.

• For which values of n would it be possible for you to arrange the board so that the first player wins, given that both players play optimally?
• For which values of n would it be possible for you to arrange the board so that the second player wins, given that both players play optimally?
• For which values of n it would be possible for you to arrange the board in such a way that the game ends in a tie, given that both players play optimally.