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 x and y on the board, and gcd(x,y) is the smallest positive linear combination of x and y and thus can be expressed as sx+ty. Further, a common divisor of x and y divides all linear combinations of x and 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 x and 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 x and 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).
Best Answer
In principle, your answer to part (c) is correct. However, it can be simplified and expressed more nicely: The number of divisors of a natural number $n$ is odd if and only if $n$ is a perfect square (because all divisors $\ne\sqrt n$ come in pairs). Therefore, your winning strategy consists in deciding who makes the first move based on whether or not $\gcd(x,y)$ is a perfect square.