All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
Define winning strategy (Posted on 2013-11-14) Difficulty: 3 of 5
Two players A and B play the following game:
Start with the set S of the first 25 natural numbers: S={1,2,,25}.
Player A first picks an even number x0 and removes it from S:
We have S:=S−x0.
Then they take turns (starting with B) picking a number xn∈S which is either divisible by xn-1 or divides xn-1 and removing it from S.

The player who can not find a number in S which is a multiple of the previous number or is divisible by it loses.

Which player has the winning strategy and what is it?

Source: someone sent it by Email.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
It's complicated | Comment 4 of 6 |
I don't have a complete strategy but there are some things to notice.  I made a picture with 1 to 25 in a circle and connected legal moves.

If you pick 1 you will lose because your opponent will pick 13, 17, 19, or 23 (these are winning positions - the one who picks one of these has won.)

Therefore if you can pick 11 you will win because you could only choose that after 22 so your opponent would be forced to choose 1.
Therefore 22 is a losing position.
(This doesn't make 2 a winning position, since 22 is not forced from 2 unless all else is used.) 
On my graph 11 is a node with only two edges.

Likewise 25 is a winning position which comes from 5, a losing position.

So there are 17 positions left not labeled as winning or losing.
As the game progresses edges can be removed as nodes are used up.  Any node with two remaining edges becomes a winning position as using one of them will force the opponent to choose 1.

For example 9 has three edges (connecting to 1, 3, 18) if player A chooses 18 and B chooses 3 the edge from 9 to 18 is removed.  9 becomes a winning position and A chooses it to win.  (B must choose 1, A picks one of the large primes.)
(18 is not necessarily  a winning position because B could have chosen 9 instead of 3 then A would pick 3 not 1.)

The point is that winning positions become more and more numerous until eventually someone loses by being forced to give the opponent the opportunity to pick one.

  Posted by Jer on 2013-11-15 16:09:10
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information