2
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ But the game starts with (4,6), not (6,8). Anyway, thank you! $\endgroup$
    – Victor Key
    Sep 25, 2017 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$ Sep 25, 2017 at 18:46
  • $\begingroup$ By the way, if you feel that this satisfactorily answers your question, please consider marking it as such. $\endgroup$ Sep 25, 2017 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, 2017 at 3:53
1
$\begingroup$

HINT

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

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .