CSC 156
Online Homework 2

Assigned Jan. 30, due Feb 10

This one is not from the textbook. Consider the following two-player game:

Two positive integers are written on the board (later on there will be more). Whenever it's your turn, you can pick two of the numbers on the board, subtract them, and write their difference on the board unless it's already there. If you can't find a pair of numbers whose difference isn't already there, the game is over and you've lost.

Tell me everything you can about this game. Is the game guaranteed to end eventually? Is there a strategy guaranteed to win it? Can you tell, from the two initial numbers, who will win (assuming both players play perfectly)? Can you tell, from the two initial numbers, how many moves there will be in the game? How would the answers to these questions change if there were three initial numbers? How would the answers change if there were three players?

Extra credit: Suppose you had to decide whether to be the first or second player before seeing the initial numbers. If the numbers are chosen randomly, is the first player more likely to win than the second, or the other way around, or are they equally likely to win? Can you figure out the exact probabilities?

The problem is to be discussed on Piazza, and a "student solution" developed collaboratively on Piazza. You will be graded on the quality of the student solution and on your individual participation in reaching it.


Last modified: Tue Feb 11 09:10:58 EST 2014
Stephen Bloch / sbloch@adelphi.edu