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 x₀ and removes it from S:
We have S:=S−x₀.
Then they take turns (starting with B) picking a number x_n∈S which is either divisible by x_n-1 or divides x_n-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.

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