10
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Another variant of Nim $\endgroup$ – ghosts_in_the_code Nov 2 '15 at 10:50
  • 10
    $\begingroup$ Unless I'm not quite getting the clue behind this, with optimal play they'll both die of old age before anyone wins... $\endgroup$ – Tim Couwelier Nov 2 '15 at 10:54
  • 1
    $\begingroup$ @Tim maybe Alice and Bob are computers. $\endgroup$ – Ian MacDonald Nov 2 '15 at 12:46
  • $\begingroup$ @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. $\endgroup$ – ghosts_in_the_code Nov 2 '15 at 14:23
  • 3
    $\begingroup$ 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. $\endgroup$ – Ian MacDonald Nov 2 '15 at 15:23
15
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – The Dark Truth Nov 2 '15 at 15:51
  • $\begingroup$ @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. $\endgroup$ – Sleafar Nov 2 '15 at 16:01
3
$\begingroup$

Second (but completed) answer, once again building of Sleafar's answer.

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – glibdud Nov 3 '15 at 1:42

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.