wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A Game of Two
        
(Message started by: casual_kumar on Aug 11^th, 2006, 5:50am)

Title: A Game of Two
Post by casual_kumar on Aug 11^th, 2006, 5:50am

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? :)

Title: Re: A Game of Two
Post by Eigenray on Aug 11^th, 2006, 9:27am

on 08/11/06 at 05:50:00, casual_kumar wrote:

A very nice puzzle,

Nice, like eating a chocolate bar.

Title: Re: A Game of Two
Post by Grimbal on Aug 11^th, 2006, 9:58am

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.

Title: Re: A Game of Two
Post by Astrix on Aug 11^th, 2006, 10:14am

I don't know what the best choice is, but I know that [hide]A[/hide] will win.
[hide]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.[/hide]

Title: Re: A Game of Two
Post by Roy on Aug 11^th, 2006, 2:57pm

[hide]if they pick numbers going up from 1,2,3..... there will be no need to strike off other factors so B will win.[/hide] But that's one unlikely scenario

Title: Re: A Game of Two
Post by casual_kumar on Aug 11^th, 2006, 3:08pm

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? 8)

Title: Re: A Game of Two
Post by casual_kumar on Aug 11^th, 2006, 3:12pm

on 08/11/06 at 10:14:34, Astrix wrote:

but thats just one side of the coin, to say who wins you must have a unique winner in every situation.

Title: Re: A Game of Two
Post by Icarus on Aug 11^th, 2006, 4:11pm

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.

Title: Re: A Game of Two
Post by casual_kumar on Aug 11^th, 2006, 11:43pm

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.

Title: Re: A Game of Two
Post by Roy on Aug 12^th, 2006, 6:03am

You really are a newbie.

Title: Re: A Game of Two
Post by Grimbal on Aug 12^th, 2006, 6:16am

Yeah, after a while you realize we are not soo sharp, we only repeat again and again old solutions we have seen before...

Title: Re: A Game of Two
Post by Eigenray on Aug 12^th, 2006, 9:34am

This game is very similar to [link=http://en.wikipedia.org/wiki/Chomp]Chomp[/link], on a different poset.

on 08/11/06 at 16:11:41, 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.)

Title: Re: A Game of Two
Post by Icarus on Aug 12^th, 2006, 11:12am

on 08/12/06 at 09:34:15, 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.)

Title: Re: A Game of Two
Post by TimMann on Aug 18^th, 2006, 3:24pm

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.

Title: Re: A Game of Two
Post by Icarus on Aug 18^th, 2006, 8:33pm

Nice, and nice to hear from you again, Tim!

Title: Re: A Game of Two
Post by srn347 on Sep 2^nd, 2007, 9:57am

A because if he goes first, he can use an unbeatable strategy.

Title: Re: A Game of Two
Post by towr on Sep 2^nd, 2007, 10:20am

on 09/02/07 at 09:57:11, 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?

Title: Re: A Game of Two
Post by srn347 on Sep 15^th, 2007, 3:46pm

Not for 1000. Try 100 or less.