Competition problem — Combinatorics

Library / /48 of 87

Combinatorics Difficulty 6.4 National Olympiad Prove it Russia

Numbers $1, 2, 3, \ldots, 60$ are written in a row (in this order). Igor and Ruslan take turns in making moves; Igor starts; by one move the player puts one of the signs of operation $+$ , $-$ , $\times$ between some pair of adjacent numbers. When a sign is placed between every two adjacent numbers we calculate the value of the obtained expression. Igor wins if this value is divisible by $3$ , otherwise Ruslan wins. Determine who of the two players has a winning strategy.

Solution

Let us replace all numbers in the sequence with their remainders modulo $3$ ; this will not change the game's outcome.

We obtain the sequence $1, 2, 0, \ldots, 1, 2, 0$ . The gaps between the numbers are numbered from left to right from $1$ to $59$ .
On his first move, Igor places a " $-$ " sign in the $30$ th gap, while pairing all other gaps as $(i, 30+i)$ . If Ruslan places a " $+$ " or " $-$ " sign in some gap, Igor responds by placing a " $-$ " or " $+$ " sign, respectively, in the paired gap. If Ruslan places a " $\times$ " sign, Igor also places a " $\times$ " sign in the paired gap.
Once all signs are placed, the resulting expression splits into several terms. The sets of terms in the left and right halves of the expression are identical but have opposite signs. Consequently, the expression's value will be congruent to $0$ modulo $3$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.