This puzzle is taken from website of Krishnamurthy Iyer (Stanford)

Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For some natural number N, the board consists of numbers from 1 to N. Each player takes turns to strike off a number from the board, with the added condition that if a number is struck off, then all its divisors should also be struck off. The player to strike off the last number on the board wins. A plays first. Is this game fair? If not, who has a winning strategy for each N and what is it? Else find the best strategy for each player.

Update (11/12/09): Solution in comments!!

I bet player 1 will always win.Think about it.The answer lies on the smallest natural number.Player 1 can always choose to strike of number 1 or not to strike of number 1 in the first turn.

ReplyDelete"The game can be reduced to an automata"

ReplyDelete"If you can reduce a game to an automaton, then at least one player has a winning strategy"

"If a player has a winning strategy, it has got to be Player 1"

Solution mailed by Jaadu. Does it make sense?

"All 2-player games where both players have to reach the same state and the game always finishes in finite time, there exists a winning strategy" -- Proved by Church and people of Automata theory in 40s

ReplyDeleteSo, in this game, at least one player has a strategy.

Since there always exists a strategy, we can prove that a strategy for one player exists. If its of the first player, we know that a strategy exists for the first player. If its for the second player, we will prove that a strategy always exists for the first player.

Let player II has a strategy. So, player II can win from any state {1,2,3,..n} - {k and Divisors of k}

Our player I starts with canceling 1. Whatever player 2 cancels, the state is {1,2,3..n} - {k and Divisors of k}. So, now player I can use player II strategy to win the game.

:)

So, Player I always wins :D :D

I came across this problem even before and even then I just gave a "existential" proof. Can someone brave of heart try to get the constructive strategy ?

ReplyDeletehttp://www.win.tue.nl/~aeb/games/chomp.html

ReplyDeleteThere cannot be a constructive strategy

nice analogy with chomp :) :)

ReplyDelete