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