question archive Here is a very, very fun game
Here is a very, very fun game
Subject:Computer SciencePrice: Bought3
Here is a very, very fun game. We start with two distinct, positive integers written on a blackboard. Call them a and b. 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 the difference 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 must be 3, which is 15??12. Then I might play 9, which is 12-3. Then you might play 6, which is 15 - 9. Then I can not play, so I lose.
(a) Show that every number on the board at the end of the game is a multiple of gcd .a; b/.
(b) Show that every positive multiple of gcd. (a; b) up to max. (a; b) is on the board at the end of the game.
(c) Describe a strategy that lets you win this game every time.
