In the beginning there are $100$ integers in a row on the blackboard. Kain and Abel then play the following game: A move consists in Kain choosing a chain of consecutive numbers; the length of the chain can be any of the numbers $1,2,\dots,100$ and in particular it is allowed that Kain only chooses a single number. After Kain has chosen his chain of numbers, Abel has to decide whether he wants to add $1$ to each of the chosen numbers or instead subtract $1$ from of the numbers. After that the next move begins, and so on. If there are at least $98$ numbers on the blackboard that are divisible by $4$ after a move, then Kain has won. Prove that Kain can force a win in a finite number of moves.
Problem
Source: German TSTST - #3
Tags: Game Theory, game, Integer, number theory, combinatorics
MellowMelon
09.07.2016 19:58
Lemma: Let $a,b,c,d$ be four numbers in order (possibly with others in between which we ignore). In a finite number of moves we can get $a \equiv 0 \pmod{4}$, $b \equiv c \pmod{4}$, or $d \equiv 0 \pmod{4}$. Proof: Apply moves to $a$ and $d$ alone until both are odd. If they are 1 and 3 mod 4 in some order, then the move $a,b,c,d$ gets one of them to 0 mod 4. Otherwise, WLOG $a \equiv d \equiv 1\pmod{4}$. Apply moves to $b$ and $c$ individually until they are opposite parity. If $b-c \equiv 1 \pmod{4}$ originally, then the move $c,d$ either results in $d \equiv 0\pmod{4}$ (-1) or $b \equiv c \pmod{4}$ (+1). Otherwise $b-c \equiv 3 \pmod{4}$ and the move $a,b$ finishes. $\blacksquare$ We go by induction on the number of integers on the board, say $n$, claiming we can get $n-2$ of them to 0 mod 4. First we do the base case $n = 3$. Let the numbers be $a,b,c$. Make moves on them individually until $b$ is even and $a,c$ are odd. If $b$ is 0 mod 4 we're done, so it's 2 mod 4. If $a,c$ are different mod 4 then the move $a,b,c$ finishes, so assume both are 1 mod 4 without loss of generality. Make the moves $a,b$ and $b,c$. If Abel subtracts for either move, then $a$ or $c$ is 0 mod 4. Else, $b$ is 0 mod 4. This finishes the base case. Assume now that $n \geq 4$ and let the numbers be $x_1, x_2, \ldots, x_n$. If at any time we get either $x_1$ or $x_n$ to be 0 mod 4, we ignore that number and apply the inductive hypothesis to finish, so assume Abel prevents this at all costs. Apply the lemma with $(a,b,c,d) = (x_1,x_2,x_3,x_n)$, where we ignore what happens to the rest of the numbers. From this we get $x_2 \equiv x_3 \pmod{4}$, and we can treat that number as a single one and apply the inductive hypothesis. Because Abel never makes the ends 0 mod 4, the inductive hypothesis forces him to make all numbers in between 0 mod 4, including both numbers of the $x_2, x_3$ pair, so we're done.
62861
25.07.2016 08:25
Canada 2014/5 is a generalization.
programjames1
15.02.2018 22:13
Can a chain skip numbers? For example, could it go $1,2,3,6,7,8,...?$
xilias
15.02.2018 23:53
programjames1 wrote: Can a chain skip numbers? For example, could it go $1,2,3,6,7,8,...?$ I don't think so,it says "a chain of consecutive numbers"