Two players play the following game. There are 2 piles of stones. One pile consists of 4 stones and the other one consists of 6 stones. Players take turns one by one. The amount of stones is unlimited. During the turn a player can add 4 stones into one pile or multiply a number of stones by 2 in one pile. The player wins if there are more than 26 stones in either pile after his turn. Who will win in this game - the first player or the second player? What choices should the winning player make to secure the win?

It's like that -> 4,6 -> 4,12 -> 4,24 -> 4,28 (win) or 4,6 -> 8,6 -> 16,6 -> 32,6 (win).

I need a table that shows all the winning combinations. (I'm actually bad at maths, it's just that our school teachers thinks that we should be able to solve complex advanced problems, but I can't solve this one no matter how much I try.)

The answer must look like this (the captions are in Russian, so don't mind them): https://i.stack.imgur.com/rrC9d.jpg


The basic framework for thinking about combinatorial games is the P-position.

A P-position is a game state where the player whose turn it is will lose. An example of a P-position in your game is when both piles have 13 stones - the current player cannot win, but after their turn the next player is guaranteed a win.

The most important fact about P-positions is that, if you start from a P-position you cannot reach another, and if you are not at a P-position, then it's always possible to reach one with your move, thus guaranteeing a win.

As I mentioned above, $(13,13)$ is a P-position, as is $(m,n)$ whenever $m\geq 13$ or $n \geq 13$. Now you can work backward through the tree: any position that can "see" such an $(m,n)$ is not a P-position. By "see", I mean there exists a move that takes you to the P-position. Mark them all as such. Continue to work backward. Here's the first couple of steps to get you started:

Mark all $(m,n)$ that can see $(13,13)$ - these are not P-positions. enter image description here

Now you go backward through the rest of the squares, marking them either 'P' or not P. Make sure that when you mark a square, you've already marked all the squares it can see! Then the rule is easy: If it can see a P-position, then it isn't one, and if it can't, then it is.

Now every square can see exactly the following squares: the four immediately to its right, the four immediately above it, the one at twice its horizontal position and the one at twice its vertical position. For example, since $(12,12)$ can't see a P-position, it is one. Intuitively: whatever my opponent does with $(12,12)$, I'll be able to either win on my turn or leave them a $(13,13)$, i.e. a P-position. So mark $(12,12)$ as a P-position, and then mark all the squares that can see it as not P-positions:

enter image description here

Continue in this way, only marking a square when you have already marked all the squares it can see. The answer to your question: if the starting position is a P-position, then the first player will lose. If it is not, then the first player will win (by making a move that puts the game in a P-position).

  • $\begingroup$ But the game starts with (4,6), not (6,8). Anyway, thank you! $\endgroup$ – Victor Key Sep 25 '17 at 18:41
  • $\begingroup$ Haha sorry, Don't know how I made that mistake! I won't edit, because the solution method should still work. $\endgroup$ – dbx Sep 25 '17 at 18:46
  • $\begingroup$ By the way, if you feel that this satisfactorily answers your question, please consider marking it as such. $\endgroup$ – dbx Sep 25 '17 at 19:15
  • $\begingroup$ Using your answer I could solve this problem and got 5/5 at school today. Thank you! The winning strategy is 4,6 start -> 4,10 1st player -> 8,10 2nd player -> 12,10 1st player and then every turn means win for the first player. $\endgroup$ – Victor Key Sep 26 '17 at 3:53


I think a tree would be more understandable, something like this ...

enter image description here


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.