6. (10) (Problem 8.12, textbook) Here is a game you can analyze with number theo

Question

6. (10) (Problem 8.12, textbook) Here is a game you can analyze with number theory and always beat me. We start with two distinct, positive integers written on a blackboard. Call them a and b. Now we take turns. (I'll let you decide who goes first.) On each turn, the player must write a new positive integer on the board that is the difference of two numbers that are already there. If a player cannot play, then they lose. 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't play, so I lose. (a) Show that every number on the board at the end of the game is a multiple of ged(a, b). (b) Show that every positive multiple of ged(a, b) up to mar(a, b) is on the board at the end of the game (c) Describe a strategy that lets you win this game every time.

Explanation / Answer

Solution:

a)

Any two numbers will have a greatest common divisor.

As in the game we have to write the divisors of the two numbers, those numbers would consist of all positive divisors of gcd( x,y). Thus in the end we would be left with only x, y and all positive divisors of gcd(x,y).(gcd = greatest common divisor)

b)

As the common divisor of two numbers would be all the positive divisors of gcd(x,y) so they would all be present in the board at the end of the game.

c)

find out the gcd of the two numbers. If total number of factors of the gcd is even then I would let you start the game and if it is odd, I would start the game. This way last factor would always be written by me. And I would always win.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.