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 2005-01-10 20:12:13