Number $ 0$ is written on the board. Two players alternate writing signs and numbers to the right, where the first player always writes either $ +$ or $ -$ sign, while the second player writes one of the numbers $ 1, 2, ... , 1993$,writing each of these numbers exactly once. The game ends after $ 1993$ moves. Then the second player wins the score equal to the absolute value of the expression obtained thereby on the board. What largest score can he always win?
Problem
Source: Russia 1993
Tags: modular arithmetic, pigeonhole principle, absolute value, combinatorics unsolved, combinatorics
azjps
07.10.2008 23:45
We claim the maximum guaranteed is $ 1993$. The first player can repeat the following step: if the current sum is positive, make the next sign a “minus”, and vice versa. The sum then can never exceed $ 1993$.
To guarantee $ 1993$, the second player may partition the numbers $ \{1,2,3,4, \ldots, 1992\}$ into the $ 2$ subsets $ \{A: 4k,4k+3\},\{B: 4k+1,4k+2\}$ (and ignores the $ 1993$). If the sign is a “plus”, then select a number from $ A$, and if the sign is a “minus”, then select a number from $ B$. When the player runs out of numbers to pick from either set, he uses $ 1993$. WLOG let him run out of $ A$ first, then the sum of the positive numbers $ = \sum A + 1993$, and the second player’s sum is $ \ge \sum A +1993 - \sum B = 1993$.
steaxauce
10.10.2008 09:28
So you're saying that, in short, the first player writes + if the current sum is negative and - if the current sum is positive, and the second player is ordering the numbers he puts down so that he saves 1993 for last and puts down 1 through 1992 in such an order that with the first player continuing to put down + when the sum is negative and - when the sum is positive, the first 1992 numbers will sum to zero. But the problem is that all the first player would have to do to thwart this strategy is to break his pattern and put pluses and minuses down in a way that would make it impossible for the second player to make his first 1992 numbers sum to 0 (or to a number n>=3986 or n<=-3986). Can you prove that this is impossible? I think it's pretty easy to see that it isn't: For instance, what if player 1 follows the strategy you gave until the second to last move, when he puts down a + if the current sum is positive and a - if the current sum is negative, and then uses the opposite sign for the final move?
azjps
11.10.2008 01:08
I believe that is what I showed. (by "isn't", do you mean is possible or isn't possible?) First, we showed that player 1 can prevent player 2 from getting a score greater than a $ 1993$. Second, we show player 2 can at least get $ 1993$. Let $ S$ be the sum of $ 1 + 2 + \cdots + 1992$. We pick a non-$ 1993$ number that is $ \equiv 0,3 \pmod{4}$ if the sign in front of the number is a '+' (not if the current sum is negative), and we pick a number $ \equiv 1,2 \pmod{4}$ if the sign in front of the number is a '-' (not if the current sum is positive). By pigeonhole, player 1 has to use at least $ \frac {1992}{2} + 1 = 997$ of the '+'s or the '-'s, and on this $ 997$th instance, we use our $ 1993$ [this does not have to be the last number!]. Right now, the absolute value of the sum of the group of $ 997$ numbers is $ S/2 + 1993$; the absolute value of the other group can be at most $ S/2$. It follows that player $ 2$ can at least get $ 1993$. edit: okay, no problem.
steaxauce
11.10.2008 04:34
I apologize, thanks for the clarification. By "isn't" I meant "isn't impossible" <=> "is possible". Also, I made an error in my first sentence (now corrected) by switching the '+' with the '-'. Your first statement was what I misinterpreted. I read it as meaning that the strategy you stated for the first player was his ideal strategy under any circumstances (and that you were basing the rest of your proof on that), not as a proof that the first player cannot have a minimum guaranteed score above that.