21
$\begingroup$

Alice and Bob play the following game, taking turns. Alice starts and writes a non-zero single digit number at the blackboard. At every turn, each player adds a single digit at the right of the current number until a number with 9 digits is reached. If this number is divisible by 11, Alice wins otherwise Bob.

Who has a winning strategy?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Does only the first digit need to be non-zero? You don't state anything about every other digits and I believe it might change the answer for your puzzle $\endgroup$
    – Rafalon
    May 12, 2021 at 10:18
  • 1
    $\begingroup$ only the first digit must be non-zero, there is no restriction for the other digits. $\endgroup$
    – ThomasL
    May 12, 2021 at 18:17

3 Answers 3

Reset to default
37
$\begingroup$

Note: This answer assumes that the non-zero restriction only holds for the first move, not for any subsequent digits, i.e. that the restriction was imposed only to ensure a valid 9-digit number was produced.

The winning player is

Bob

using the following strategy:

There is a well-known trick for reducing a number modulo 11, namely adding the digits at the odd positions and subtracting those at the even positions. In other words, Alice's moves minus Bob's moves results in a much smaller number with the same remainder mod 11 as the original nine-digit number.

Bob can do as his first move one less than Alice's digit, and in subsequent moves just copy Alice's digits. This ensures that the number is 1 modulo 11 after each of Bob's moves. Alice's last move can only result in a number that is 1 to 10 modulo 11, but not zero because that would require a digit of value 10.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ The divisibility trick works because $10\equiv-1$ (mod 11). Therefore $10^2\equiv+1$ (then apply linearity to the sum of digits x place position. Also interesting is that the first-turn restriction makes a difference. $\endgroup$
    – obscurans
    May 12, 2021 at 7:00
  • $\begingroup$ If that strategy were to work, there is a weakness: What if Alice starts with a 1? Bob has no move but to copy that and wait for a chance. What if Alice only plays 1s? It breaks down. But then it seems it does not work anyway. (trying not to reveal spoilers in this comment makes it harder to be clear what I mean, sorry!) $\endgroup$
    – AdamV
    May 12, 2021 at 10:46
  • $\begingroup$ @AdamV If Alice only plays ones, the number will be 101111111, which is not divisible by 11, making Bob win. Bob does not copy Alice in the first move. $\endgroup$
    – Jaap Scherphuis
    May 12, 2021 at 11:07
  • $\begingroup$ I think I misread that no numbers could be 0, not just the first for some reason. $\endgroup$
    – AdamV
    May 12, 2021 at 11:10
  • $\begingroup$ @AdamV Fair enough. On re-reading the question that is a little ambiguous. I assumed it was only on the first digit in order to make it a valid number without leading zeroes, and I hope I was right in that assumption. $\endgroup$
    – Jaap Scherphuis
    May 12, 2021 at 11:13
9
$\begingroup$

[Edit: I read the puzzle as requiring all digits to be non-zero, in which specific case...] The winning player is always

Bob

Because

As he plays the 8th digit, Bob must make the 8-digit number be divisible by 11. In order for the 9 digit number to also be divisible by 11, Alice would have to play a zero, which is not allowed.

The simplest way to achieve that goal is

to ensure the 8 digit number is divisible by 11 by copying every digit that Alice plays. A number of the form aabbccdd will always be divisible by 11.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ aabbccdd is eight digits, not the nine that are required. Alice has both the first and the last move in the game. $\endgroup$
    – Jaap Scherphuis
    May 12, 2021 at 11:07
  • 1
    $\begingroup$ Yes, but since aabbccdd is divisible by 11, she has no move except a zero. But I may have misread that as a restriction on all digits, not just the first. I can't downvote my own answer though... $\endgroup$
    – AdamV
    May 12, 2021 at 11:10
  • 1
    $\begingroup$ Maybe you can just edit your answer to explicitly state that assumption/interpretation, like I did with my answer just now. $\endgroup$
    – Jaap Scherphuis
    May 12, 2021 at 11:20
2
$\begingroup$

If the leading digit could be zero, which it can't, but if it could, then

Alice wins

by

playing $0$ first, then copying all of Bob's moves.

This results in

an eight digit number of the form $AABBCCDD$, which is always divisible by eleven.

Note that

this is the same as Bob's winning strategy in the original game, but with a different opening.

@obscurans pointed this out in a comment

Improve this answer
$\endgroup$

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.