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.)
Solution within the constraints | Comment 3 of 6 |

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
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 (3)
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