## February 2008 solution

### The first player can always be made to win.

Suppose the first player uses the following strategy: always take the highest possible value at any given turn. For this strategy, we can arrange the board so that each value but the highest has a neighbor of higher value than it. This will cause the first player to always take a higher value than is taken by the second player in the subsequent turn. Such arrangements of the board are very easy to find. For example, one can arrange the numbers in standard reading order.

### The second player can be made to win if and only if n>2.

For n=2, it can easily be shown that the strategy described above for the first player always results in this player winning.

For n>2, we will show a winning arrangement and a winning strategy for the second player. This strategy revolves around the concept of "traps". A trap is an odd-sized connected set of high-valued cells surrounded by low-valued cells in the set of all its immediate neighbors, which must also be of odd size.

Here is an example of such a trap, with diamonds signifying high values and empty cells signifying low values. Notably, the total number of cells composing a trap is even.

Suppose that we tile the board into connected sets, each of even size. A feasible strategy of the second player will be in this case "Consider only values that are of the same set as the first player took from in her latest turn. Of these, remove the highest possible." If one of the sets is a trap and the first player steps into it (removes a first value from it), this cell will necessarily contain a low value. The second player, following her strategy, will take a high value. Ultimately, the trap will be emptied with the second player taking at least one more high value than the first.

We will need an arrangement with at least three traps. The reason for this is that the first player can choose where to begin in the first move, and she can avoid one trap by beginning in one of its high-valued positions. As the first player can choose to do this with the trap for which the prize is highest, we will need at least two additional traps to counter-balance this.

We will not use the kidney-bean shaped trap described above, because it is too large for our purposes. Instead, we will use the smallest possible trap: This is a trap, provided that the middle piece of the trap is an edge piece of the board, and therefore has exactly three neighbors. On a 4x4 board, four such traps can be placed in the following arrangement: On any larger board, we'll place four such traps along with domino tiles to complete the rest of the board in a formation such as the one demonstrated below for 8x8: We will place in each trap the values a, a+1 and a+2 for the low-valued cells and b for the high-valued cell, for some such a and b. This configuration insures that the sum of values taken by the second player is at least b-a-3 larger than that of the first player, for cells taken from the trap, provided that the first player doesn't choose to begin the game in the high-valued cell. If she does, the sum of the cell values taken from the trap by the first player will be no more than b-a-1 greater than that of the second player.

We will place in each domino piece two consecutive numbers, insuring that the advantage gained by the first player on each such tile is at most 1.

Suppose the values used in the four traps are:

a1=1 b1=n2-3
a2=4 b2=n2-2
a3=7 b3=n2-1
a4=10 b4=n2

The best strategy of the first player is to begin the game inside the first trap. This will give her n2-5 for that trap. She will also get one point for each of the n2/2-8 domino tiles. However, she will lose n2-9 for the second trap, n2-11 for the third and n2-13 for the fourth, resulting in a total balance of 1.5n2-20, which, for n≥4 is in favor of the second player.

### A tie can be forced if and only if n>2.

As we have seen, the first player's strategy is unbeatable for n=2. For all other n, consider the following: Suppose we have not just four traps of the kind described in the previous section but k of them. Suppose further that these k traps utilize the values n2-4k+1 through n2. We will arrange the remaining n2-4k values so that each has a neighbor of greater value within the n2-4k, except the value n2-4k, which should be a neighbor of the trap with the highest b-a value.

The nice thing about this arrangement is that both players have a clear best strategy: the first player starts with the high-valued cell of the trap with the highest b-a value, then continues by always picking the highest possible value, excluding values within the traps. Once all the rest of the board is empty, the first player goes into the traps in such a way that the a+2 and a+1 values will be hers.

The strategy for the second player (given the strategy of the first player and the arrangement of the board) is as follows: if the first player took a value from a trap, take the highest possible value within that trap. If not, take the highest possible value from outside any trap.

Now, the question is merely what the values of the traps are, to determine who wins. Here is a possible arrangement (the notation of which will be explained immediately aftrwards):

ZZZAAABBBCCCDDD .... XXXYYYYX .... DCBAZ

The notation used here is as follows: the first letter signifies the identity of the trap to which the value n2-4k+1 belongs. The next, signifies the identity of the trap to which the value n2-4k+2 belongs, and so on, with the last letter signifying the identity of the trap to which the value n2 belongs. The first three values and the last value belong to the trap denoted as "Z". This means that this trap has n2-4k+1 as its a value and n2 as its b value, making it the highest valued trap.

In the arrangment, the second player can reach a tie on the "Y" trap, gain 4 points on the "X" trap, and so on, with the "A" trap allowing the second player to gain 4k-8 points on it. In both cases, the "Z" trap can, potentially, be used by the second player to gain 4k-4 points, but, in fact, the first player will start within it, taking the n2 value first, so it will actually give the first player an advantage of 4k-2.

Consider the final total balance. The first player can gain (n2-4k)/2 points for all values outside traps plus an additional 4k-2 on the "Z" trap, giving her a total advantage of n2/2+2k-2. However, the remaining traps set the balance back by 2(k-2)(k-1) to a total of n2/2-2k2+8k-6 or n2/2-2(k-2)2+2.

Choosing k to be n/2+2 makes the first player win by exactly two points.

Now, we will tweak this arrangement slightly, by replacing the high values of the "Z" trap and the "A" trap to form this new arrangement:

ZZZAAABBBCCCDDD .... XXXYYYYX .... DCBZA

The "Z" trap, though its b value has been lowered by 1, is still the most valuable trap, so the first player will start from it. On the other hand, the "A" trap's b value has been raised by 1. This sets the first player's total balance back by 2, causing a tie exactly.

The only remaining question is whether k=n/2+2 can be afforded in every case where n>2. In fact, one can arrange along the sides of an n by n board a number of traps that is equal to 4n/3 up to a constant. By simple trial and error, one can find that a 4x4 board accomodates four traps, a 6x6 - five and an 8x8 - eight. (One would have been able to fit six on a 6x6 board, if we didn't require for the remaining pieces to be connected.) For any larger shape, note that one can create an arrangement for an (n+6)x(n+6) board given an n by n board by simply keeping each trap at a constant position relative to its nearest corner and adding two traps to each side in the positions that become freed. This adds 8 traps when raising n by six, which is much more than the required three.