0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I'm stuck on how to show that this is related to the gcd of the original two numbers.

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).

$\endgroup$
  • $\begingroup$ So the inductive hypothesis is that: it works for $n$ numbers on the board so if you take the difference of any two numbers, then they are always of the form $cg-dg$ $\endgroup$ – VV6570 Oct 25 '17 at 12:20
0
$\begingroup$

Your answer for c) works, assuming part b). However, what you have for b) misses the point. What you need to show is that the game can't end before you've written all the multiples of $\gcd(a,b)$ below the maximum - in other words you can't have a situation where you have some, but not all, of these numbers, yet can't create any new ones.

Hint for this: aim to show that 1. if $\gcd(a,b)$ ever gets written down then all the other numbers will eventually follow 2. there is always a sequence of moves which leads to $\gcd(a,b)$. (Do you know Euclid's algorithm?)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.