I have been reading Grade Five Competition from the Leningrad Mathematical Olympiad by Garaschuk and Liu, which is a wonderful source of interesting problems. One of the problems from the year 1984 is stated below:
Problem. Anna and Boris play a game with the numbers from 1 to 100 written in order in a row. Anna goes first, and turns alternate thereafter. In each move, a player puts one of the operation signs +, − and × between any two numbers which do not already have an operation sign in between them. After 99 operation signs have been placed, the value of the expression is computed. Anna wins if this value is odd, and Boris wins if it is even. Prove that Anna has a winning strategy.
Remark. Unfortunately, the problem does not clarify if the order of operations matter, namely, if multiplication should be applied before addition -- I assume this should be the case.
The solution given at the end of the book is written in a way that is confusing to me. I will include it below. Since I don't want to spoil the solution to those who want to think about it, I will make it invisible:
Since only parity matters, we may replace all $−s$ by $+s$. Let $0$ represent an even number and $1$ represent an odd number. Anna starts by adding the last two digits, in some alternating sequence which begins and ends in $1$'s. Suppose Boris inserts a $\times$ sign, necessarily between a $0$ and a $1$, generating two adjacent $0$'s. Anna inserts a $+$ sign between them. Suppose Boris inserts a $+$ sign, necessarily between a $0$ and a $1$, generating two adjacent $1$'s. Anna inserts a $\times$ sign between them. In either case, the sequence is shortened by two digits, but remains alternating. Moreover, it still begins and ends in $1$'s. Eventually, the sequence shortens to $101$ and Anna wins.
Question 1. Can someone clarify the details in this solution and explain it in simpler terms?
Question 2. Is there another, perhaps more intuitive, solution to the problem?
Answer to either of the questions is very welcome!
My interpretation of the problem statement: every time a player inserts an operation she/he puts parenthesis around the operation. This means that we can throw away the operands and replace them with the result. For example:
1 0 1 0
1 0 (1 + 0) ==> 1 0 1
(1*0) 1 ==> 0 1
(0 + 1) ==> 1
If this is correct then Anna can successfully maintain a shrinking sequence of alternating 1's and 0's which start with 1 and end with 1. The last such sequence will have a single 1, i.e. odd.
I can't think of a better and/or more intuitive solution.