Congested Walkway
Dan and Sam play a game on a grid, in which one takes squares (red) and the other takes circles (blue). Once the game starts, they take turns moving a single piece in their turn. Each piece can only be moved straight forward or backward, any number of grids (and cannot skip over the opponent's piece). This is the initial position:
A player loses when he is not able to move any of his pieces in his turn. If Dan goes first, who will win? In other words, who has a winning strategy?
This is the twelfth problem of the set Winning Strategies .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Relevant wiki: Combinatorial Games - Winning Positions
Playing this game on an n by m grid is equivalent to playing Nim with m piles of n − 2 sticks (the rows corresponding to piles and free squares to sticks). Understanding the game of Nim (also an interesting exercise) tells you that if m is even and both players play optimally, then the second player ( Sam ) will win. If m is odd, then the first play will win.