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!!
Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)
Subscribe to:
Post Comments (Atom)
Fraction Brainteaser
Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this art...

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tos...

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...
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 2player 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