8
$\begingroup$

Alice and Bob play a game starting from Alice where Alice and Bob are supposed to write a number to the board, Then the game goes through several rounds between Alice and Bob with the rules below:

  • Alice goes first and writes on the board a positive integer less than or equal to our top-limit number $2017$. After this, neither player can write down either that number or any of its divisors.
  • Then Bob writes another number, after which again neither player can write down that number or any of its divisors.
  • Alice and Bob continue to take turns to write a new number no multiple of which has been written before.
  • Whoever manages to play last is the winner.

And As we all know Alice and Bob, they are smart and play the optimal strategy.

For example,

Let say the top limit number was $5$:

$1-2-3-4-5$

Alice: $4$ (Then $1$,$2$ and $4$ would be eliminated)

$ - -3- -5$

Bob: $5$

$ - -3- - $

Alice: $3$

Alice Wins!

Who will win at the end, with best play on both sides, if the top-limit is $2017$?

$\endgroup$
  • $\begingroup$ You're welcome! I hope I haven't made your puzzle unrecognizable. $\endgroup$ – Gareth McCaughan Oct 7 '17 at 22:43
  • $\begingroup$ @GarethMcCaughan you made it better! $\endgroup$ – Oray Oct 7 '17 at 22:44
17
$\begingroup$

This game

is a first-player win whatever our "top limit" is.

Here's why:

Suppose first of all that the first player begins by playing 1. Perhaps this leads to a win for the first player with best play, in which case we've found a winning first move and we're done. Otherwise, the second player has a win from that point; let's say they win by playing n. OK then: the first player can begin by playing n, leading to the exact same position as after 1, n but with the roles reversed -- which means that the first player wins.

In summary,

if opening with 1 is not a win for the first player, then opening with what the second player refutes it with is a win for the first player.

$\endgroup$
  • $\begingroup$ @Oray Still works for top limit 7. $\endgroup$ – EKons Oct 8 '17 at 9:56
  • $\begingroup$ @ΈρικΚωνσταντόπουλος you are right :) $\endgroup$ – Oray Oct 8 '17 at 10:01
  • $\begingroup$ Is it necessary that in a game without draws, some player must be able to force a win? $\endgroup$ – Neil W Oct 8 '17 at 14:51
  • $\begingroup$ Yes. Suppose player 1 cannot force a win. Then player 2 can play in such a way as to guarantee that player 1 doesn't win. Since there are no draws (note: I assume infinitely-prolonged play counts as a draw for this purpose) the only way this can happen is for player 2 to win instead. $\endgroup$ – Gareth McCaughan Oct 8 '17 at 14:53

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.