Game of Two

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!!

Comments

  1. 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
  2. "The game can be reduced to an automata"

    "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?

    ReplyDelete
  3. "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

    So, 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

    ReplyDelete
  4. 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 ?

    ReplyDelete

Post a Comment