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?

  • $\begingroup$ 99 is one number, not two? $\endgroup$ – JMP Jan 30 at 15:37

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.

| improve this answer | |
  • $\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$ – Ross Millikan Jan 31 at 3:11

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.