small vs large

[BMAD]

20 Numbers are written on the board: 1, 2, ... ,20. Two players are putting signs before the numbers in turn (+ or -), where they desire. The first wants to obtain the minimal possible absolute value of the sum. 

 

What is the maximal value of the absolute value of the sum that can be achieved by the second player? 

[bonanova]

Step 1: Four-number game

Consider the simpler game using just {1 2 3 4}

Call the players A and B; player A moves first.
Let A first assign a positive number.
What is the largest sum that B can achieve?

Suppose A first assigns +1. (partial sum=1)
B's best move is +4 (partial sum=5)
A will then reduce the sum as much as possible with -3 (partial sum=2)
B will then increase the sum with +2 (final sum=4)

Record the moves more compactly; consider all four of A's initial moves.

A: +1 (1) B: +4 (5) A: -3 (2) B: +2 (4)
A: +2 (2) B: +4 (6) A: -3 (3) B: +1 (4)
A: +3 (3) B: +4 (7) A: -2 (5) B: +1 (6)
A: +4 (4) B: +3 (7) A: -2 (5) B: +1 (6)

If A begins by assigning a negative number, the |largest| sums are -4 and -6.
So in the four-number game, B can achieve |sum| = 4.

Suppose B wants the largest negative sum.

A: +1 (1) B: -4 (-3) A: +3 (0) B: -2 (-2)
A: +2 (2) B: -4 (-2) A: +3 (1) B: -1 ( 0)
A: +3 (3) B: -4 (-1) A: +2 (1) B: -1 ( 0)
A: +4 (4) B: -3 ( 1) A: +2 (3) B: -1 (+2)

By avoiding 1 on his first move, A can prevent an opposite-sign sum.
By choosing 4 on his first move, A forces a same-sign sum.

Step 2: Five sets of four numbers

Play the game with the set {5 6 7 8}

A: +5 (5) B: +8 (13) A: -7 (6) B: +6 (12)
A: +6 (6) B: +8 (14) A; -7 (7) B: +5 (12)
A: +7 (7) B: +8 (15) A: -6 (9) B: +5 (14)
A: +8 (8) B: +7 (15) A: -6 (9) B: +5 (14)

which adds 8 to the {1 2 3 4} results.

A: +5 (5) B: -8 (-3) A: +7 (4) B: -6 (-2)
A: +6 (6) B: -8 (-2) A: +7 (5) B: -5 ( 0)
A: +7 (7) B: -8 (-1) A: +6 (5) B: -5 ( 0)
A: +8 (8) B: -7 ( 1) A: +6 (7) B: -5 (+2)

which is the same as the {1 2 3 4} results.

For {9 10 11 12} the largest sum is 20
For {13 14 15 16} the largest sum is 28
For {17 18 19 20} the largest sum is 36.

Step 3: The full game (simplistic view)

When A plays (in one of the four sets of numbers), then if B always plays in the same set,

playing {1 2 3 4 ... 17 18 19 20} reduces to playing playing the five 4-number games,

(just not in sequence.)

 

In particular, A will be forced to make the first play in each set, so the analysis in Step 2 will apply.

If A anticipates that B will maximize the magnitude of the individual sums,

then A's play reduces to choosing the signs (by the sign of his first play)

of the five numbers {4 12 20 28 36} so that their sum has the smallest magnitude.

 

Since {4 12 20 20 36} = 4 + 8 x {0 1 2 3 4} the minimum sum of 4 is achieved

when the bracket sums to 0. That is {0 1 -2 -3 4} or {0 -1 2 3 -4}.

So the simplistic solution is: B can (at best) achieve |sum| = 4.

Step 4: The full game (no assumptions on play)

B need not try for the maximum sum from each set.

B might create sums of {-2 0 2} from any of the sets.

By tracking progress in each of the five sets,

B can likely achieve a total sum much larger in magnitude than 4.

Which is why I titled the spoiler "first thoughts."

 

There's probably a much simpler approach, like making adjacent moves wherever possible.

[bonanova]

Better strategy for

B:

1. A puts a sign on a number, say +12.
2. B puts the same sign on the highest unsigned number, +20 (partial sum S₁= +32.)
3. A moves.
4. B puts + on the highest unsigned number
5. Repeat until 20 signs have been placed.

S₁, the partial sum after B's first move, cannot be reduced all the way to zero.

A's  best strategy is to minimize S₁ at the outset by playing low on his first move: +1,

making S₁ = 21, then reduce the sum as much as possible on his succeeding moves.

 

That game proceeds as follows: ( of course, if -1 is played first, all the signs reverse)

 

  A   B  S_i

 +1 +20 +21

-19 +18 +20

-17 +16 +19

-15 +14 +18

-13 +12 +17

-11 +10 +16

 -9  +8 +15

 -7  +6 +14

 -5  +4 +13

 -3  +2 +12

 

B's highest achievable |sum| is 12.

[jasen]

First player will always choose a biggest number and put (-) in front
Second player will always choose a biggest number and put (+) in front

so the result will be

-20+19-18+17-16+15-14+13-12+11-10+9-8+7-6+5-4+3-2+1 = -10