Divisor game

Probability Level 3

Let $N \ge 2$ be a positive integer. Alice and Bob play the following divisor game: starting with the set $D_N$ of positive divisors of $N$ , the players take turns removing some elements from the set. At a player's turn, he or she chooses a divisor $d$ that remains, and removes $d$ and any of the divisors of $d$ that remain. The player who moves last loses .

For example: $N = 18, D_N = \{ 1,2,3,6,9,18 \}$ . Alice chooses $d=2$ , so she removes $1$ and $2$ . The remaining set is $\{3,6,9,18\}$ . Bob chooses $d = 9$ and so must also remove $3$ . The remaining set is $\{6,18\}$ . Alice takes $6$ , and now Bob is forced to take $18$ , so he loses.

Let $n \ge 2$ be the largest positive integer $\le 200$ such that if Alice and Bob play the divisor game for $n$ and both of them play optimally, the second player wins. Find $n$ . If no such $n$ exists, enter $999$ .

The answer is 999.

1 solution

Ivan Koswara
Jan 20, 2016

This is a simple application of the strategy-stealing argument.

Note that since $n \ge 2$ , the game needs at least two moves, and thus the second player must make a move. Suppose the second player has a winning strategy. Consider the move $m$ that the second player makes when the first player plays 1. By assumption, this move holds the win for the second player; that is, the player that is not moving. But now the first player can play on $m$ immediately on the first move. This situation is identical as before (since playing 1 only removes 1, and playing $m$ will remove all divisors of $m$ which include 1), and thus the winner should be the player not to move. But since it's the first player that made the move $m$ , it's the first player that is not to move, and thus the first player is winning, contradicting the assumption that the second player has a winning strategy. Thus the assumption that the second player has a winning strategy is false; the first player must win for all $n \ge 2$ .

(Note that the above argument doesn't work if $n = 1$ , because the second player wins by not moving, and so the first player cannot steal this "move".)

Moderator note:

Great! The strategy-stealing argument provides an existential solution, without considering the construction aspect.

This is very interesting. If the rule changes so that 1 is not include in the $D_N$ then what is the number will be?

Tran Hieu - 5 years, 4 months ago

199, because the player will be forced to choose the only number 199 and the second player wins. :-D

Jerry Hill - 5 years, 4 months ago

But can 200 work? And in general, beside prime, what type of number will guarantee the second player win?

Tran Hieu - 5 years, 4 months ago

@Tran Hieu – This is a good question. Essentially you are asking about the correct strategy for the first player--is choosing 1 always a winning first move if the number is not prime?

I can tell you that the answer is no, and I can give you an example of a number for which it is not, namely $n=36$ . Can you show why $1$ isn't winning for $n=36$ ?

Patrick Corn - 5 years, 4 months ago

@Patrick Corn – @Patrick Corn -- Ah, good example! Since 36 = (2^2)(3^2), removing either 2 or 3 leaves the other player in a losing position.

So perhaps a rule for this is that if n = ((p1)^(m1))((p2)^(m2))...((pk)^(mk)), where (pi) and (mi) are the ith prime factor (excluding 1) and ith corresponding exponent, then the first player is automatically in a losing position if k is odd, and can otherwise win by choosing any of the prime factors.

In know I'm like 4 years late to this conversation, but considering I am here looking at these comments, Bayesian thinking leads me to suppose that someone else will likely also be reading these comments. :)

Christian Brown - 12 months ago

@Christian Brown – Determining a winning first move is nontrivial in general. But in this case, removing 2 or 3 doesn't work. The next player can remove 6, leaving the divisors $4,9,12,18,36.$ This is losing for the person whose turn it is to move: if that person takes 4 or 9, the other person takes 9 or 4; if that person takes 12 or 18, the other person takes 18 or 12.

For numbers $n$ with exactly two prime divisors, this game is isomorphic to the classical version of a game called Chomp, which has some interesting properties.

Patrick Corn - 12 months ago

Divisor game

The answer is 999.

1 solution

Moderator note:

0 pending reports