Fog Creek Software
Discussion Board




matchsticks puzzle

there are 16 matchsticks arranged in 4 rows
                                        1                        row 1
                                    2  3  4                    row 2
                                5  6  7  8  9                row 3
                        10 11 12 13 14 15 16        row 4

A player can remove as many matchsticks he wants but all from a particular row(he gets to chose any row). The player who removes the last stick wins. If two players play this game alternatively by removing sticks in the way described above what would be the strategy the players should follow to maximize their winning chances (i.e try not to lose, ofcourse one of the players has to lose but it should be decisive, in the sense player 1 wins becouse he starts to play first and follows the strategy all along the game).

Abyss
Wednesday, June 22, 2005

hint: player 1 can never win if player 2 plays optimally.

i.e player 1 is presented with a losing position

Abyss
Thursday, June 23, 2005

initial state: 1, 3, 5, 7

break this up into binary and see that:
there is an even number of bits set in the 1's column
there is an even number of bits set in the 2's column
there is an even number of bits set in the 4's column

Call this state, "equivalent-to-zero"

Whatever player 1 does, the state will not be equivalent to zero. Then player 2 can always ensure the state will be equivalent to zero (may take a few minutes to convince yourself of this). Player 2 will eventually win if he keeps the state equivalent to zero.

WanFactory
Thursday, June 23, 2005

that was a good one wanFactory

the puzzle was actually a take on the popular game called NIM.

it can be extended to any number of rows with any number of matchsticks.

i hope the below helps for puzzles of similar nature

If a1, a2....,ai,...an  denote the number of  matchsticks then the winning move should leave

(1) a1 ^ a2 ^ ...ai ...^..an = 0.

where ^ denotes XOR operation - which applies bitwise to the binary representation of two or more numbers.

Now, bit is a position in a binary representation. There is a 0th bit (the rightmost one), the next is 1st, and so on. A bit is said to be turned on if the corresponding digit is one. Otherwise, it's turned off. The relationship (1) is equivalent to saying that, considering all 'n' numbers (o.e for every row), every bit is turned on an even number of times, i.e., either 0 or 2.

Here is a word proof. First of all, if after your move (1) holds while a1, a2.., ai, an are not 0, your opponent can't win on the next move. Condition (1) assures that for every bit turned on there is another bit on but in a different row. Since at every turn a player is allowed to remove matchsticks only in one row, it is impossible to turn all the bits off in one move.

for a mathematical explanation of above refer to

http://web.usna.navy.mil/~wdj/book/node10.html

Abyss
Thursday, June 23, 2005

I played NIM when I was a kid. I even remember playing a text-version of the game on the PET computers.

WanFactory
Thursday, June 23, 2005

Well for those who know NIM i have a more interesting puzzle or shall i say something to test the real understanding of their introductory combinatory theory.

this is just a self introspective measure of how much we have really tried to improve on our understanding abilities of impartial games especially after knowing the logic of how NIM is played from a young age.

here we go...

we have a game of Nim-Square : as in Nim, we start with some piles of stones. Two players A and B alternately remove a number of stones from any single pile, as long as the number of stones removed is a perfect square.

can it be proved that a nim square game with a configuration of (18, 26, 28) is equivalent to a game of nim which starts with (1, 2, 4).

Abyss
Thursday, June 23, 2005

the above problem is just for the fun of it..i cant really call it a puzzle but a good one to to put our thought on for the inquisitive of the minds.

i enjoyed trying to solve the problem..hope it gives the same pleasure to you all.

Abyss
Thursday, June 23, 2005

Hello Abyss,
you point is not clear to me....?
(1) a1 ^ a2 ^ ...ai ...^..an = 0.
if this hold it need not necessary that the player 2 wins?
lets take an example.....

                            1
                        2 3 4

if player 1 choose 2,3 .... you dont have the change to even win......
I think you statement is not generic or something is missing (atleast in my interpretation.????


Deepak pant (ST micro.)
               


       

Deepak pant(STM)
Saturday, June 25, 2005

Deepak - (1) is just a condtion for a winning move.

it could be made by either players ... if player 1 makes a move leaving the state of the game in a situation where (1) holds - an example is the situation you have taken...then there is no way for player 2 to win ..if player 1 plays optimally..by optimal we mean every move player 1 tries to keep the game in a state where (1) holds


to be more clear ..as in your example

          1
      2 3 4

lets analyse the game step by step so you understand the condition

at first row 1 has 1 matchstick and row 2 has 3

expressing in binary

row 1        - 001
row 2        - 011

row 1 XOR row 2 is not zero....as  column 2 has odd number of bits as 1 because of row 2 value = 3..this means player 1 that is the player who is going to make the move is in advantageous postion becaeuse he can make a winning move to leave the game in a state where

row 1 XOR row 2 is zero

this he makes by removing any two sticks from row 2..which leaves the game in a state where (1) holds and makes player  2 lose

so if the game started with the above matchstick position then the player who is about to make the move wins (here we give him player 1)


but for the original question where the arrangement was

row 1            001 
row 2            011 
row 3            101
row 4            111

here row1 XOR row2 XOR row3 XOR row4 = 0
player 1 is already presented with a losing position....
so if player 2 plays optimally he will always win..

i hope i have made things clear

to put it in short -  condition 1 is just a criteria for a winning move or alternately give your opponent a losing position

Abyss
Saturday, June 25, 2005

Deepak,

in your example of:
a1: 1,        = 1
a2: 2,3,4  = 3

we find that a1 ^ a2 != 0
this means that player 1 can always win by making a move such that a1 ^ a2 = 0.

In the original problem a1 ^ a2 = 0
which a1 ^ a2 != 0 regardless after player 1 plays.
This means player 2 can always win by setting a1 ^ a2 = 0.

The trick to the problem is to realize that making a1 ^ a2 ^... ^ an =0 is a winning move because then your opponent will be forced to make it not zero.

WanFactory
Monday, June 27, 2005

*  Recent Topics

*  Fog Creek Home