Alice and Bob are playing a game. They write down the integers between $1$ and $100$ (inclusive). First, Alice chooses a number she likes and deletes it, and then Bob chooses to delete another number among the divisors and multiples of the one Alice deleted. Then Alice repeats what Bob has done, choosing another number among the divisors and multiples of the one Bob deleted. The game continues until one of them has no choices and the other wins.

For example, Alice chooses $94$. Bob chooses $47$. The only choice left for Alice now is $1$. And then Bob chooses $97$ to win the game.

To make the question interesting, we add the restriction on Alice that she can only begin with an even number.

The question is: Does Alice have a winning strategy?

It can be interpreted as a graph. The graph has $100$ vertices and has edges between every divisor-multiple pair. When a point is deleted, if every point with an edge to the deleted point has no winning strategy for Alice, then the deleted point has a winning strategy for Bob. But I can't run the program on my PC. Maybe there is a wiser strategy?

  • $\begingroup$ Sorry I mean $94$. I'll edit it. $\endgroup$ – Oolong milk tea Jan 27 at 8:06
  • $\begingroup$ If there is a "maximal" match (which means that no other match contains the all the matched point in this match and still more than $1/2$ unmatched point.) for an even number such that the even number remians unmatched, then first to delete the even number will give a winning strategy for Alice by delete vertices according to the match. $\endgroup$ – Oolong milk tea Jan 27 at 10:52

If at any time Bob chooses $1$ then Alice chooses $97$ and wins. So in the following I will ignore this choice for Bob.

Alice wins by playing $62$. There are two possibilities.

Bob chooses $31$

Alice now forces the following sequence where Alice's choices are asterisked. She always chooses a product of two primes greater than $50$ where one of the primes has already been used and so Bob has no choice (other than $1$).

$*93*,3,*51*,17,*85*,5,*95*,19,*57*$ and now $1$ is forced.

Bob chooses $2$

Alice now forces the following sequence.

$*58*,29,*87*,3,*51*$ and now as in the above sequence.

  • $\begingroup$ Is this the only solution? $\endgroup$ – Asker Jan 27 at 16:57
  • 1
    $\begingroup$ I don't imagine so. See if you can find others! $\endgroup$ – S. Dolan Jan 27 at 17:12

EDIT : Oops, misread the question. This would be too easy.

Alice chooses a prime number bigger than 50 (Grothendick would say 57) ; then Bob's only choice is 1, and then Alice can choose any number again. She picks a new prime number bigger than 50, and Bob is stuck.

For your program, take care : the strategy depends on which numbers have already been played, so you can't decide whether a starting point is winning by analysing the other starting points' results.


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.