There are 2n cards labeled 1, 2, ..., 2n respectively, and the cards are distributed randomly between two players so that each has n cards. Each player takes turns to place one card, and you win if you put down a card so that the current sum of all the played cards is divisible by 2n+1.
For example, if n=10, and the previously placed cards are 5, 8, 9, 19, then if player A now places 1, he wins since 5+8+9+19+1 = 42 is divisible by 2*10+1=21.
Assuming both players want to win, what strategy should one adopt in order to win? Following the strategy, is there a consistent winner of this game?
(In reply to
re(4): Solution by David Shin)
Yes, I see now I had a bug in my program that was following that local strategy (or I intended to make follow that strategy). The bug caused 2 to lose sometimes. Now that it follows that strategy perfectly, 2 never loses. The commented out IF i <> j THEN and its corresponding END IF, were still present, so if the winning card was the one that produced the need to play that card again (which the opponent could not do), that move was not recognized as a winner. It just looked at the already played cards and the other cards in its hand to see if they were needed to win by the opponent.
n2 = 8
DIM deck(n2)
DO
FOR i = 1 TO n2
deck(i) = i
NEXT
FOR i = 1 TO n2
j = INT(RND(1) * n2 + 1)
IF i <> j THEN SWAP deck(i), deck(j)
NEXT
FOR i = 1 TO n2 STEP 2
PRINT deck(i);
NEXT
PRINT
FOR i = 2 TO n2 STEP 2
PRINT deck(i);
NEXT
PRINT
REDIM down(n2)
winner = 1
played = 0
pl = 0
DO
t = 0
FOR i = 1 TO played
t = t + down(i)
IF t > n2 THEN t = t  (n2 + 1)
NEXT
toPlay = 0
FOR i = 1 + pl TO n2 STEP 2
IF deck(i) > 0 AND t + deck(i) = (n2 + 1) THEN
winner = pl
toPlay = i
EXIT FOR
END IF
NEXT
IF toPlay = 0 THEN
FOR i = 1 + pl TO n2 STEP 2
IF deck(i) THEN
FOR j = 1 TO played
IF down(j) THEN
t2 = t + deck(i) + down(j)
DO
IF t2 > n2 THEN t2 = t2  (n2 + 1)
LOOP UNTIL t2 < (n2 + 1)
IF t2 = 0 THEN
toPlay = i
END IF
END IF
NEXT
END IF
NEXT
END IF
IF toPlay = 0 THEN
FOR i = 1 + pl TO n2 STEP 2
IF deck(i) THEN
FOR j = 1 + pl TO n2 STEP 2
IF deck(j) THEN
' IF i <> j THEN
t2 = t + deck(i) + deck(j)
DO
IF t2 > n2 THEN t2 = t2  (n2 + 1)
LOOP UNTIL t2 < (n2 + 1)
IF t2 = 0 THEN
IF deck(j) < deck(i) THEN toPlay = j: ELSE toPlay = i
END IF
' END IF
END IF
NEXT
END IF
NEXT
END IF
IF toPlay = 0 THEN
FOR i = 1 + pl TO n2 STEP 2
IF deck(i) THEN toPlay = i
NEXT
END IF
played = played + 1
COLOR 13 + pl
PRINT deck(toPlay);
down(played) = deck(toPlay)
deck(toPlay) = 0
pl = 1  pl
LOOP UNTIL winner > 1
wins(winner) = wins(winner) + 1
COLOR 7
PRINT
PRINT wins(0), wins(1)
LOOP

Posted by Charlie
on 20050110 20:12:13 