9 replies to this topic

[Anza Power]

This was sent to me by a friend...

2 players play a game where an infinity 1-dimentional board is divided into cells numbered 0 1 2...

4 coins are placed on some cells in this board, the second coin from the left is gold:


(the position of the coins in this picture is just for show)

The players take turns, each player chooses one of the four coins and moves it 1 or more cells to the LEFT, you cannot surpass a coin or land on the same cell.

If you move a coin beyond the leftmost cell it is taken out of the game, whichever played takes out the gold coin wins...

So in the above example the player who's turn it is could either move the leftmost coin 1 cell or take it out by moving it 2 cells, or move the gold coin 1 or 2 cells, or move the third coin 1 cell, or move the fourth coin 1 2 or 3 cells...

Develop a strategy for winning the game given the initial positions of the coins...

[bonanova]

Interesting puzzle!

 

Spoiler for Analogy

 

Great similarity to the Game of Nim.

 

Consider the coins as piles, and leftward spaces as objects in the piles.

If you play to empty all the piles after one of your moves, 

you transform the configuration

 

from _ X _ _ O _ X _ _ _ X _ _ _ _ _ _    into X O X X _ _ _ _ _ _

 

Your opponent is then forced to remove the leftmost X, allowing you to remove the winning O.

 

For other numbers of coins, and arbitrary positioning of the gold coin,

the above holds for any odd number of X to the left of O.

But for an even number, you would play so it's your turn to move next.

 

But, for the general case, there are two huge wrinkles.

1. The number can change between odd and even as Xs are removed.
    
2. In Nim you only decrease the size of a pile.
   Here, moving a coin decreases the number of spaces in front of the
   moved coin, but it also increases the number of spaces behind it.

So [1] you may have to switch between "losing" and "winning" strategies,

and [2] the strategy is modified from standard Nim game play.

 

OK, enough of general thoughts. I don't know how you would do either of these things.   

 

Now to solve the specific case in the OP.

[bonanova]

Spoiler for Solution

Name the four coins, left to right, X1 O X2 X3.
Represent the game position by the number of leftward-adjacent empty spaces.
The initial position is thus (1213).

Removing X1 loses the game, since opponent can then remove O.
Removal of X1 is forced by the game position (0000).
Define any move made prior to that position a safe move.

The maximum number of safe moves [that is the case where each coin is moved only a single space] is 1+3+4+7 = 15.

Note that 1 3 4 7 are the partial sums of (1213).

In any game position, the partial sums sum to the maximum number of remaining safe moves.

 

The fewest safe moves [one for each coin, starting with X1] is 1+1+1+1 = 4.

In any game position, the minimum number of remaining safe moves is simply the number of coins

that have any [not necessarily adjacent] empty spaces to their left.

If only single-space moves are made, (1213) is a winning position for the first player.
But more generally, if the first player can force the number of safe moves to be any odd number, he will win.
That is, player 1 wants to make the last safe move.

 

He can do this by making a symmetrical position with his first move.

If he maintains symmetry by appropriately mirroring each of P2's subsequent moves,

then the total number of safe moves in the game will be odd, and P1 will win.

 

That is, (1213) would then be a winning position for the first player using moves of any type.

Spoiler for Notation for game having 15 safe moves

    0.  1 2 1 3  _ X _ _ O _ X _ _ _ X  (starting position)

1. 0 3 1 3  X _ _ _ O _ X _ _ _ X
2. 0 3 0 4  X _ _ _ O X _ _ _ _ X
3. 0 3 0 3  X _ _ _ O X _ _ _ X
4. 0 3 0 2  X _ _ _ O X _ _ X
5. 0 3 0 1  X _ _ _ O X _ X
6. 0 3 0 0  X _ _ _ O X X
7. 0 2 1 0  X _ _ O _ X X
8. 0 2 0 1  X _ _ O X _ X
9. 0 2 0 0  X _ _ O X X
10. 0 1 1 0  X _ O _ X X
11. 0 1 0 1  X _ O X _ X
12. 0 0 1 1  X O _ X _ X
13. 0 0 1 0  X O _ X X
14. 0 0 0 1  X O X _ X
15. 0 0 0 0  X O X X

 

Spoiler for Winning strategy

Player 1 moves first and wins.

 

First move:

P1 creates a maintainably symmetric position by moving coin X1 to the left (0313): X _ _ _ O _ X _ _ _ X.

P2 must now move coin O, X2, or X3.  In each case, P2 can be forced to lose.

Case1. P2 moves O.

 

P1 will move coin X3 similarly: one, two or three spaces.
 
1a. Three spaces. (0043): X O _ _ _ _ X _ _ _ X.  P1 moves X3 three spaces (0040) X O _ _ _ _ X X.

P2 can only move X2. P1 moves X3 similarly, maintaining (00s0).
Eventually s becomes 0 (0000).

P2 must remove X1. P1 removes O and wins.

Keeping a list of positions that P1 can create that will lead to a win for P1.

(00sr) can force (00s0) which can force (0000), which wins for P1.

1b. Two spaces. (0133): X _ O _ _ _ X _ _ _ X.  P1 Moves X3 two spaces (0131) X _ O _ _ _ X _ X.
P2 cannot move X3 next to X2 (0130) or P1 will move O next to X1 (0040) which loses for P2.
P2 cannot move O next to X1 (0041) or P1 will move X3 next to X2 (0040) which loses for P2.
P2 must move X2. But then P1 will move X3 simlarly, maintaining 01r1.
Eventually r reduces to 0: (0101) like X _ O X _ X.
P2 must now move X3 (0100) or O (0011). P1 moves the other coin (0010) and wins.

So 01r1 can force 0101 which can force 0010 which wins.

1c. One space. (0223): X _ _ O _ _ X _ _ _ X. P1 moves X3 one space (0222) X _ _ O _ _ X _ _ X.
If P2 moves O or X3,  P2 will move the other of the two coins similarly (0131) or (0040) and win.
P2 must move X2. P1 will then move X3 similarly, maintaining 02s2 and eventually (0202) X _ _ O X _ _ X.
P2 must move O or X3. P1 will move the other similarly, two or one spaces.
If two spaces, 0000 and P1 wins.
If one space, 0111 X _ O _ X _ X.
If P2 moves O (0021) or X3 (0110) P1 moves the other, making 0020, and win.
If P2 moves X2 (0102) P1 moves X3 (0101) and wins.

So 0222 can force 0131, or 0040, both of which win.

 

Case 2. P2 moves X2  (0304). This is the only move possible for X2. 

 

P1 moves X3 one space (0303) X _ _ _ O X _ _ _ X.

P2 can only move O or X3; one, two or three spaces.

2a. Three spaces (0033) or (0300). P2 moves the other coin similarly (0030) and wins. (1a.)

2b: Two spaces (0123) or (0301). P2 moves the other coin similarly (0121) and wins. (1b.)

2c: One space (0213) or (0302). P2 moves the other coin similarly (0212). This is a new position.
If P2 moves O (0032) or X3 (0210) two spaces, P2 moves the other similarly (0030) and wins. (1a.)
If P2 moves O (0122) or X3 (0211) one space, P2 moves the other similarly (0121) and wins. (1b.)
So P2 must move X2 (0203). P1 moves X3 one space (0202) and wins. (1c.)

 

Case 3. P2 moves X3.

 

P1 moves coin O similarly, one, two or three spaces.

3a. Three spaces: (0310) X _ _ _ O _ X X.  P1 moves O three spaces (0040) and wins. (See 1a.)

3b. Two spaces: (0311) X _ _ _ O _ X _ X. P1 moves O two spaces (0131) and wins. (See 1b.)

3c. One space: (0312) X _ _ _ O _ X _ _ X. P1 moves O one space (0222) and wins. (See 1c.).

[Anza Power]

^ bonanova excellent you got it, the game isn't about the general case, you know you only have 4 coins and the second one from the left is the golden one, only thing that can change is the position of these coins...

Your explanation is a bit lengthy though, all you need to do is:

Spoiler for

Keep the distance between the first 2 coins the same as the distance between the last 2 coins, you can easily check for every case depending on what coin the opponent chose to move you can fix the situation, eventually all 4 coins would end up jammed in the left and the opponent would have to push the silver coin out...

Edited by Anza Power, 07 January 2013 - 08:13 PM.

[bonanova]

First player always wins then?

[k-man]

First player always wins then?

Spoiler for Except...

...cases when the initial setup already has the equal distance between 1-2 and 3-4. In those cases the second player wins.

[Prime]

^ bonanova excellent you got it, the game isn't about the general case, you know you only have 4 coins and the second one from the left is the golden one, only thing that can change is the position of these coins...

Your explanation is a bit lengthy though, all you need to do is:

Spoiler for

Keep the distance between the first 2 coins the same as the distance between the last 2 coins, you can easily check for every case depending on what coin the opponent chose to move you can fix the situation, eventually all 4 coins would end up jammed in the left and the opponent would have to push the silver coin out...

 

Spoiler for General rule?

This puzzle looks like one-dimensional Nim. Except, the moves are limited by available space on the left of each coin. Thus the XOR formula does not work. It seems, the formula given by AP works for that particular case.
It is similar to the XOR rule for the Nim in this way:
You cannot convert a position conforming to the rule into another position that also conforms to the rule by any legal move.

How would you play the game if there were more than 4 coins, and/or the gold coin was in a different position, like 3rd or 4th?

[bonanova]

First player always wins then?

Spoiler for Except...

...cases when the initial setup already has the equal distance between 1-2 and 3-4. In those cases the second player wins.

 

k-man, Great observation.   Anza Power, very interesting puzzle.

[Prime]

Interestingly enough, the XOR formula inhabits this game, like it does Nim.

Consider a bit more complex variation: two copper coins on the left, followed by gold coin, followed by two more copper coins.

 

Spoiler for XOR rules!

Let’s call the coins C1, C2, G3, C4, and C5. The left edge of the board is E. A number shall represent the maximum number of squares a coin can move to the left until it is stopped by another coin on the left, or goes off the board in case of the C1.
For example, if C1 is on the leftmost square, then E-C1=1; If there are 3 empty squares between C1 and C2, then C1-C2=3. Finally, let X designate an arbitrary number (several X-s in a position specification need not be equal to one another.)

Here is an example of a key position, from which the player whose move it is shall lose, provided the opponent plays correctly:
E-C1=1, C1-C2=X, C2-G3=0, G3-C4=X, C4-C5=1.
Meaning, the first coin is on the leftmost square, second coin could be any number of squares to the right, gold coin is right next to it, then the fourth coin sits any number of squares to the right, and the fifth coin has exactly one vacant square between itself and the fourth coin. Or graphically: C.....CG..........C_C

Omitting the symbol on the left, e.g. C2 instead of C1-C2, the following is a table of some key positions:

C1 C2 G3 C4 C5
.1....X...0....X...1
.1....X...1....X...0
.1....X...2....X...3
.1....X...3....X...2
.1....X...4....X...5
.1....X...5....X...4
...........................
.2....X...0....X...2
.2....X...1....X...3
.2....X...2....X...0
.2....X...3....X...1
.2....X...4....X...6
.2....X...5....X...7
.2....X...6....X...4
...........................
.3....X...0....X...3
.3....X...1....X...2
.3....X...2....X...1
.3....X...3....X...0
.3....X...4....X...7
.3....X...5....X...6
..........................

If you convert numbers in the above table to binary and perform XOR operation between three numbers in each row, you will get zero every time. And that’s the formula for a key position!
How do we pick the intervals that count as opposed to those marked here with “X”? We just pair the coins starting from the rightmost. In this example C5-C4, G3-C2, and C1-E are the intervals that count. Why? A good explanation evades me at the moment. However, consider, for example, a key position 3..X..5..X..6. Let’s say, from that position the losing side moved C2 two spaces left resulting in 3..X..7..X..6. Now the winning side can restore 3..X..5..X..6 by moving G3 two spaces to the left.

The property of a key position is that you can never get another key position from it by a single move. The property of a non-key position is that you can always get a key position from it by a single move. The XOR operation magically works for the purpose of formally defining a key position.

The problem in the OP is subject to the same rule. It’s a special case, where only 4 coins are present and C2-G3 and C4-C5 are the only two intervals that count. Having equal number of spaces in those intervals XOR-s to zero.

Presently, I cannot invest an effort into formally proving that general formula. Feel free to prove or disprove it, as the case may be.  

[Prime]

A finishing touch...

 

Spoiler for The general formula

And the formula is......

When you XOR all significant intervals and the result is zero, that is a key position, from which whoever moves must lose the game, provided the opponent plays correctly.
XOR is a binary operation defined as following:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
Therefore, for ease of calculation convert all significant intervals to binary.

 

Significant intervals are defined as following:
Pair up neighboring coins starting with the rightmost one. For odd number of coins the leftmost coin must be paired with the left edge of the board. For example, 6 coins must be paired like so: .....c1-c2....c3-c4......c5-c6; whereas 5 coins must be paired: E-c1...c2-c3....c4-c5, where “E” is the edge of the board.
An interval between the coins of each pair is the number of vacant squares between them. It is called "significant interval" herein. For the leftmost coin (c1) the interval between it and the edge of the board (where applicable) is the number of vacant squares to the left of c1 plus one. However, in the case where the second coin (c2) is the gold coin, and the E-c1 interval is applicable (odd number of coins,) the interval E-c1 shall be just the number of vacant squares to the left of c1.

For example:
_ _ C ..... C _ _G.....C _ C, where the intervals (left to right) are: 3, 2, and 1 (losing on your move);
_ _ C ..... G _ _C.....C _ C, where the intervals (left to right) are: 2, 2, and 1 (must win on your move by moving the very last coin one space).

The intervals outside "pairs" don't matter.

Finally, I must note, there are no significant intervals when the gold coin is the first coin on the left. Just grab it!

The winning strategy is simple: just make sure that after your move all significant intervals XOR to zero. And if you cannot do that – don’t bet money or valuables on the outcome.

Proof:
1). Any terminal position, where your opponent has just one possible move, after which you take the gold coin, conforms to the zero XOR rule.
2). From any position not conforming to zero XOR, you can always obtain a conforming position with a single move.
3). From any position conforming to zero XOR, you can never obtain another conforming position with a single move.

The reason for constructing significant intervals starting with the rightmost coin is, that you cannot leave the last coin hang unpaired. If you did, then one could move it without affecting any significant intervals in violation of the point (3) of the proof above.

 

Armed with this knowledge, you could make a bet, whereby first your opponent sets up any position and then you choose who moves first.