Ana and Beto play against each other. Initially, Ana chooses a non-negative integer $N$ and announces it to Beto. Next Beto writes a succession of $2016$ numbers, $1008$ of them equal to $1$ and $1008$ of them equal to $-1$. Once this is done, Ana must split the succession into several blocks of consecutive terms (each term belonging to exactly one block), and calculate the sum of the numbers of each block. Finally, add the squares of the calculated numbers. If this sum is equal to $N$, Ana wins. If not, Beto wins. Determine all values of $N$ for which Ana can ensure victory, no matter how Beto plays.
Problem
Source: Rioplatense Olympiad 2016 level 3 P1
Tags: game strategy, combinatorics, Sum of Squares, game
05.09.2018 22:57
Suppose $N> 2016$. Then Bob can simply play $1,-1,1,-1,\dots$, and Ana can achieve at most $2016$. So $N\le 2016$.
06.09.2018 04:55
I believe any even number from 0 to 2016 works.
21.04.2020 18:58
Bumplease
21.04.2020 19:34
Answer $N$ is any even number from $0$ to $2016$. Proof It is necessary for $N$ to be an even number from $0$ to $2016$. If Bob chooses the sequence $(1, -1, 1, -1, \dots, 1, -1)$, then the most Ana can get is $2016$ by making the blocks $((1), (-1), (1), (-1), \dots, (1), (-1))$. Also, the sum of any block Ana can make is $-1, 0,$ or $1$. Whenever Ana makes a block that sums to $-1$ or $1$, it takes an odd number of values. Whenever the block sums to $0$, there are an even number of values. So, there are an even number of blocks that sum to either $-1$ or $1$, which implies that $N$ must be even. It is sufficient for $N$ to be an even number from $0$ to $2016$. Now we show that all even values of $N$ work between $0$ and $2016$. First, suppose Ana has a sequence of $N\ge 4$ blocks, such that the sum in each block is either $-1$ or $1$. We show that it is possible to find another sequence with $N-2$ blocks all summing to either $-1$ or $1$. Let the blocks be $$B_N = (b_1, b_2, \dots, b_N)$$There exists $2$ consecutive blocks, $b_i$ and $b_{i+1}$ that sum to $0$. Otherwise, all $b_j$ are of the same sign, which implies that $$|b_1 + b_2 + \cdots + b_N| > 0,$$impossible as $$b_1 + b_2 + \cdots + b_N = 1 + (-1) + 1 + (-1) + \cdots + (-1) = 0.$$If $i=0$, take $b_{0}, b_{1}, b_{2}$ and combine them into one block. Otherwise, take $b_{i-1}, b_i, b_{i+1}$ and combine them into one block. We have found a new sequence of $N-2$ blocks that each sum to either $-1$ or $1$. This shows all even numbers from $2$ to $2016$ are possible. What about $0$? That can be achieved by a single block with all of the numbers. $\blacksquare$