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
