I have this question in one of my assignments of a course(MIT 6042) that I am pursuing online. Question is as follows:
Here is a very, very fun game. We start with two distinct, positive integers written on a blackboard. Call them x and y. You and I now take turns. (I’ll let you decide who goes first.) On each player’s turn, he or she must write a new positive integer on the board that is a common divisor of two numbers that are already there. If a player can not play, then he or she loses. For example, suppose that 12 and 15 are on the board initially. Your first play can be 3 or 1. Then I play 3 or 1, whichever one you did not play. Then you can not play, so you lose.
(a) [6 pts] Show that every number on the board at the end of the game is either x, y, or a positive divisor of gcd(x, y).
(b) [6 pts] Show that every positive divisor of gcd(x, y) is on the board at the end of the game.
(c) [6 pts] Describe a strategy that lets you win this game every time.
I was able to solve part (a) as game involves writing only common divisors of
y on the board, and gcd(x,y) is the smallest positive linear combination of
y and thus can be expressed as
sx+ty. Further, a common divisor of
y divides all linear combinations of
y and thus divides gcd(x,y).
Part(b) was rather trivial I suppose, though I am not sure, as game involves writing all common divisors of
y and they divide gcd(x,y) as well as proved in part(a).
Main issue is with part (c). Solution I proposed is that if number of common divisors of
y is even then let the other player start the game and if it is odd then I should start the game. However this solution seems too trivial as well and I suppose they wouldn't put it in the assignment if it was that simple.
Can anyone tell if there is anything wrong with any of my solutions and if there is a more refined solution to part(c).