# Ninety-nine non-negative numbers

Alice and Bob play the following game with $99$ numbers $M_1,\ldots,M_{99}$.

• In the beginning, the $99$ numbers take the values $1,2,4,8,16,\ldots,2^{97},2^{98}$.
• Then Alice and Bob alternatingly make moves; Alice makes the first move.
• In every move, the active player picks five numbers $M_a,M_b,M_c,M_d,M_e$ (with five distinct indices $a,b,c,d,e$) and decreases each of them by $1$.
• If one of the numbers becomes negative, the game ends. The player who has caused this loses, and the other player is declared winner.

Question: Which player has a winning strategy? (As usual, we assume that Alice and Bob use optimal strategies.)

• Another variant of Nim Nov 2, 2015 at 10:50
• Unless I'm not quite getting the clue behind this, with optimal play they'll both die of old age before anyone wins... Nov 2, 2015 at 10:54
• @Tim maybe Alice and Bob are computers. Nov 2, 2015 at 12:46
• @IanMacDonald Even that is impossible. $2^{98}\approx3.2\times 10^{29}$. If a computer plays $10^{15}$ moves per second (impossible in today's technology), and there are $3\times 10^7$ seconds in a year, it would still take millions of years to finish the last number. Nov 2, 2015 at 14:23
• So what you're saying is that we need a computer the size of a planet that's dedicated to answering a single question after millions of years of processing? I feel like I've read this book. Nov 2, 2015 at 15:23

## TL;DR

The first player should decrease $M_1$, $M_{96}$, $M_{97}$, $M_{98}$, $M_{99}$ in the first move. Afterwards he can repeat all moves of the second player to win.

This is guaranteed to work because the numbers $M_1 .. M_{95}$ are all even after the first move, and each of the numbers $M_{96} .. M_{99}$ is bigger than the sum of all numbers $M_1 .. M_{95}$. At the end all numbers $M_1 .. M_{95}$ will be $0$, and the numbers $M_{96} .. M_{99}$ will be positive with the second player to move.

The rest of the post describes how I came to the conclusion above.

## Closer look

Let's make two groups of numbers $M_1 .. M_{95}$ and $M_{96} .. M_{99}$:

$\begin{array}{} M_1 & M_2 & M_3 & ... & M_{95} & \qquad\qquad & M_{96} & M_{97} & M_{98} & M_{99} \\ 1 & 2 & 4 & ... & 2^{94} & \qquad\qquad & 2^{95} & 2^{96} & 2^{97} & 2^{98} \end{array}$

The sum of the numbers $M_1 .. M_{95}$ is $2^{95}-1$ which is smaller than $M_{96}=2^{95}$. Even if we would decrease all numbers $M_{96} .. M_{99}$ in each move, they will stay positive until the end of the game.

## Changing the rules

This allows us to create an equivalent game with slightly different rules. First we get rid of the numbers $M_{96} .. M_{99}$. Second we change the move rule to the following:

- In every move, the active player picks between one and five numbers and decreases each of them by $1$.

This game is equivalent to the original game, because we can decrease the missing one to four numbers from the group $M_{96} .. M_{99}$ without changing the outcome of the game.

## Winning position

Let us assume we have a position where all numbers are even numbers. In such a position it is always possible to repeat the move done by the previous player reaching again a position where all numbers are even numbers. At some point the first player will run out of possible moves and the second player wins.

## How to win?

The first player can decrease the number $M_1=1$ (and $M_{96} .. M_{99}$ in the original game) and reach the winning position from the previous chapter (he will be then the second player).

• Great solution I would say. Theres just one point that I think is wrong: your assumption of "all differences between numbers being even" should be "all numbers being even". Imagine having the numbers 1 3 5 left (it shouldn't happen for this specific question). Your assumption of all differences being even would be true in this case but the first player would be able to win by first making all numbers equal and then following your strategy. Just changing this should still let your solution work. Nov 2, 2015 at 15:51
• @TheDarkTruth I meant that the difference from 0 to the lowest number has to be even as well, but your definition is simpler, so I changed the answer accordingly. Nov 2, 2015 at 16:01

Alice wins

How?

If we disregard M96-M97-M98-M99, and therefor consider each turn as removing 'one to five' units from the remainder, eventually said remainder will run out. If someone gets to a point where the remainder is dividible by six, they just let the other player pick 1 to 5 from the 'remainder', and on their pick, they pick 6 - (whatever the other did), so after each two turns, the net value of the remainder goes down by 6, therefor always remaining dividable by 6.

In the limit case, all M1 to M95 will be depleted after a such move, meaning the other player only gets to pick 4 from M96-M99, and needs to turn one negative.

Now can Alice force the wining postion on the first try?

YES. The only way she couldn't, is if the initial amount were dividable by 6. Given it's an odd number (due to M1), she can always force the win.

• This makes sense, but only applies as long as there are at least 6 numbers left in the "remainder". After that, there'll need to be a change of strategy, as the player who's been in control is no longer guaranteed to be able to take 6-n from the remainder. Nov 3, 2015 at 1:42