A game of 2's

Reading the question, we find that this is a game. Obviously, the first thing everyone solving this should do is to

$\huge \text{Play the game!}$

Let's try a few smaller values and see what we get. (The first column represents the player who has just taken coins, and $n$ represents the number of coins in the pile)

$\begin{array}{c|c|c} \text{Player} & \text{Operation} & n\\ \hline \text{Start} & \text{ } & 22\\ \text{Sharky} & 1 & 6\\ \text{Ivan} & 2 & 3\\ \text{Sharky} & 1 & 1\\ \end{array}$

Notice that Ivan can't play any operation on 1 since it is both a power of 2 and odd. We observe that the winner will make $n=1$ . Thus, Sharky won if Ivan had used the first operation. Let's see what happens if Ivan had used the other operation.

$\begin{array}{c|c|c} \text{Player} & \text{Operation} & n\\ \hline \text{Start} & \text{ } & 22\\ \text{Sharky} & 1 & 6\\ \text{Ivan} & 1 & 2\\ \text{Sharky} & 2 & 1\\ \end{array}$

So it seems Sharky has the winning strategy for 22. Let's try more numbers!

$\begin{array}{c|c|c} \text{Player} & \text{Operation} & n\\ \hline \text{Start} & \text{ } & 28\\ \text{Sharky} & 1& 12\\ \text{Ivan} & 2 & 6\\ \text{Sharky} & 2 & 3\\ \text{Ivan} & 1 & 1\\ \end{array}$

In this case, it seems Ivan won. Using our previous game, we know 6 is a losing position for the person who's about to remove coins from it. Thus, we don't need to investigate Sharky's second move. What about his first move though?

$\begin{array}{c|c|c} \text{Player} & \text{Operation} & n\\ \hline \text{Start} & \text{ } & 28\\ \text{Sharky} & 2 & 14\\ \text{Ivan} & 1 & 6\\ \text{Sharky} & 2 & 3\\ \text{Ivan} & 1 & 1\\ \end{array}$

Here, we find almost the same position yet again! Thus, we know Ivan has a winning strategy for 28.

If you keep playing this for different values of $n$ , you might observe some sort of pattern. However, how would you prove it? Think about this, then keep reading down to find out a great strategy for solving this.

---

If you were thinking about converting $n$ to binary, you are correct in thinking so. Motivation for thinking about this is because you are either subtracting the greatest power of 2 from it, which translates in binary to removing the first digit 1 (if there exist other non-zero digits), or halving it, which translates in binary to removing the last digit 0 (if it exists). These both feel like easy operations to deal with. Let's analyse the above games with a conversion to binary to see what's happening.

$\begin{array}{c|c|c|c} \text{Player} & \text{Operation} & n & \overline{n}_2\\ \hline \text{Start} & \text{ } & 22 & 10110\\ \text{Sharky} & 1 & 6 & 110\\ \text{Ivan} & 2 & 3 & 11\\ \text{Sharky} & 1 & 1 & 1\\ \end{array}$

$\begin{array}{c|c|c|c} \text{Player} & \text{Operation} & n & \overline{n}_2\\ \hline \text{Start} & \text{ } & 22 & 10110\\ \text{Sharky} & 1 & 6 & 110\\ \text{Ivan} & 2 & 2 & 10\\ \text{Sharky} & 1 & 1 & 1\\ \end{array}$

$\begin{array}{c|c|c|c} \text{Player} & \text{Operation} & n & \overline{n}_2\\ \hline \text{Start} & \text{ } & 28 & 11100\\ \text{Sharky} & 1& 12 & 1100\\ \text{Ivan} & 2 & 6 & 110\\ \text{Sharky} & 2 & 3 & 11\\ \text{Ivan} & 1 & 1 & 1\\ \end{array}$

$\begin{array}{c|c|c|c} \text{Player} & \text{Operation} & n & \overline{n}_2\\ \hline \text{Start} & \text{ } & 28 & 11100\\ \text{Sharky} & 1& 14 & 1110\\ \text{Ivan} & 2 & 6 & 110\\ \text{Sharky} & 2 & 3 & 11\\ \text{Ivan} & 1 & 1 & 1\\ \end{array}$

From here, we can see that the first operation can only be applied $a-1$ times, where $a$ signifies the number of 1's in the binary representation of $n$ , and also that the second operation can be applied $b$ times, where $b$ signifies the number of terminating 0's in the binary representation of $n$ .

Observe that after each move, the sum $a+b$ decreases by 1. Thus, after both Sharky and Ivan have their turns, $a+b$ decreases by 2. Therefore, we must have $a+b$ constant in $\pmod{2}$ after Sharky and Ivan have made their moves. This simplifies the problem dramatically. We also note from previously that if $n=1$ , then the next player loses.

If $a+b$ is odd, then we must have $a+b\equiv 1\pmod{2}$ . After Sharky and Ivan keep making their moves, eventually, Ivan will have made $n$ to be equal to 1. Thus, Ivan wins if $a+b$ is odd. Similarly, if $a+b$ is even, Sharky wins.

We have solved the general case!

To solve for $n=420$ , we note $\overline{n}_2 = 110100100$ , which has $a=4$ and $b=2$ , so $a+b$ is even. Thus, Sharky is the winner.

Please let me know if there are mistakes in my reasoning:

For me, I see 420 = 2^8 + 2^7 + 2^5 + 2^2

Operation 1 is equivalent to removing the 1st term (the left most one). Operation 2 is equivalent to reducing the powers of every term by one.

The game comes to an end when a player is left with exactly one coin, which is the only situation where no legal moves are possible.

Operations 1 or 2 may be carried out in any order, but operation 2 will be executed exactly *twice * (need not be consecutively), after which the last term ends up becoming 1, making the sum to be odd and therefore making it impossible to perform operation 2 according to its rule. As for operation 1, it will be executed exactly 3 times , after which there will only be 1 term left.

Hence, after exactly 5 moves (3 times of op. 1 and 2 times of op. 2 regardless of order), only 1 coin will be left. The player who has to make the 6th move will not have a legal move and will therefore lose the game. Since 6 is an even number, the one who makes the first move will win. Congratulations, Sharky!

Not such an elegant, general solution, but all roads seem to lead rapidly to a Sharky win!!

Step 0....S .....................420

Step 1....I.............164 .......or........ 210

Step 3...S......... 26...or..........82....or....105

Step 3...I .........13...or...10,......18...or....41

Step 4...S.............5......or....2.......or .... 9

Step 5....I ...........................1!!!!

There is no winning "strategy" in a sense-- no matter what choices the player makes, Ivan will lose at his third turn.

Let $N$ be the number of coins in the heap, and resolve it in the form $N = \sum_{k \in S} 2^k,$ where $S$ is a set of non-zero integers. In this case, $N = 420 = 2^8 + 2^7 + 2^5 + 2^2$ so that $S = \{8,7,5,2\}$ .

Let's consider the effect of each valid moves on the set $S$ : they are

• remove the largest value from $S$ , provided $|S| > 1$ ;

• subtract one from each element of $S$ , provided $0 \not\in S$ .

The first operation will decrease $|S|$ (the number of elements in $S$ ) by one but not affect $\min S$ ; the second operation will decrease $\min S$ by one, but not affect $|S|$ . Therefore the characteristic value $c = |S| + \min S$ will decrease by one in every turn. Moreover, a player can only lose if both $|S| = 1$ and $0 \in S$ , i.e. when $c = 1$ . Therefore, given an initial situation with characteristic $c$ , we know that there are $c - 1$ moves before the game ends.

In this situation, $c = 4 + 2$ , so that there are $5$ possible moves before $\boxed{\text{Ivan}}$ loses.

This is no match for Sharky's lovely solution of the general case, but more modestly solves the game from the specified starting point.

We can start with three observations and then show that $\boxed{\text{ Sharky }}$ has a winning strategy.

First note that if there is one coin in the pile there is no legal move.

Next note that if the pile has more than one coin there will be a legal move.

These two observations together show that the loser will be the first person confronted with a pile containing one coin.

Finally note that once there is an odd number of coins in the pile, the number of coins remains odd for the rest of the game. This is because move-option 2 is not permissible and move-option 1 involves subtracting an even power of 2. An odd number minus an even number always produces another odd number. So once there is an odd number of coins in the pile, the moves of both players are forced to be move-option 1.

Now here is Sharky's strategy. He should half the number of coins leaving 210 coins. Now if Ivan halves the number to leave 105 in the pile we are onto an odd number chain and there are no more choices to be made. The sequence goes

420-210-105-41-9-1

If instead of halving the 210, Ivan takes away 128 coins, Sharky should halve the result which switches the game onto the odd number track. The sequence now goes

420-210-82-41-9-1

Both of these sequences have five moves, so the next move is Ivan's. But since he is confronted with a pile of one coin he has no legitimate move and so looses the game.

Not that we really need another solution, but the 3 by 4 grid below shows all the possible states:

420 & 164 & 36 & 4

210 & 82 & 18 & 2

105 & 41 & 9 & 1

At any state there are two possible moves: to the right or down. Subtracting the largest power of two is a move to the right. Dividing by two is a move down. These moves commute with each other, i.e. subtracting the largest power of two followed by a division by two leads one to the same point as doing the same operations in the opposite order. Of course if I listed all the numbers by their binary representation, the nature of the grid would be more obvious.

110100100 & 10100100 & 100100 & 100

11010010 & 1010010 & 10010 & 10

1101001 & 101001 & 1001 & 1

The move to the right is accomplished by removing the leading '1' while the move down is accomplished by removing the last '0'.

I got it right with what i could understand, but want to make sure i understood correct,

Given k = 420, largest power of 2 < k = 2^8 = 256

1. Given Sharky is going to start first, he can remove 256 coins. which leaves us with 420 - 256 = 164
2. Ivan is left with 164 and can remove max of 128 which is 2^7 which leaves remaining coin count to 164 - 128 = 36
3. Sharky now left with 36 coins can remove 2^5 = 32, with 4 coins remain
4. Ivan now left with 4 coins can make a legal move by removing 2^2 = 4 leaving 0 coins.
5. Sharky cannot make any legal move now,

Am left with 2 questions, what is a winning strategy here? And why Sharky is on Winning Strategy?

For a person to lose, they must either end with a odd number

We immediately notice that removing a power of 2 does not "remove a two", that is, cause the number to lose a power of two. We also notice

420=2^2 3 5*7

thus, Sharky will always have the upper hand by forcing Ivan to have a odd number.