5
$\begingroup$

Adam and Bob play a game on a blackboard. A number $n>1$ is initially written on the board, and alternately they replace the number $k$ currently written with one of these:

  • A) A positive divisor of $k$, different from $1$ and $k$ itself. If the player chooses this move, he gains 1 point. Of course, if $k$ is prime, this move cannot be chosen!
  • B) $k+1$. Choosing this move implies the loss of 1 point.

The players start with 200 points each.
When a player runs out of points, he loses. Assuming that Adam starts the game, for which values of $n$ Bob has a strategy for victory?

Note: the players always play optimally, they're incredibly smart. The value $n$ isn't chosen by the players, it's random.

$\endgroup$
  • 1
    $\begingroup$ How many points do each of the players start with? $\endgroup$ – MisterEman22 May 22 '15 at 19:47
  • $\begingroup$ It's 200, forgot to say! $\endgroup$ – leoll2 May 22 '15 at 19:52
  • $\begingroup$ A partial answer is that a player who receives a $6$ wins. (They can force the cycle of moves $3$, $4$, $5$, $6$ until the other player runs out of points). Someone who receives a $5$ loses, so anyone who receives $5k$ wins. $\endgroup$ – Milo Brandt May 22 '15 at 20:01
  • 1
    $\begingroup$ For those saying it's too broad, it's not! Ask here and I'll clarify! $\endgroup$ – leoll2 May 22 '15 at 20:07
  • 1
    $\begingroup$ I'm not sure why someone voted to close this question. It seems perfectly fine to me! $\endgroup$ – Kevin May 24 '15 at 19:00
3
$\begingroup$

As an appetizer, here is an insightful, but incorrect strategy which we will develop into a correct strategy:

If you receive a composite number, write down an odd prime factor $p$ of it. The opponent will write down $p+1$, which will be composite again.

This suggests that all composite numbers are wins (i.e. wins by the player who receives the number - so Adam would win these, not Bob). The only issue here is that the strategy breaks down if the given number $n$ is of the form $2^k$, as it would have no odd prime factors. In fact, noting that the first player may force the cycle $2,3,4,5,6,3,4,5,6,\ldots$, we find that $2$ is a win, despite being prime. Similarly $8$ is a loss, despite being composite.

Motivated by the above strategy we ask: What is the set $P$ of primes which are winning positions? To figure this out, consider that for $p\in P$, we must have that $p+1$ is a losing position. However, for $p$ other than $2$ it holds that $p+1$ is composite. In this case, it must be that all prime factors of $p+1$ are in $P$, as otherwise $p+1$ would be a win by playing a losing prime factor of it (i.e. one not in $P$). More generally, $p+1$ must not be divisible by any losing position $n'$, as moving to $n'$ would then be a winning strategy for $p+1$, making a $p$ a loss.

Using the above observations, we may prove that $$P=\{2,7,13\}.$$ Now, for contradiction, let $p$ be the minimal winning prime not in the above set. The above arguments suffice to show that $$p+1=2^a7^b13^c$$ for some integers $a,b,c$. Moreover, one may quickly check that all of the following are losing positions by tracing out a few moves until the earlier mentioned cycle is achieved by the opposing player: $$2^3=8$$ $$7^2=49$$ $$13^2=169$$ $$2\cdot 7=14$$ $$2\cdot 13=26$$ $$7\cdot 13=91$$ The only non-trivial products of the form $2^a7^b13^c$ not divisible by one of the above are $2$, $4$, $7$, and $13$, all of which are winning positions. However, none of the six losing values listed are one greater than a prime not already in $P$ - hence there is no valid solution for $p$ and our list of winning primes is complete. Moreover, the six losing values listed are all of the losing composite values.

Using the above, we can find that, if you receive $n$ on your turn, then the optimal move is:

  • If $n$ is prime or equals $4$, then play $n+1$.

  • If $n$ is one of $\{8,\,49,\,169,\,14,\,26,\,91\}$ then it doesn't matter what you do. You lose.

  • If $n$ is of the form $2^a7^b13^c$ and not in one of the above cases, then play one of $\{8,\,49,\,169,\,14,\,26,\,91\}$ (at least one of which must be legal).

  • If $n$ is composite and has a prime factor other than $2$, $7$, or $13$, play some such prime factor.

This attains a win from all winning positions, and is hence optimal. It is obvious that the player destined for a win will not run out of points too soon, as they will always be choosing a divisor, except for $n=2,\,4,\,7,\,13$, and the game will pass through each of those numbers at most once (before reaching the win at $n=6$) - so as long as each player has at least $5$ points, it won't affect the result. To answer the puzzle, Bob has a winning strategy for:

  • Any prime other than $2$, $7$, and $13$

  • The numbers $8,\,49,\,169,\,14,\,26,$ and $91$.

$\endgroup$
  • 1
    $\begingroup$ Man, this puzzle didn't look that hard when I started writing this! $\endgroup$ – Milo Brandt May 22 '15 at 21:40
  • $\begingroup$ "Bob has a winning strategy for" Should be "Bob has a winning strategy except for" $\endgroup$ – Taemyr Oct 16 '15 at 6:35
  • $\begingroup$ @Taemyr The post is correct; the list I give is the set of losing positions in the game which are losses for Adam (the first player) and wins for Bob (the second player). Consider a particular example, like $5$, which is on the final list, and is clearly a loss for Adam. $\endgroup$ – Milo Brandt Oct 16 '15 at 17:24
0
$\begingroup$

A 3-4-5-6-3 loop pattern can be described as: Player 1 gets the 3 and is forced to lose a point and go to 4. Player 2 chooses to lose a point and go to 5 forcing Player 1 to go to 6 losing another point. Player 2 then chooses 3 getting his point back. This nets a result of -2 for Player 1 and 0 for Player 2.

The following scenarios result from a 3-4-5-6-3 loop
2: A+1 => 3; B+1 => 4; A+1 =>5; B+1 =>6; A Sets to 3; Result A wins.
3: A+1 => 4; B+1 => 5; A+1 =>6; B sets to 3; Result B wins.
4: A+1 => 5; B+1 => 6; A sets to 3; Result A wins.
5: A+1 => 6; B Sets to 3; Result B wins.
6: A sets to 3; A wins.

Landing an 8 can be described by the following: Player 1 can go to 2 or 4 (see above) or can increment to 9 losing a point. Player 2 then chooses 3 (see above).

7: A+1 => 8; A wins
8: B wins

At this point we know that Bob will win 3, 5, or 8. Adam will win 2,4,6,7 and any multiple of 3,5,or 8 (excluding 3,5 and 8)

11: A+1 => 12; B sets to 3; B Wins (We can conclude that any prime number that is x-1, where x is a winning number for Player 1, will result in a winning number for Player 2.

Bob wins if one of the following is met:

  • n = 3
  • n = 5
  • n = 8
  • n is a prime number that is 1 less than a winning number for Adam

(I realize this is most likely an incomplete set)

$\endgroup$
0
$\begingroup$

So far we have this list of winning numbers (if player A gets one of these numbers, then player A will win):

2, 4, 6, 7, 9, 10
In addition, all numbers that are multiples of a losing number will be a winning number, because if Player A got those numbers, they could simplify it to the losing number for the other player to get.

And here are all the losing numbers (if player A gets one of these numbers, then player A will lose):

3, 5, 8, 11

I'll go about answering this by making a set of rules: (If someone could edit this and put the rules in spoilers I'd appreciate it. Not sure if that's possible using ul/ol. I couldn't figure how to do the normal spoiler with lists)

  • If a number can be simplified to a losing number, then it is a winning number
  • Someone who receives a 5 loses by the following turn order:
      1. A receives 5, forced to put 6; -1
      2. B puts 3; +1
      3. A forced to put 4; -1
      4. B puts 5; -1
      5. This move sequence repeats, with B forcing all of A's moves
    This leaves A with a -2 net and B with a 0 net, meaning that B eventually wins. Let's call this set of turns LS5 (loss sequence 5).
  • From the LS5, anyone who gets a 3 would also lose
  • Again building off LS5, anyone who can force a 5 or a 3 would win. This means that anyone who is given a multiple of either 5 or 3 could use move A to give the other player 5 or 3 respectively
  • A player should never use move A to simplify to a 2, because the opponent could use move B to make it 3, and thus eventually winning by LS.
  • A player that receives an 8 loses by the following turn order:
    1. A gets 8, puts 4
    2. B gets 4, puts 5; LS5 continues, A loses
    -OR-
    1. A gets 8 puts 2, loses by the rule above
    -OR-
    1. A gets 8, puts 9
    2. B gets 9, puts 3; LS5 continues, A loses
    By this, a player that gets 9 wins. Let's call these LC8 and LC9
  • A player that gets 10 uses move A to return 5 and wins by LC5.
  • A player who gets 11 loses by:
    1. A gets 11, must make it 12
    2. B gets 12, makes it 3, wins by LC5
$\endgroup$

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.