10
$\begingroup$

Players A and B alternate writing one digit to make a six-figure number. That means A writes digit $a$, B writes digit $b$, ... to make a number $\overline{abcdef}$.

$a,b,c,d,e,f$ are distinct, $a\neq 0$.

A is the winner if this number is composite, otherwise B is. Is there any way to help A or B always win?

$\endgroup$
  • $\begingroup$ A wins even if you drop the distinctness condition. It is rare that the first four digits lead to a winning position for B: 1122 1158 1416 1794 2101 2891 2962 3213 3676 4072 6838 7211 7277 8622 9616 9903 $\endgroup$ – starblue Jul 11 '16 at 16:57
15
$\begingroup$

Player A has a winning strategy. First, Player A picks $a = 3$.

Case I: Player B picks $b = 9$.

Then, Player A picks $c = 1$. If Player B picks $d = 7$, Player A can pick $e$ arbitrarily. If Player B picks $d \neq 7$, Player A picks $e = 7$. Following this strategy, $\{1,3,7,9\} \subseteq \{a,b,c,d,e\}$. So Player B is forced to pick $f \in \{0,2,4,5,6,8\}$, which makes $\overline{abcdef}$ composite.

Case II: Player B picks $b \neq 9$.

Then, Player A picks $c = 9$ and waits for Player B to pick $d$.

If $\{b,d\} = \{0,6\}, \{1,5\}, \{1,8\}, \{4,5\}, \{4,8\}, \{7,5\}, \{7,8\}$, then Player A picks $e = 2$.

If $\{b,d\} = \{1,2\}, \{4,2\}, \{7,2\}$, then Player A picks $e = 5$.

If $\{b,d\} = \{0,4\}, \{0,7\}, \{6,4\}, \{6,7\}, \{2,5\}, \{2,8\}, \{5,8\}$, then Player A picks $e = 1$.

If $\{b,d\} = \{0,1\}, \{6,1\}$, then Player A picks $e = 4$.

If $\{b,d\} = \{6,2\}, \{6,5\}, \{6,8\}, \{1,4\}, \{1,7\}, \{4,7\}$, then Player A picks $e = 0$.

If $\{b,d\} = \{0,2\}, \{0,5\}, \{0,8\}$, then Player A picks $e = 6$.

In all of these cases, $e$ was chosen such that $b+d+e \equiv 2\pmod{3}$. Hence, $a+b+c+d+e \equiv 2 \pmod{3}$. If Player B picks $f \in \{1,7\}$, then $a+b+c+d+e+f$ will be a multiple of $3$, and thus, $\overline{abcdef}$ is a multiple of $3$, and hence, composite. Otherwise, $f \in \{0,2,4,5,6,8\}$, and $\overline{abcdef}$ is composite.

Therefore, Player A can follow this strategy to guarantee that $\overline{abcdef}$ is composite, and thus, ensure that Player A wins the game.

$\endgroup$
8
$\begingroup$

This is community wiki because it is JimmyK4542's answer with different reasoning.

First note that if the final digit is 0, 2, 4, 5, 6, or 8 then the result is composite and A wins. In other words B can only win if the final digit is 1, 3, 7, or 9 and even then it is not guaranteed.

A gets to choose three digits. As in JimmyK4542's answer A chooses 3 first (9 works as well). If B chooses any of 1, 3, or 7 then A can choose the other two and guarantee a win. Thus, we only need to consider the cases where B's choice lies outside this set.

A chooses 9 as his second digit (or 3 if he chose 9 first). Again, if B selects either 1 or 7 then A selects the other and wins. Thus when A is going to select his third digit we need only consider the cases where B has selected two digits from the set $\{0, 2, 4, 5, 6, 8\}$.

A's strategy now is to select a number such that even if B chooses either of 1 or 7 that the number will be composite. Note that 1 and 7 are both equal to 1 mod 3 and 3 and 9 are both 0 mod 3. Therefore, A must ensure that his choice added to B's two previous choices equals 2 mod 3. Let us examine the three cases:

1) The sum of B's two numbers is 0 mod 3. We know that he cannot have chosen both 2 and 8, so choose one of them.

2) The sum of B's two numbers is 1 mod 3. Choose 1 or 7.

3) The sum of B's two numbers is 2. We know that he cannot have chosen both 0 and 6 so choose one of them.

And we are done.

I have added this answer because the reasoning may appear more intuitive to some and the strategy perhaps more direct.

$\endgroup$
2
$\begingroup$

If I understand it well, the players will tell $3$ digits of the number each. And given the distribution of primes among natural numbers (between $100,000$ and $1,000,000$, there are approximately $7.656\%$ of prime numbers), it is very likely that $A$ wins almost every time with numbers chosen at random (more than $92\%$ chance).

I'll attempt to show an intuitive and not-so-much-theoretical approach.

For $A$ to win every time, they just have to choose $e$ so that the final number cannot be a prime. We can show this is possible by pointing out that there is a way to choose $e$ and get no primes for every number between $\overline{abcde0}$ and $\overline{abcde9}$ for all distinct $a$, $b$, $c$, $d$, in $\left[0; 9\right]$, $a\ne0$.

I computed it with a Python program, and it appears that there are no hundreds between $100,0\text{xx}$ and $1,000,0\text{xx}$ that satisfy these conditions. We can always find some $e$ so that the final number is forced to be composite.

On the other hand, this shows that it is impossible to provide a strategy for $B$ to win, if $A$ chooses their digits well.

Hope that this suits your game rules (which I may have misunderstood), let me know in the comment section.

$\endgroup$
  • $\begingroup$ B loses if the number is composite. $\endgroup$ – xoxox Jul 11 '16 at 8:47
  • $\begingroup$ Right, I'll correct right away $\endgroup$ – BusyAnt Jul 11 '16 at 8:48
  • $\begingroup$ How can you choose the number $e$? $\endgroup$ – Zootopia Jul 11 '16 at 9:07
  • $\begingroup$ Isn't it written by $A$ ? $\endgroup$ – BusyAnt Jul 11 '16 at 9:13
  • $\begingroup$ What does your python code do? Checking whether, for fixed first four digits $a,b,c,d$, there exists $e$ such that $\overline{abcdef}$ is not prime for all digits $f$? $\endgroup$ – Batominovski Jul 11 '16 at 9:23
2
$\begingroup$

The existing answers can be simplified: their case splits are unnecessary.

For B to win it is necessary but not sufficient that the final digit B picks is in $\{1, 3, 7, 9\}$.

If A's first pick is $3$ and A ensures that the first three digits include $9$ (i.e. A picks $9$ for the third digit if B didn't pick it for the second digit), then when it comes to A's third pick (choosing the fifth digit from six unpicked digits) we have the following guarantees:

  • Both $3$ and $9$ have been picked
  • There is at least one unpicked digit equal to $1 \bmod 3$, and at least one equal to $2 \bmod 3$.
  • Either there is at least one unpicked digit equal to $0 \bmod 3$, or the sum of the first four digits is $0 \bmod 3$.

Therefore A can always choose the fifth digit such that the sum of the first five digits is $2 \bmod 3$. Then since B needs the final digit to be $1$ or $7$, the number will end up being divisible by $3$ and hence B cannot win.

$\endgroup$

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.