KGS math club/solution 1 1

Problem (by amkach):

Consider the two player game that begins with an even length fixed random sequence of positive integers. Each player, in turn, removes either the first or last of the remaining integers, ending when all the integers have been removed. A player's score is the sum of the integers that they removed; the winner is the player with the higher score (with a tie if equal scores). Show that Player One has a non-losing strategy, i.e., can always force a tie or a win.

Solution:

Let the sequence be (x_1 ... x_n). Let p = x_1 - x_2 + x_3 ... - x_n and

   s = score - opponent's score.

Observation: reverse the sequence and p changes to -p.

 The sequence may be reversed at will since this won't
 affect the game.

Strategy: if p >= 0, take the first, else take the last. To be shown: If strategy is followed, regardless what the

 adversary does, always s + p >= 0.

Proof by induction:

 p will always be kept positive (or 0) by reversing the
   sequence before the player 1's move if p < 0.
 1) in the beginning, s = 0  =>  s + p = p >= 0
 2) assume s + p >= 0.
    Since p >= 0 (if p < 0, reverse the sequence and 
      proceed with the proof). Now x_1 should be removed.
   If opponent takes the x_2,

s' = s + x_1 - x_2 and

     p' = x_3 - x_4 ... - x_n, and 

s' + p' = s + p >= 0.

   If opponent takes the x_n, reverse the sequence. Then

s' = s + x_1 - x_n and

     p' = x_n-1 - ... + x_3 - x_2, and

s' + p' = s + p >= 0. In the end, p will be 0, and s + p = s - p >= 0, that is,

 score >= opponent's score. q.e.d.

Here's a python script to put the strategy into an empirical test; should always give score >= 0 (exhaustively test the opponent responses): import random rand = random.randint seq = [] scores = {} for i in range(0, rand(3,6) * 2): seq.append(rand(-20,20)) print seq def play(seq, score): while (seq): sign = 1; sum = 0 for x in seq: sum += sign * x; sign = -sign if sum >= 0: score += seq.pop(0) else: score += seq.pop() play(seq[1:], score - seq[0]) score -= seq.pop() try: scores[score] += 1 except KeyError: scores[score] = 1 play(seq, 0) print "Scores by frequency\nscore freq" scorelist = scores.items() scorelist.sort() for s in scorelist: print " %3d  %3d" % s

And another for a 1000 game series: import random rand = random.randint scores = {} def play(seq, score): while (seq): sign = 1; sum = 0 for x in seq: sum += sign * x; sign = -sign if sum >= 0: score += seq.pop(0) else: score += seq.pop() play(seq[1:], score - seq[0]) score -= seq.pop() try: scores[score] += 1 except KeyError: scores[score] = 1 for i in range(0, 1000): seq = [] for i in range(0, rand(3,6) * 2): seq.append(rand(-10,10)) play(seq, 0) print "Scores by frequency\nscore freq" scorelist = scores.items() scorelist.sort() for s in scorelist: print " %3d  %5d" % s