Consider the following two-player game. The game starts with two distinct, positive integers written on a blackboard. Call them $a$ and $b$. The players then take alternating turns. At each turn, the player must write a new positive integer on the board that is the difference of two numbers already on the board. If a player has no valid play, then that player loses. For example, suppose that 12 and 15 are on the board initially. Player 1 must play 3, which is 15-12. Then player 2 might play 9 = 12-3. Then player 1 might play 6 = 15-9. Now player 2 can’t move, so loses.
(a) Prove that every integer on the board at the end of the game is a multiple of $\gcd(a,b)$.
(b) Prove that every multiple of $\gcd(a,b)$ up until $\max(a,b)$ is written on the board by the end of the game.
(c) Assuming you have the choice to pick which player goes first, describe a strategy to win the game.
My solution so far:
(a) Proved by induction. Thanks! @Peter Taylor
(b) So the game is basically writing all multiples of $\gcd(a,b)$. $a$ and $b$ are multiples of $\gcd(a,b)$ by definition, but you won't write them because they were already there to start the game. So you're just writing all multiples not equal to a or b. Once you finish writing those, the game ends, and you have all multiples of $\gcd(a,b)$, including a and b. So if you sort the list of numbers, it ends with $\max(a,b)$. (Not too sure of this...seems wishy-washy)
(c) If the number of multiples of the gcd up until max(a,b) is odd, then I go first. Example: Start with 12 and 15. gcd=3. All multiples of 3 up until 15 are 3,6,9,12,15. 12 and 15 start. I go first and write 3. Player 2 may write 12-3=9. Then I play 15-9=6. No more multiples of gcd are left for player 2 to write so I win. If the number of multiples of gcd up until max(a,b) is even, then I let player 2 go first. As soon as he writes the first difference, there is an odd number of multiples left and when it's my turn, it just becomes the previous case. So I win again.
Please check part (b) and (c). Also, does anyone have a good source for learning about gcd's and divisibility and stuff? I'm having a hard time conceptualizing the relationship between gcd and linear combinations. Thanks.
By induction: initially $g = \gcd(a,b)$ divides all of the numbers on the board (which are just $a$ and $b$). Inductive step: if we pick two numbers on the board, $cg$ and $dg$, then their difference is $(c-d)g$ is a multiple of $g$.
Since that gets you past the point where you were stuck, I'll leave you to carry on, starting at subquestion (b).