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.

DECLARE FUNCTION playIt! (p!)
DIM SHARED used(25), totplays, h(25), ct

OPEN "winstrat.txt" FOR OUTPUT AS #2

h(0) = 2
FOR play1 = 2 TO 24 STEP 2
    IF playIt(play1) THEN PRINT "player 1 wins with"; play1
NEXT play1
PRINT ct

CLOSE

FUNCTION playIt (p)
used(p) = 1

good = 0: hasmove = 0
totplays = totplays + 1
h(totplays) = p

IF totplays = 3 AND p = 13 THEN
   REM
END IF

IF totplays = 25 THEN
  playIt = 1: EXIT FUNCTION
END IF
FOR i = 1 TO 25
    IF used(i) = 0 AND (h(totplays) MOD i = 0 OR i MOD h(totplays) = 0) THEN
      hasmove = 1
        IF playIt(i) THEN
    '      IF totplays = 1 THEN
    '        PRINT h(1); h(2)
    '      END IF
          good = 1: EXIT FOR
        END IF
    END IF
NEXT
IF good THEN
 playIt = 0
ELSE
 playIt = 1
 IF totplays = 2 THEN ' MOD 2 = 0 AND hasmove = 0 THEN
   FOR i = 1 TO totplays
      PRINT h(i);
   NEXT i
   PRINT
   FOR i = 1 TO totplays
      PRINT #2, h(i);
   NEXT i
   PRINT #2,
   ct = ct + 1
 END IF
 IF totplays MOD 2 = 1 THEN
      REM
 END IF
END IF
used(p) = 0
totplays = totplays - 1
END FUNCTION

finds that:

The winning first reply for the second player depends on the first player's first move:

  player
1        2
play    reply

2       14
4       12
6       12
8       16
10       20
12       4
14       2
16       4
18       9
20       10
22       11
24       4

But the list of replies and counter-replies is quite large, and I don't see an easily-described pattern.

Posted by Charlie on 2013-11-15 09:47:57