Author |
Topic: A Game of Two (Read 2219 times) |
|
casual_kumar
Newbie
Gender: 
Posts: 21
|
 |
A Game of Two
« on: Aug 11th, 2006, 5:50am » |
 Quote  Modify
|
A very nice puzzle,
A and B, are two infinitely (equally) intelligent people. They play a game. The game is described as: -
There are N numbers written on a paper (1 to N). When a player's move comes, he can strike off any one number of his choice which are available on the paper. After striking off a number, he also has to strike off the number's factors. So, striking off 10 would result in striking off 5, 2, and 1. If a factor is already striked off, no need to strike it off again. All striked off numbers are out of the game. The game proceeds with rest of the numbers. The person striking off the the last number wins.
If A begins the play and both A and B play their best possible moves, who will win for N = 1000? 
|
| « Last Edit: Aug 11th, 2006, 5:51am by casual_kumar » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A Game of Two
« Reply #1 on: Aug 11th, 2006, 9:27am » |
Quote Modify
|
on Aug 11th, 2006, 5:50am, casual_kumar wrote:
Nice, like eating a chocolate bar.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Game of Two
« Reply #2 on: Aug 11th, 2006, 9:58am » |
Quote Modify
|
It is like in the The Matrix, you always have the choice.
I personally have no idea which is the right choice, (I'm not infinitely intelligent, you see...) but I can tell the choice is there for whomever takes it.
|
|
IP Logged |
|
|
|
Astrix
Newbie
Posts: 37
|
|
Re: A Game of Two
« Reply #3 on: Aug 11th, 2006, 10:14am » |
Quote Modify
|
I don't know what the best choice is, but I know that A will win.
Suppose that if A picks any number from 2 to 1000, then B has a winning answer. In that case A can pick 1 and he will have a winning answer to whatever B picks.
|
|
IP Logged |
|
|
|
Roy42
Senior Riddler
Gender:
Posts: 418
|
|
Re: A Game of Two
« Reply #4 on: Aug 11th, 2006, 2:57pm » |
Quote Modify
|
if they pick numbers going up from 1,2,3..... there will be no need to strike off other factors so B will win. But that's one unlikely scenario
|
|
IP Logged |
Regards,
≈Roy42
|
|
|
casual_kumar
Newbie
Gender:
Posts: 21
|
|
Re: A Game of Two
« Reply #5 on: Aug 11th, 2006, 3:08pm » |
Quote Modify
|
Don't forget that they will always make the best possible move. So, why would A start with 1 and more unlikely strike numbers in order (1 2 3 4 ...) to ultimately loose the game? 
|
|
IP Logged |
|
|
|
casual_kumar
Newbie
Gender:
Posts: 21
|
|
Re: A Game of Two
« Reply #6 on: Aug 11th, 2006, 3:12pm » |
Quote Modify
|
on Aug 11th, 2006, 10:14am, Astrix wrote:I don't know what the best choice is, but I know that A will win.
Suppose that if A picks any number from 2 to 1000, then B has a winning answer. In that case A can pick 1 and he will have a winning answer to whatever B picks. |
|
but thats just one side of the coin, to say who wins you must have a unique winner in every situation.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Game of Two
« Reply #7 on: Aug 11th, 2006, 4:11pm » |
Quote Modify
|
Astrix is correct. His argument shows that if B had a winning strategy, A could steal it, regardless of the situation. Therefore B has no winning strategy. Since draws are impossible, A must have one.
"Strategy-stealing" is a well-known technique in game theory for proving first-player wins.
The vast majority of 2-player deterministic no-draw games are 1st player wins (i.e., the 1st player, if he plays optimally, can force a win). This was part of what allowed John Conway to invent surreal numbers.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
casual_kumar
Newbie
Gender:
Posts: 21
|
|
Re: A Game of Two
« Reply #8 on: Aug 11th, 2006, 11:43pm » |
Quote Modify
|
Yes, I just wanted him to show that if A has a winning strategy in the game of 2 to 1000, he would still win as striking any other number in 1 to 1000 strikes off 1 in the very first move.
Good going everyone. I have not seen a forum with such sharp minds.
|
|
IP Logged |
|
|
|
Roy42
Senior Riddler
Gender:
Posts: 418
|
|
Re: A Game of Two
« Reply #9 on: Aug 12th, 2006, 6:03am » |
Quote Modify
|
You really are a newbie.
|
|
IP Logged |
Regards,
≈Roy42
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Game of Two
« Reply #10 on: Aug 12th, 2006, 6:16am » |
Quote Modify
|
Yeah, after a while you realize we are not soo sharp, we only repeat again and again old solutions we have seen before...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: A Game of Two
« Reply #11 on: Aug 12th, 2006, 9:34am » |
Quote Modify
|
This game is very similar to Chomp, on a different poset.
on Aug 11th, 2006, 4:11pm, Icarus wrote:| The vast majority of 2-player deterministic no-draw games are 1st player wins (i.e., the 1st player, if he plays optimally, canforce a win). This was part of what allowed John Conway to invent surreal numbers. |
|
How's that? (It's funny, because no surreal number is a 1st player win: there's one 2nd player win 0, and the rest go to whichever player, L or R, can move to it.)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Game of Two
« Reply #12 on: Aug 12th, 2006, 11:12am » |
Quote Modify
|
on Aug 12th, 2006, 9:34am, Eigenray wrote:| How's that? (It's funny, because no surreal number is a 1st player win: there's one 2nd player win 0, and the rest go to whichever player, L or R, can move to it.) |
|
Poorly stated to the point of being untrue, is how that is. 
While it is true that no well-formed surreal number is a 1st player win, the same is not true of psuedo-numbers, and in gaming, positions that correspond to surreal numbers tend to be trivially obvious wins for one player or the other (L vs R).
I should have specified in addition that the games be symmetric: i.e. when presented on their turn with the same position, both players have exactly the same moves available to them. Such games, of which 0 is the only one which is a surreal number, are rarely ever 2nd player wins, partly because it is difficult for the 2nd player to have a strategy the first player cannot steal. (Of course, "rarely" is not the same as "never", or else the 1st player wouldn't be able to win either since after his move he becomes the 2nd player. Hence he must always move to one of those rare 2nd player win positions).
Conway originally was studying how separated subgames in Go could be analyzed together, and developed a general concept of "adding" and "negating" games. He then was able to define two games as equivalent if the sum of one and the negation of the other resulted in a 2nd-player-win game. If 2nd player wins were common, this would mean a high level of equivalency, and few equivalence classes. But instead he found that the equivalence classes had a rich structure that includes a massive extension "field" of the reals, which is now known as the surreal numbers. ("Field" in quotes because usually a field is considered a set, and the surreals, which also include the cardinal numbers, cannot be a proper set.)
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: A Game of Two
« Reply #13 on: Aug 18th, 2006, 3:24pm » |
Quote Modify
|
A very slightly different way to show that A wins: If player B has a winning strategy, this strategy must in particular have a winning answer to A playing "1" as his first move. Let this answer be k. Then suppose A plays k as his first move. This automatically strikes out 1, so the state of the game is now exactly the same as if A had begun with 1 and B replied with k, except that it's now B's move. A then continues using B's winning strategy, and wins.
This contradicts the assumption that B has a winning strategy; therefore B doesn't have one. But the game is finite, has no draws, and has no chance element, so A must have a winning strategy.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A Game of Two
« Reply #14 on: Aug 18th, 2006, 8:33pm » |
Quote Modify
|
Nice, and nice to hear from you again, Tim!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: A Game of Two
« Reply #15 on: Sep 2nd, 2007, 9:57am » |
Quote Modify
|
A because if he goes first, he can use an unbeatable strategy.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Game of Two
« Reply #16 on: Sep 2nd, 2007, 10:20am » |
Quote Modify
|
on Sep 2nd, 2007, 9:57am, srn347 wrote:| A because if he goes first, he can use an unbeatable strategy. |
|
That assumes there is an unbeatable strategy. Can you prove there is one?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: A Game of Two
« Reply #17 on: Sep 15th, 2007, 3:46pm » |
Quote Modify
|
Not for 1000. Try 100 or less.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print