1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Its a really important fact. $\endgroup$ – shiva Aug 6 '16 at 13:30

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.