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

Home > Games
Oddwins (Posted on 2006-10-03) Difficulty: 3 of 5
A game of 11 marbles wherein each player can either pick one or two marbles from the total. Starting from Player A & then Player B alternatively. This continues till all the marbles are picked. The winner is the one having odd number of marbles.

What is the strategy to be followed for Player A & B to win?. What happens for higher total number of marbles (13, 15 etc )?

No Solution Yet Submitted by Salil    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution for 11 marbles | Comment 9 of 11 |

The first three columns below represent the number of available marbles remaining, the number of marbles currently held by the player whose turn it is, and the number of marbles held by the opponent.  The fourth column is how many marbles to take.

After the gap, the next three columns represent what situation this leaves the opponent in: available marbles, marbles in his own hand, marbles in the original player's hand.  The next two sets of three are the possibilities for what the other player might give back to the original.

  1  4  6  1       0  6  5
  1  6  4  1       0  4  7
  2  3  6  2       0  6  5
  2  4  5  1       1  5  5       0  5  6
  2  5  4  2       0  4  7
  2  6  3  1       1  3  7       0  7  4
  3  3  5  2       1  5  5       0  5  6
  3  5  3  2       1  3  7       0  7  4
  4  3  4  1       3  4  4       2  4  5       1  4  6
  5  2  4  1       4  4  3       3  3  5       2  3  6
  5  2  4  2       3  4  4       2  4  5       1  4  6
  5  4  2  1       4  2  5       3  5  3       2  5  4
  5  4  2  2       3  2  6       2  6  3       1  6  4
  6  1  4  2       4  4  3       3  3  5       2  3  6
  6  2  3  1       5  3  3       4  3  4       3  3  5
  6  3  2  2       4  2  5       3  5  3       2  5  4
  7  1  3  2       5  3  3       4  3  4       3  3  5
  8  1  2  1       7  2  2       6  2  3       5  2  4
  9  0  2  1       8  2  1       7  1  3       6  1  4
  9  0  2  2       7  2  2       6  2  3       5  2  4
 10  0  1  1       9  1  1       8  1  2       7  1  3

The second player has the win, as he's initially presented with situation 10,0,1 or 9,0,2 depending on whether the first player took 1 or 2 marbles.  If the first took 1 marble, the second must take 1 marble, leaving the first player with the state 9,1,1, from which there is no winning strategy, as he must leave it to the second player as 8,1,2 or 7,1,3, both of which have winning strategies posted above.

If the first player took 2 marbles, the second could take either 1 or 2 and still be assured of victory: follow the path as above.

DECLARE FUNCTION makePlay! (n!)
CLEAR , , 29999

DIM SHARED pl, avail, hand(2), h$, ct

CLS
OPEN "mkplay1.txt" FOR OUTPUT AS #2
OPEN "mkplay2.txt" FOR OUTPUT AS #3
avail = 11
pl = 1
h$ = ""
  res = makePlay(1)
  res = makePlay(2)
PRINT ct

FUNCTION makePlay (n)
 h$ = h$ + LTRIM$(STR$(n))
 avail = avail - n
 hand(pl) = hand(pl) + n
 IF avail = 0 THEN
   IF hand(pl) MOD 2 THEN
    winner = pl
    PRINT #2, h$
    GOSUB report2
    ct = ct + 1
   ELSE
    winner = 3 - pl
   END IF
 ELSE
   pl = 3 - pl
   winner1 = makePlay(1)
   pl = 3 - pl
   IF avail > 1 THEN
    pl = 3 - pl
    winner2 = makePlay(2)
    pl = 3 - pl
   ELSE
    winner2 = 0
   END IF
   IF winner1 = pl AND (winner2 = pl OR winner2 = 0) THEN
     winner = pl
     PRINT #2, h$
     GOSUB report2
     ct = ct + 1
   ELSE
     winner = 3 - pl
   END IF
 END IF
 makePlay = winner
 h$ = LEFT$(h$, LEN(h$) - 1)
 avail = avail + n
 hand(pl) = hand(pl) - n
EXIT FUNCTION

report2:
    PRINT #3, USING "###"; avail + n; hand(pl) - n; hand(3 - pl); n;
    PRINT #3, "     ";
    PRINT #3, USING "###"; avail; hand(3 - pl); hand(pl);
    IF avail > 0 THEN
      PRINT #3, "     ";
      PRINT #3, USING "###"; avail - 1; hand(pl); hand(3 - pl) + 1;
      IF avail > 1 THEN
        PRINT #3, "     ";
        PRINT #3, USING "###"; avail - 2; hand(pl); hand(3 - pl) + 2;
      END IF
    END IF
    PRINT #3,
RETURN

END FUNCTION

The table shown is file #3, mkplay2.txt, sorted with duplicate lines removed.

Edited on October 4, 2006, 9:37 am
  Posted by Charlie on 2006-10-04 09:20:20

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