# Two persons play the following game

Two persons play the following game. They in turn called the four-digit numbers that do not have zeros in the record, and the sum of digits is divisible by $9$. In this case, each successive number must start with the same numbers, which ends the previous one, for example: $3231 - 1539 - 9756 - 6561 ...$ . Repeat number is impossible. Anyone who can not call another number loses. Who are the players - novice or his opponent - can win independence from other games?

• Not easy to understand. What does "in the record" mean? What does "win independence from other games" mean? – Gerry Myerson Feb 26 '17 at 5:22
• So, Chyev, care to clarify? – Gerry Myerson Feb 27 '17 at 9:29

Solution: Here is my solution to the problem which I've interpreted to mean as follows:

Two persons play the following game. They in turn call four-digit numbers where no digit is zero, the sum of whose digits is divisible by 9. Each following number must start with the last digit of the previous number called, for example: 3231−1539−9756−6561...3231−1539−9756−6561... . Numbers may not be repeated. The first person who cannot call a number loses. Does this game have a winning strategy and if so, what is that strategy?

First of all note there are nine 4-Digit No-Zero divisible-by-9 numbers (I will call them 4DNZ9 numbers) which are symmetric, namely 1881, 2772, 3663, 4554, 5445, 6336, 7227, 8118, and 9999. The winning strategy: player one first plays one of these symmetric 4DNZ9 numbers, say $nxxn$, forcing player two to choose another number starting with $n$, and on each subsequent round, player one will play the transpose of player two's number.

Since player two's numbers must begin with $n$, their transpose will end with $n$, forcing player two to continually choose numbers beginning with $n$ until those numbers are exhausted (clearly there are a finite number of 4DNZ9 numbers beginning with $n$, in fact it can be shown there are exactly 81, one of which is symmetric). Every non-symmetric 4DNZ9 number starting with $n$, say $nxyz$ has a unique transpose not starting with $n$, namely $zyxn$. Thus player one can always force player two to choose a number beginning with $n$. As there is only one symmetric 4DNZ9 number for each $n$, player two cannot force player one to choose a number beginning with $n$. Player two will lose on their 81st play, no longer being able to supply a number beginning with $n$.

As this is getting a bit abstract, let's choose an example $n$, say 6. Player one would choose 6336 as her first number. If player two then chooses 6948, player one then chooses 8496. Player two is then forced to pick another number beginning in 6, say 6939. Player one in turn will choose 9396, and so on. As 6336 is the only symmetrical 4DNZ9 number beginning with 6, player two will not be able to force player one to pick a number beginning with 6. However, each number played by player two will have a unique transpose and player one will be able to play that transpose forcing player one to choose yet another number beginning with 6. Eventually player two will run out of options.

Below are my first few posts if anyone wants to see the process I went through to get to the answer

I think 'in the record' is a mis-translation and it just means none of the 4 digits in the number are zero. The 'independence from other games remark' I'm not so sure of, but I think it can be disregarded.

My best guess is we can just assume both players don't make mistakes and we want to know if the player who plays first or second will be the winner.

I'd like to know from the original poster what attempts they've made so far to solve the problem.

Edit: I've worked on the problem as formulated above. I believe I've solved it in the following manner:

The sum of the digits must be either 9, 18, 27, or 36. For the sum to be 9, the only numbers you get must use the following sets of digits, 6111, 5211, 4311, 4221, 3321, or 3222. There are an even number of ways to permute the digits, either $\binom{4}{1} = 4$ (for example 6111, 1611, 1161, 1116), or $\binom{4}{2}*2 = 12$ (as for 5211). Thus there are an even number of numbers whose digits sum to 9.

You can work the same way for 18 and 27, getting even numbers from the permutations though it's a bit more work, especially 18.

However, 36 is a special case--only one way to get that, namely 9999. Hence in the end you will add four even numbers and 1, so there are an odd number of the four-digit numbers fitting the requirements. That means the first person should win.

I've left a lot sketchy here--specifically the cases where the sum is 18 and where it is 27. I'm also sure there's a much more elegant way to do this problem; my method, even if it is correct, is definitely brute force.

Edit #2: Method 2 Consider the four digit number $abcd$. We know the sum $a+b+c+d$ is either 9, 18, 27, or 36. There is as above only one way to get 36, namely 9999. However, to get 9, 18 or 27, it is impossible to get $a=b=c=d$. Thus we are left with following 4 possibilities: 1) three numbers the same and one different (like 6111) in which case there are 4 ways to permute as above; 2) two pairs (6633 is an example) which will have $\binom{4}{2} = 6$ ways to permute; 3) one pair and two other unique number (6642 is an example) which can be permuted $\binom{4}{2}*2 = 12$ ways; and 4) all unique digits(9531 is an example) , which can be permuted 4! = 24 ways. In all cases except 9999 we have an even number, therefore the total is odd and the first player wins.

Edit #3: My solution is incorrect and incomplete as I missed the part where he says first digit of the new number must be the same as the last digit of the previous.

Edit #4: 8-) As I was falling asleep, I think I found a winning strategy. The first player chooses a symmetric number (like 9999 or 8118). After that he transposes the number given by player 2. So if player 1 gives 9999 and player 2 gives 9981, Player 1 next gives 1899 forcing Player 2 to give another number starting with 9. Player 1 continues in this way, exhausting all 81 numbers starting with 9. This is just a sketch, I'll fill out details tomorrow when I wake up. (Note that for each first digit, 1 to 9, there are 81 numbers of 4 digits not using 0's that are multiples of 9 as required, but only one that is symmetric, and you could start with any one of those symmetric numbers and keep player 2's choices isolated to a group of 81 until she runs out.)

• "can win independence of other games" should mean "has a winning strategy," which seems to be the general consensus. – Fabio Somenzi Feb 26 '17 at 6:01