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

 Define winning strategy (Posted on 2013-11-14)
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.)
 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:

`  player1        2play    reply`
`2       144       126       128       1610       2012       414       216       418       920       1022       1124       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

 Search: Search body:
Forums (0)