1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – Gerry Myerson Mar 25 '18 at 0:50
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Mar 25 '18 at 0:51
  • $\begingroup$ So,why not ask your friend how to do it? $\endgroup$ – Gerry Myerson Mar 25 '18 at 2:39
  • $\begingroup$ Well, do you know what answer he got? It will be easier to do it, if we know what we're trying to do. $\endgroup$ – Gerry Myerson Mar 25 '18 at 12:19
  • $\begingroup$ any ideas when n is prime ? $\endgroup$ – Mike Mar 26 '18 at 12:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mike Apr 7 '18 at 10:11
  • $\begingroup$ @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. $\endgroup$ – Barry Cipra Apr 7 '18 at 12:28

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.