Math 160 Mathematical Problems and Games, Fall 2002
Problem Set 10: hand in one problem on Tuesday, November 26.

The problems this week are about game theory.  Game theory has applications in economics and other social sciences, as well as being interesting mathematically.

Some terms:  A winning strategy is a strategy that one player can follow to guarantee that they will win.  (In the games below, where two players play against each other, only one can have a winning strategy. Why?).  A losing position is the state of the game after you move if the other player can then win.  (For example in game #1 below, if you take all of the stones from one of the piles, leaving only one pile, that is a losing position because the other player can take all of the second pile and win.)  A winning position is the state of the game after you move, if no matter what the other player does you can still win.  (For example in game #1 below, two piles of one stone each is a winning position.  Why?).  You can often analyze games from the end backwards, determining which positions are winning and which are losing, and develop a strategy that way.  Other useful ideas are parity (odd and even), and symmetry-- sometimes a winning strategy mirrors whatever the other person does in some way.

Instructions for this week:  As always, try all of the problems.  Then choose one to write up and hand in.

1.  There are two piles of stones. One piles has 30 stones, and the other has 20 stones. Players take turns removing as many stones as they please (at least one) from ONE pile. The player who takes the last stone (or stones) wins. How should you play if you want to win? Should you go first or second? (In other words, which player has a winning strategy, and what is it?)

2. There are three piles of stones. One pile has 4 stones, one has 5 stones, and the other has 6 stones. Players take turns removing as many stones as they please (at least one) from ONE pile. The player who takes the last stone wins.  Which player has a winning strategy, and what is it?

3.  On an 8 x 8 square board, player take turns moving a coin from the lower left hand corner towards the upper right hand corner.  The coin starts in the lower left hand corner.  On each move, a player can either move up one space, to the right one space, or one space diagonally up and to the right.  Which player has a winning strategy, and what is it?

4.  This game begins with the number 1.  In a turn, a player can multiply the current number by any natural number between 2 and 9.  The player who first names a number larger than 1000 wins.  Which player has a winning strategy, and what is it?
If any of this is confusing or you want a hint, email me at ksir@math.sunysb.edu .  

Remember, Nov. 26 is our last class!  If you liked this course at all, I can recommend other courses that you might like to take (or stop by the Undergraduate Math Office for other recommendations and advice).