 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Who will win? (Posted on 2005-01-10) 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?

 See The Solution Submitted by Bon Rating: 2.0000 (1 votes) Comments: ( Back to comment list | You must be logged in to post comments.) re(5): Solution | Comment 8 of 9 | (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 2005-01-10 20:12:13 Please log in:

 Search: Search body:
Forums (0)