19
$\begingroup$

Note : the mechanisms described in this puzzle are related to those found in this question.

This is a game of 2 players.
Each player can pick up 1, 2, or 3 coins in any pile (copper , silver , gold) in their turn. The winning condition for a player is to pick up the last gold coin.
However, it is forbidden to empty a pile if there are non-empty piles of less valued coins.
(can't empty the gold pile if the silver pile is still non-empty)

At the start of the game, the initial number of coins on each pile is set as a random strictly positive number.
For each game, you have the undeniable advantage of deciding who goes first, between you and your opponent. Beware, he knows already all the tricks and will play perfectly.

Question : How can you win, given any possible combination, in the initial state ?

Example of a game :

[C1 | S4 | G1] you decide to go first  (S : -2)
[C1 | S2 | G1] he has 2 possibilities : (C : -1) or (S : -1)
[C0 | S2 | G1]  or  [C1 | S1 | G1] you respond adequally to make [0 1 1]
[C0 | S1 | G1] his turn (S: -1)
[C0 | S0 | G1] (G : -1) -> you win

Source : A stone minigame found in the video game Tales of Eternia (PSP).
The title "Master of stones" is actually granted to any player who can win this mini game.
Here, stones have been replaced by coins for differentiating the orders of the piles and the extra rule about non empty piles.

$\endgroup$
  • $\begingroup$ note : deciding to go first on the starting position [1 4 1] without the extra rule about non-empty piles is a guaranteed loss. $\endgroup$ – Anton Jul 20 '16 at 12:36
  • 2
    $\begingroup$ no, it is also a winning position, as I can, in my first move, take the last (and only) gold coin $\endgroup$ – BianB BB Jul 20 '16 at 14:01
  • $\begingroup$ @BianBBB Whoops, my bad. I had in mind that taking the last coin (out of all the piles) on your turn would be impossible, without thinking about just emptying the gold pile. :) $\endgroup$ – Anton Jul 20 '16 at 14:07
  • $\begingroup$ I'm confused -- a random number of stones is added to each pile of coins? $\endgroup$ – Mike Manfrin Jul 20 '16 at 19:25
  • $\begingroup$ @MikeManfrin It was the initial number of coins, I changed from the initial problem that used stones in order to not be ambiguous about the non-empty piles extra rule. I edited that in. $\endgroup$ – Anton Jul 20 '16 at 19:32
11
$\begingroup$

Let's forget about the "no emptying a stack until cheaper stacks are empty rule" for a second. In this case, the game is just three-stack Nim, except you can't remove more than three coins at a time. The solution is almost the same as Nim: compute the nim-sum C ⊕ S ⊕ G of the heap sizes, and choose to go second if and only if this sum is congruent to zero (mod 4). The winning strategy is to always ensure the sum stays zero (mod 4) after each of your moves.

Now, how do things change with the "cheaper stacks first" condition? The only difference is the bottommost gold and silver coins are sometimes illegal to remove. Let's put a mark on these two coins. By using the previous paragraph's strategy on the unmarked coins, you can ensure that you will remove the last unmarked coin. At this point, your opponent is faced with a single gold and silver coin, and loses.

The only slight hiccup is that even though you are ignoring the marked coins until the end, your opponent doesn't have to. Namely, he can remove the marked silver coin before all the unmarked gold coins are gone. If he does this, remove the number of unmarked gold coins the strategy specifies, plus the marked one.

Here is the conclusion:

You should choose to go second if and only if C ⊕ (S-1) ⊕ (G-1) is a multiple of four, where ⊕ denotes the nim-sum.

The winning strategy is to keep moving so this quantity stays a multiple of four.

$\endgroup$
  • $\begingroup$ Where did this G ± S + C black magic come from? A bunch of small cases? $\endgroup$ – ffao Jul 20 '16 at 21:10
  • $\begingroup$ @ffao Exactly! I happened to see a nice pattern which I couldn't explain, but could prove. $\endgroup$ – Mike Earnest Jul 20 '16 at 21:29
  • $\begingroup$ Given the end game playbook provided at the bottom, one can probably inductively derive those ± rules as a way of guaranteeing arrival at one of those winning states. $\endgroup$ – Ethan Jul 20 '16 at 21:53
  • $\begingroup$ To anyone who is like me wondering if this generalizes to a bigger number of piles: at least not easily :/ $\endgroup$ – ffao Jul 21 '16 at 5:49
  • 1
    $\begingroup$ @Reibello Yes. 0 is a multiple of 4, since 0*4=0. $\endgroup$ – Mike Earnest Jul 21 '16 at 15:20
8
$\begingroup$

You can determine if the initial hand is a losing one (and decide to not start).

The first losing hand is [0 1 1] and also all [4*k 1 1], [0 1+4k, 1], [0,1,1+4k] hands.

Every time it is necessary to make 2 moves to go to a losing hand, you have also a losing hand => [0+i 1+i 1], [0 1+i 1+i], [i 1 1+i].

Is [1 4 1] a losing hand? Not of the form of the losing hands, so no. You should begin.

Is [1 2 1] a losing hand? Of the form [0+i,1+i,1] with i=1, so yes. You should leave the opponent to begin the game.

Is [2 4 3] a losing hand? We can take an i of 2 => [0 4 1] which is not of the form [0 1+4k, 1], so it is a winning one. Breakdown of possible moves: [2 4 3] -> [2 1 3] -> { [1 1 3] or [0 1 3] or [2 1 2] or [2 1 1] } -> { [1 1 2] or [0 1 1] } -> { [0 1 2] or [1 1 1] or [0 0 1] } -> win this turn or make [0 1 1] and win on the next one.

$\endgroup$
  • $\begingroup$ pretty good start. Note that no pile contains 0 coins at start. $\endgroup$ – Anton Jul 20 '16 at 13:48
  • $\begingroup$ 1 4 1 appears to me to be a losing hand on start. Your first turn you a forced to take a copper (0 4 1). Your opponent will take 3 silver (0 1 1). You now have a losing hand. $\endgroup$ – Reibello Jul 20 '16 at 14:05
  • 4
    $\begingroup$ You are not forced to take a copper, take 2 silver instead and so you give a loosing hand to your opponent (this is the example given by Anton) $\endgroup$ – Laurent Jul 20 '16 at 14:07
  • $\begingroup$ Is there an easy way to create a losing hand from any non-losing hand ? maybe a formula that uses some modulus on C, S-1 and G-1... $\endgroup$ – Anton Jul 20 '16 at 15:38
4
$\begingroup$

You choose whether or not to go first, based on the results of the three piles modulo 4.

To 'win' a pile: if the # modulo 4 is 0, you want to go last, otherwise you want to go first.

To 'lose' a pile: if the # is 1 modulo 4, you want to go last, otherwise you want to go first.

Apply the following: To win the last pile, work out if you need to go first or last on it. This will tell you if you need to win or lose the preceeding pile. Apply this logic back to the first pile.

Play as follows to 'win' a pile: If this is the first move, and the pile has more than 4 stones, cut it down to 0 modulo 4. If this is not the first move, and the pile has more than 4 stones, play 4-x where x was the other player's preceeding move. If it's <4, finish it (if you can). (Note that it should never be 4 stones in your turn if you're playing to win and have chosen correctly)

Play as follows to 'lose' a pile: If this is the first move, and the pile has more than 5 stones, cut it down to 1 modulo 4. If this is not the first move, play 4-x where x was the other player's preceding move.

If you're going first, focus first on the first pile.

This technique will always ensure that you have the capacity to take (or give) the last stone. If your opponent attempts to divert onto other piles, it should be possible to just continue playing 4-x until you can force the pile to only contain 1, but I haven't proven that yet.

UPDATE:

Got it!

If your opponent starts another pile, you just have to make your second move take it to 0 or 1 modulo 4, as appropriate, depending on your goal for that pile.

The only issue with this now is if your opponent takes 1 or 2 from a pile of 4 that you can't finish yet. If this is the case, it's your move, so switch your objective on the first unfinished pile.

$\endgroup$
3
$\begingroup$

Every time you play, you play 4-number_of_stone_previously_played.

Well, we know that for if the gold pile is a multiple of 4, you want him to be first playing on it. Else, you start and leave the pile as a multiple of 4.

Now for silver row : if the gold % 4 = 0 you want to finish the pile of silver. Else you want to let him finish. So you want to start the pile of silver :

  • if gold%4 = 0 && silver%4 !=0 and leave the pile of silver as silver%4=0 (after you played)

  • if gold%4!=0 && silver%4=0

The choice on starting the pile i depends of either you want or not start pile i+1 and pile_i%4

Here is a table to sum up either stating or not : let's say (1,0,1) means copper%4=0, silver%4!=0 and gold%4=0 (ie pile%4=0 ->1 else 0)

here is how to make a table with all solutions : F means you have to finish pile , P mean opponent has to finish pile, S mean Start, N means play as second. let's file it from right to left.

( 1 , 0 , 1 ) ->  ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 ) -> ( 1 , 0 , 1 )  ->  ( 1 , 0 , 1 )
( | , | , |F)     ( | , | ,S|F)    ( | , |P,S|F)    ( | ,S|P,S|F)    ( |P,S|P,S|F)      (N|P,S|P,S|F)

because F under a 1 means you have to start. Starting means you have to NOT finish previous pile etc : (0,0,0) : opponent start (0,0,1) : we start (0,1,0) : we start (0,1,1) : opponent start (1,0,0) : time up i have to leave my pc (1,0,1) : (1,1,0) : (1,1,1) :

$\endgroup$

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.