Two people are playing an exciting game in which they take turnsremoving marbles from a bag. At the beginning of the game, this bagcontains some red marbles and some blue marbles. The bag istransparent so at any time during the game, the players knowexactly how many red and how many blue marbles are in the bag.
The players alternate taking turns. On a player’s turn, he orshe must remove some marbles from the bag. The player chooses whichmarbles to remove, under the condition that he or she remove atleast one marble and the marbles removed in a single turn are allthe same color. The player to remove the last marble from the bagduring his or her turn wins.
Assume that player 1 is playing the game with player 2,and player 1 makes the first move. If you were player 1, whatoptimal strategy could you use to play this game? Under whatstarting conditions would this optimal strategy guarantee a win,and why? What can you say about the outcome of the game if thesestarting conditions are not met?
(Hint: Try thinking of an invariant you could maintain duringcertain points of the game)
