Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Why do you think that player 1 has a winning strategy? –  Michael Greinecker Nov 21 '11 at 13:53
    
It's not so Nim-like. Perhaps the most important feature of Nim-like games is the normal play condition--that is, the loser is the first player unable to make a move. This game determines the winner by a computed score, which is completely different. –  Nathan Nov 21 '11 at 14:05
    
@ Michael.G. - I heavily suspect it. I haven't found/seen any example that shows that player 2 can win (in some cases, he can force a draw). –  Shaywei Nov 21 '11 at 14:44
    
The extraprdinary book Winning Ways for your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy develops what's more or less a general theory of num-like games. That shoould probably be the first place to look for information. –  Mariano Suárez-Alvarez Nov 21 '11 at 15:32
    
@Nathan: many games have nim limits, which makes them nim-like. In this game, consider the case where one of the tokens has value larger than all the others combined. Then the game is equivalent to a two-pile game of nim. –  Anton Geraschenko Nov 23 '11 at 18:12
add comment

7 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
You might want to edit the last paragraph. In the position 2-1-2-3, that similar strategy for the second player doesn't quite work, right? –  Johan Wästlund Nov 21 '11 at 16:26
    
Right. Thanks for the correction; I've edited the answer to retract the error. –  Andreas Blass Nov 21 '11 at 20:38
add comment

If I understand your question right, then there is a winning strategy for the first player when the number of 'tokens' is even. More generally if you have a tree with weighted vertices (with integer values) and each player takes turns in removing a leaf then the first player wins if the number of vertices is even. A proof can be found in

http://www.math.unl.edu/~s-tseacre1/grab-the-gold-8.pdf

Unfortunately the proof isn't constructive.

Edit : Indeed Andreas points out the paper mentions the result for paths is simpler, was so happy to be able to answer an MO question I forgot to stop to think about it.

share|improve this answer
add comment

Well, if $\sum a_i$ is odd, then there cannot be a draw and so by Zermelo's theorem one of the players has a winning strategy. If the sum of the $a_i$'s is even then one player may be able to force a draw.

Edit: False statement removed, see answer by Joshua Erde.

You could naively work out the min-max tree to find the optimal strategy for each player in $O(2^k)$ worst-case time using a branch and bound algorithm, which would probably work much better than $O(2^k)$ as a heuristic.

Using dynamic programming it can be done in polynomial time.

share|improve this answer
1  
One of the constraints is that the number of tokens is 2k, that is, even. Therefor, (1 10 1) and (1 1 10) are not valid examples. –  Shaywei Nov 21 '11 at 14:43
    
Thanks, answer edited –  Michael Biro Nov 21 '11 at 15:43
add comment

I apologize for not being able to provide a reference, but I have heard Peter Winkler speak on precisely this problem, with essentially the same answer Andreas Blass gave here. One correction, though: If the two sums (of the odd- and even-numbered positions) are equal, the first player may still have a winning strategy, because at the beginning of each round he can reevaluate whether to go with evens or odds, as the example 2-1-2-4-2-1 shows.

As I recall, all bets are off if there's an odd number of tokens. That's in part because even with an even number of tokens, things get subtle if the goal is to find a strategy that maximizes the first player's total take.

share|improve this answer
    
Page 1 of "Mathematical Puzzles: A Connoisseur's Collection". –  Johan Wästlund Nov 21 '11 at 16:37
1  
One more up vote will give me a reputation total of 666, at which point I can retire with a devil-may-care attitude... –  Barry Cipra Nov 21 '11 at 17:26
add comment

Here's a simulation of the problem from Winkler's book:

http://www.cut-the-knot.org/Curriculum/Games/Coins.shtml

What if the tokens are arranged on a circle? The first move is arbitrary; after that the game proceeds as before.

share|improve this answer
add comment

It has already been pointed out that the first player can take either all tokens at odd positions or all tokens at even positions, thereby securing at least a draw. But the example 2-1-2-3 shows that such a strategy is not always optimal.

Since the game has only $O(k^2)$ positions (subsequences of consecutive tokens), an optimal strategy can be computed in polynomial time.

share|improve this answer
add comment

Some observations (correct ones, I hope): I will use $a_i$ to denote both a token and the value it has. Consider a position $a_1a_2\dots a_t$ We may assume that $a_1 \ge a_t$ and that not all the values are equal (because we already understand that case). For purposes of analysis, we may also scale so that the elements sum to 1 (remembering to rescale if we want the value for use elsewhere.) The value $v(a_1\dots a_t)$ is the winnings of the first player minus those of the second (under optimal play.)

  • for $t=1$ the value is $a_1$ and for $t=2$ it is $a_1-a_2.$ In general it is the smaller of $a_1-v(a_2\dots a_t)$ and $a_t-v(a_1\dots a_{n-1}$)

  • for $t=3$ it is $a_1 +\operatorname{min}(a_2,a_3)-\operatorname{max}(a_2,a_3)$

  • For purposes of analysis that we may rescale so that the elements sum to $1.$ In the case that $t$ is even we may first subtract the same amount from each token to make the minimum $0.$

  • The full course of the game (under optimal play) depends only on the order of the $2^t$ partial sums (not all of which are pertinent.)

  • When the optimal strategy changes it is a tie game, with two optimal strategies.

  • We have seen that when $t$ is even the first player can be sure to get at least half the value by a simple strategy.

  • If one of the $a_i \gt 1/2$ then the winner is the first player when $t$ is even. It is the second player when $t$ is odd except for the case that $a_1 \gt 1/2.$ The value is easy to determine because one player has all the even index tokens and the other all the odd. If some $a_i=1/2$ then everything is the same except when $a_j=0$ for all tokens with $j-i$ even. Then there are two strategies.

  • We assumed $a_1 \ge a_t,$ if also $a_1 \ge a_2$ then the first player has a winning strategy choosing $a_1.$

  • An analysis by cases of $t=4$ is not hard, especially assuming that the smallest entry is $0$ and the rest sum to $1$

    • for $0x(1-x)0$ choose the $0$ by the smaller entry
    • for $xy(1-x-y)0$ choose $x$ unless $y=1/2$ in which case either choice leads to a tie.
    • for $x0(1-x-y)y$ choose $x$ unless also $y=1/2$ in which case either choice leads to a tie.
    • for $x(1-x-y)0y$ chose $y$ if $1-x-y \ge 1/2$
  • I feel that the first player wins in the even case but do not have a justification for that.

I don't know how succinct $t=5$ and $t=6$ would be. A program with the rules for $t \le 4$ built in might lead to some easily proved observations.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.