• 0

Divisor Take-Away Game

Question

Posted · Report post

Here's the game: the first player picks an integer n > 1 , then the second player subtracts a proper divisor d < n of that number, telling the first player the difference n - d , then the first player subtracts a proper divisor of that new number, etc. The player who announces a difference of 1 is the winner. Does either player have a winning strategy? If not explain why not; if so, which player is it, does it depend on n, and what's the strategy?
note: A positive proper divisor is a positive divisor of a number n, excluding n itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.
0

Share this post


Link to post
Share on other sites

4 answers to this question

  • 0

Posted · Report post

First player wins easily. He picks the number n=3, forcing the second player to subtract d=1 and announce n-d=2. Then the first player subtracts 1 from 2, announcing a difference of 1. It does heavily depend on n though, if the first player were to pick n=2 he would be cooked.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

What if player 2 picks their own number and chooses d?

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

Rainman is a sniper!

:thumbsup:

Edited by gavinksong
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

If you start with the number 2, then whoever subtracts a number first will clearly win. Rainman showed that if you start with the number 3, then whoever subtracts a number first will lose. For cases where N>3:

If N is odd, then all divisors of N must also be odd. So if you face an odd N, you must subtract an odd number and leave your opponent with an even N. Because the goal is to get to 1 which is odd, you cannot win directly from N if N is odd.

If N is even, you can subtract 1 to make it an odd number. That means your opponent can't win on the following move and must leave you with an even number on your next turn, at which point you can subtract 1 again (or any other odd divisor if there is one) to keep leaving your opponent with an odd number from which they can't win. N will keep decreasing until you get a 2 and win.

So if N is odd then the player currently taking a turn will lose, and if N is even then the player currently taking a turn will win.

Edited by plasmid
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.