8
$\begingroup$

All positive integers from $1$ to $n$ are written in a row in increasing order. Two players, $A$ and $B$ are playing a game where they each take turns erasing two consecutive numbers from the row and replacing them either by their product or their sum. Player $A$ wins if the last remaining number is odd, otherwise player $B$ wins. If player $A$ takes the first turn, find all possible values of $n$ for which player $A$ has a winning strategy.

This is a problem from a mock contest of last week. Here is my progress in solving the problem:

The game ends after $n-1$ turns. Since player $A$ takes the first turn, he can take the last turn for even $n$s. He can win the game if he is left with two odd numbers (by taking their product) or one odd and one even number (by taking their sum) before the last turn. But he can't win the game if he is somehow left with two even numbers before the last turn.

But for odd $n$s, player $B$ takes the last turn. He can make an even number in the last turn when he is left with two even numbers (by taking their sum or product) or two odd numbers (by taking their sum) or one odd and one even number (by taking their product) before the last turn. Thus, player $B$ can always win for odd $n$s.

Hence, player $A$ can win only for even numbers but not for all even numbers. I further claim that he has a winning strategy only if $n\equiv 2 (\bmod 4)$ noticing the cases $n=2$ and $n=4$. But I couldn't prove this.

So, I currently need a proof to the claim. Also, some other methods to solve the problem are welcome.

Edit: I made a mistake in the case $n=4$. So, my above claim is not correct.

$\endgroup$
9
  • $\begingroup$ Why do you claim that $A$ can't win for $n=4$? The initial row is $1,2,3,4$, and in his first turn he can combine $3,4$ to $7$, leaving $B$ with $1,2,7$. Now, doesn't matter what $B$ does, he can't touch both $1$ and $7$ and therefore in his last turn, $A$ will have $2$ numbers, one of which is odd, and in any case (odd and odd or odd and even) he can make the last number odd. $\endgroup$
    – Omer
    Aug 5, 2021 at 15:24
  • $\begingroup$ @Omer Ah, made a mistake. I rather started with 2,3 and 1,2 and those didn't work. Then, I ignored 3,4 as I was confident that wouldn't work also. Now, I get it that's the mistake. $\endgroup$
    – Oshawott
    Aug 5, 2021 at 15:31
  • $\begingroup$ This game looks like a generalized Nim game, with two piles of matchsticks (odds and evens) and you can 1) remove one even number, 2) remove and odd number, 3) remove two odd numbers and add an even number conditionally $\endgroup$ Aug 5, 2021 at 15:39
  • $\begingroup$ Could you please provide a specific source for this problem? $\endgroup$
    – paw88789
    Aug 5, 2021 at 15:41
  • 1
    $\begingroup$ @Maxence: I don't think it's a generalized Nim game because of the asymmetric winning conditions. $\endgroup$
    – paw88789
    Aug 5, 2021 at 15:42

2 Answers 2

4
$\begingroup$

First note that we can think of the row as a row of $0$'s and $1$'s because we only care about pairity.
Let $n$ be the length of the row.
Claim:
$1)$. if $n$ is even and $A$ begins, than $A$ wins.
$2)$. if $n$ is odd and $B$ begins, than $A$ wins.

Note that $1)$ is enough for us for the problem, but we will prove both $1$ and $2$ simultaneously by induction on $n$.

The base cases $n=1,2,3$ are trivial. Suppose now the claim holds for $1,2,...,n-1$ and let's prove it for $n$.
If $n$ is even, the row is of the form $1,0,1,0,1,0,....,1,0$ and we may take the last pair of $(1,0)$ and make it a $1$. By induction hypothesis, since now it is $B$'s turn, $A$ wins.
If $n$ is odd and $B$ begins, the row is of the form $1,0,1,0,1,0,....,1,0,1$.
Player $B$ might pick a pair of the form $(1,0)$ or a pair of the form $(0,1)$, and replace this pair with a $0$ or a $1$. Note that doesn't matter what pair he chose to replace, there is either a $1$ right before it or a $1$ right after it: there is a $1$ after each pair of the form $(1,0)$ and there is a $1$ before each pair of the form $(0,1)$. Therefore the two numbers $B$ chose to replace are part of $3$ consecutive numbers in the row, which are $1,0,1$ (and $B$ chose either the first two or the last two of those three). Doesn't matter what $B$ did, we can make the $1,0,1$ that $B$ chose his pair from a $1$. For example, if $B$ chose the first two and made them a $0$, the $1,0,1$ became a $0,1$, which $A$ can make a $1$ from. Therefore, after $A$'s second turn, the difference from the original row is that a $1,0,1$ was replaced by a $1$. Now, since it is $B$'s turn now, by induction hypothesis $A$ wins.

$\endgroup$
2
$\begingroup$

We work modulo two. Let $n$ be even, and let $A$ start and play by adding the last two numbers, so that the remained numbers are in a "word" (of residues modulo two)... $$\ 1010\dots 01\ .$$ Now $B$ plays, and we show that $A$ can play again so that the pattern is kept. Indeed, $B$ plays so that the change appears in a subword either as $010\to 0x$, or $010\to x0$, or $101\to 1x$, or $101\to x1$. Here $x$ is a reside mod two, either $0$, or $1$. Then $A$ plays, changing the change of $B$, as follows: $$ \begin{aligned} &010\overset B\longrightarrow 0x\overset A\longrightarrow 0 =0\cdot x\ ,\\ &010\overset B\longrightarrow x0\overset A\longrightarrow 0 =x\cdot 0\ ,\\ &101\overset B\longrightarrow 1x\overset A\longrightarrow 1 \ni\{1\cdot x,1+x\}\ ,\\ &101\overset B\longrightarrow x1\overset A\longrightarrow 1 \ni\{1+x, 1\cdot x\}\ . \end{aligned} $$ So $A$ can always play so that when $3$ numbers remain, the pattern (mod two) is $101$, and from the above, when one numbers remains, the pattern (mod two) is $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.