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