13
$\begingroup$

The numbers 1,2,3, ..., 99 are written on the blackboard. Alice and Bob play the following game, taking turns. Alice starts. At every turn, each player removes one number until two numbers are remaining. If the sum of those two numbers is divisible by 7, Alice wins otherwise Bob.

Who has a winning strategy?

$\endgroup$
3
  • $\begingroup$ 99 is one number, not two? $\endgroup$
    – JMP
    Commented Jan 30, 2020 at 15:37
  • $\begingroup$ This puzzle appears as number 33. in the famous Russian book "mathematical circles", with $21$ and $5$ instead of $99$ and $7$ $\endgroup$ Commented Sep 8, 2022 at 0:54
  • $\begingroup$ Hi. I have seen another puzzles posted by you with characters Alice and Bob and the sentence "Who has a winning strategy?". Are these puzzles your own creations or there is a source for them? $\endgroup$
    – user70797
    Commented Aug 6, 2023 at 11:53

1 Answer 1

19
$\begingroup$

I believe this is the answer.

Alice has a winning solution

The strategy is below.

The numbers $1,2,...,99$ can be split by their value modulo 7. This gives us 14 numbers that are $0,2,3,4,5,6$ modulo 7 and 15 numbers that are $1$ modulo 7. So Alice first removes a number that is 1 mod 7. Now, we can pair the numbers with each other such that each one is paired with another such that they sum to a number mod 7. We can do this because their are 14 in each 'class' the 1's pair with the 6's, 2's with 5's, 3's with 4's and finally the 0's can be split in half and paired with each other. Each time Bob removes a number, Alice removes one from the corresponding class. Thus, when Alice removes the last number she can ensure that the resultant sum is 0 mod 7.

Edit: Slightly clearer response with strategy.

Alice removes 1. Bob's number will be $0, 1, 2, 3, 4, 5$ or $6$ modulo 7. There are 14 of each (important that this is even). Alice can maintain that the sum is always 0 mod 7 no matter what Bob removes as she can remove something from a corresponding class (0 with 0, 1 with 6, 2 with 5, 3 with 4). Since there are an equal number in each class (and an even number in the 0 class) Alice can always do this. Thus, at the end when she removes the last number she can still ensure it is 0 mod 7.

$\endgroup$
1
  • $\begingroup$ It only matters that the number that are $0 \bmod 7$ is even. For all the others it matters that the number in corresponding classes is equal, so we could have $13$ that are $1 \bmod 7$ and $13$ that are $6 \bmod 7$ without changing the answer. Well done. $\endgroup$ Commented Jan 31, 2020 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.