[Math] Nim-like(?) game winning strategy

combinatorial-game-theorynim

I have the following Nim-like game (at least, it seems Nim-like to me).

There are $2k$ tokens in a row, $k \in \mathbb{N}$.

Each token $a_i$ has a value $ v_i \in \mathbb{N}$

All this information is revealed to both players in advance.

In each turn, the acting player needs to take one token from on of the edges only! – i.e: take $a_i$ such that: $i$ is either the lowest remaining available index or the highest.

What would be a winning strategy for the first player? (computable in "reasonable")

Example game:

Tokens: $a_1=7;a_2=3;a_3=1000;a_4=10;a_5=7;a_6=1000 $

(Here $k=3$)

Turn 1 – Player 1 take $a_6$.

Turn 2 – Player 2 takes $a_1$

Turn 1 – Player 1 take $a_5$.

Turn 2 – Player 2 takes $a_4$

Turn 1 – Player 1 take $a_3$.

Turn 2 – Player 2 takes $a_2$

Player 1 wins with 2007 points. Player 2 loses with 20 points.

Best Answer

Joshua Erde's answer is better than he thought. Although the paper he cites proves the result for all trees with an even number of nodes, it contains a short remark (on the first page) about the case of a linear ordering. That remark provides the following answer to the present question in the case where draws are impossible. Assume, without loss of generality, that at least half of the total value is in odd-numbered positions. Then the first player gets all the odd-numbered positions (and therefore at least a draw, and therefore a win since I assumed draws are impossible) as follows. Take the element at position 1. That leaves even-numbered positions (2 and 2k) at both ends, and the second player must take one of them. The first player then takes the neighboring odd-numbered position. Once again, both ends are even-numbered positions and the second player must take one. Continuing in this way, the first player simply takes, at each move after the first, the token next to the one that the second player just took. It is clear that this strategy gives the first player all the odd-numbered tokens.

More generally, this strategy works unless the odd-numbered positions contain exactly half of the total value. In this case, the strategy only guarantees the first player a draw, and he cannot do better because a similar strategy for the second player also guarantees at least a draw.

EDIT: As Johan Wästlund pointed out, the last half-sentence, "and he cannot do better ...," is nonsense. Please ignore it.

Related Question