# a game between to players, a postive integer in base 10 with n digits is divisible by n

Two players $A$ and $B$ play the following game : $A$ starts given a positive integer $n$ greater than $1$,they alternaly choose an integer between $0$ and $9$ to form a $n$ digits integer in the decimal base : for example $A$ choose $a_1,B$ choose $a_2$,.........$a_n$ and the number in the decimal base is $a_n...a_2 a_1$.$A$ wins if at the end the number $a_n...a_2a_1$ is divisible by $n$, otherwise $B$ wins Find all positive integers for which $A$ wins and all positive integers for which $B$ wins.

• Can you prove that $A$ can always win for $n=2$? and also for $n=3$? But that $B$ can always win for $n=4$? – Gerry Myerson Mar 25 '18 at 0:50
• And what does the question have to do with the sum of the digits? That's in your title, but nowhere in the body of the question. – Gerry Myerson Mar 25 '18 at 0:51
• So,why not ask your friend how to do it? – Gerry Myerson Mar 25 '18 at 2:39
• Well, do you know what answer he got? It will be easier to do it, if we know what we're trying to do. – Gerry Myerson Mar 25 '18 at 12:19
• any ideas when n is prime ? – Mike Mar 26 '18 at 12:14

Update: This answer is now a complete solution.

The OP has clarified in comments that the rules of the game prohibit $0$ as an option for the final, lead digit, $a_n$. It turns out this makes a difference in at least one case, namely $n=11$. For the moment, at least, I'm going to give an answer just for that one case. (Update: see the "Added 4/7/18," below.)

Since $10\equiv-1$ mod $11$, we have

$$a_{11}a_{10}a_9a_8a_7a_6a_5a_4a_3a_2a_1\equiv a_1-a_2+a_3-a_4+a_5-a_6+a_7-a_8+a_9-a_{10}+a_{11}\mod 11$$

If $a_{11}=0$ were an option, then Player A would have an easy winning strategy: Choose $a_1=0$ and then let $a_{2k+1}=a_{2k}$ for $1\le k\le5$, which keeps the alternating sum at $0$ mod $11$ after each of Player A's moves. But this won't work if $a_{11}=0$ is not allowed, since Player B is allowed the option $a_{10}=0$, which Player A would be forbidden to match.

Indeed, Player B has the winning strategy here: Play randomly up to the tenth move, at which point the alternating sum is $S\equiv a_1-a_2+a_3-a_4+a_5-a_6+a_7-a_8+a_9$ mod $11$, and then play $a_{10}=S$ if $0\le S\le9$ and $a_{10}=9$ if $S=10$. In the first case, Player A lacks the option $a_{11}\equiv0$ mod $11$; in the second case, there's no option $a_{11}\equiv10$ mod $11$.

Added 4/7/18: Here's a complete solution.

For $n=2$, $5$, and $10$, Player A can guarantee a win by choosing $a_1=0$. For $n=3$, $7$, and $9$, she can win by choosing $a_n$ so as to make the number divisible by $n$; this is guaranteed because $n$ is relatively prime to $10$ and less than $10$. Finally, for $n=15$, $35$, and $45$, Player A can win by choosing $a_1=0$ (or $5$) and $a_n$ so as to make the final number divisible by $3$, $7$, or $9$, respectively.

Player B can win for all other values of $n\gt1$. Here's how.

For $n$ any multiple of $4$, Player B can choose $a_2=1$ or $2$; one of these choices guarantees the final number is not divisible by $4$. For $n$ any multiple of $25$, it's even easier: choose $a_2=1$.

If $n=2m$ with $m$ odd and relatively prime to $10$ (e.g., $n=6=2\times3$), Player B can choose $a_n=1$ or $2$; since $2a_{n-1}\ldots a_2a_1-1a_{n-1}\ldots a_2a_1=10^{n-1}\not\equiv0$ mod $m$, at least one of the choices gives a number not divisible by $m$, hence not by $n=2m$.

Finally (and this is the only really tricky case), if $n$ is an odd multiple of an odd number $m$ that is greater than $10$ and relatively prime to $10$ (e.g., $n=55=5\times11$), Player B can guarantee a win by doing a calculation on his last choice, $a_{n-1}$. For each of his $10$ options, Player B can check if Player A has a "counterdigit" $a_n$ that makes the final number divisible by $m$ (hence potentially by $n$). What's important is that a counterdigit for one option cannot be a counterdigit for another option: If $aba_{n-2}\ldots a_2a_1\equiv0$ mod $m$ and $b'\not=b$ (with $0\le b,b'\le9$), then

$$ab'a_{n-2}\ldots a_2a_1\equiv ab'a_{n-2}\ldots a_2a_1-aba_{n-2}\ldots a_2a_1=(b'-b)10^{n-2}\not\equiv0\mod m$$

since $\gcd(m,10)=1$ and $m\gt10\gt|b'-b|\gt0$. But Player A has only $9$ counterdigits available (because $a_n=0$ is not allowed). Therefore Player B has at least one choice that Player A cannot counter.

Remark: The proof just given of the final case depends crucially on the "anti-pigeonhole" principle (if you have $N$ pigeons but $N+1$ pigeonholes, at least one pigeonhole must remain empty...). But with the exception of $n=11$, it's possible (even likely) a different proof could be given showing that Player B can win whenever $n$ is divisible by an odd number greater than and relatively prime to $10$, even if $a_n=0$ is an option for Player A's final move. I haven't been able to come up with one, though; if anyone else can, I'd like to see it.

• Let's make the game easier ,the players can put the numbers in any order in a horizontal order as follow digit 1,digit 2,.....,digit n – Mike Apr 7 '18 at 10:11
• @Mike, it's a good idea to consider variants on the rules for a game, but it'd be best here to do so as a separate, stand-alone question (with a link to this question, to help provide context). MSE is geared for people to give answers to single, specific questions. – Barry Cipra Apr 7 '18 at 12:28