Winning strategy in a game with the positive divisors of 10n10^n

There are two players and referee. We mark players I and II. Referee says any positive divisor of the number 10n. Thereafter, the players alternate turns with player I starting. In each turn, a player can multiply by a prime number (2 or 5) or divide by a 10 the integer number that another player said during the previous turn so that the result is a positive divisor of the number 10n that players did not say before. A player who cannot move is considered to lose the game. Which player has a winning strategy depending on the number called by the referee?

My work. I proved that this problem is equivalent to the following problem: “Two players move “rook” on the chessboard (n+1)×(n+1). In one move, the “rook” can be moved horizontally to the right or vertically downward by just one square. Also, in one move, the “rook” can be moved diagonally up and to the left by just one square. The referee chooses the starting position of the “rook” on the chessboard. Thereafter, the players alternate moves with player I starting. In each move, the player moves the “rook” to the square, in which she had never been before. A player who cannot move is considered to lose the game. Which player has a winning strategy depending on the starting position of the “rook”?”

Answer

Edit: I will pass on the +150 bounty (or more) to whoever solves the question.

Too long for a comment. I conjecture patterns based on brute-forced n[0,9].


As already discussed, the game is equivalent to two players taking turns moving a piece on a (n+1) chessboard, such that they can’t revisit a square. The legal moves are {(+1,0),(0,+1),(1,1)} which are equivalent to {(2),(5),(÷10)}. The top-left corner is (0,0) equivalent to 2050 and the bottom-right corner is (n,n) equivalent to 2n5n.

We can represent the solutions as a (n+1)×(n+1) matrix A where the aij entry is 0 if the first player has a winning strategy starting on square (i,j) equivalent to referee picking the number 2i5j, and 1 otherwise (second player has a winning strategy).

Assuming my C++ program does not have any unexpected flaws,

I have brute-forced the solutions for n=0,1,2,3,4,5,6,7,8,9.

If we color 0‘s and 1‘s with green and blue (dark blue), we get the following matrices:

enter image description here

Where notice the following patterns (Conjectures):


If n is even, chessboard (matrix) has odd dimension, then:

aij={1,(i is even, j is even),(blue)1,(i,j)Ie(n),(dark blue)0,otherwise,(green)

Where Ie are sporadic examples not included in cases when i,j are both even.

So far for n9, we observed the sporadic examples:

  • Ie(0)=Ie(2)=Ie(4)=
  • Ie(6)={(3,4),(3,6),(6,3),(4,3)}
  • Ie(8)={(3,8),(5,8),(4,5),(5,4),(8,5),(8,3)}

If n is odd, chessboard (matrix) has even dimension, then:

  • aij alternates 1,0  (blue,green) on the main diagonal and specially an,n=1  (blue).
  • Else (if we are not on the main diagonal), as we are moving away from some diagonal square ak,k for k1 in the positive direction (right or down):
  1. If (ak,k=1), we have a single 0  (green) followed by a line of all 1‘s  (blue).
  2. If (ak,k=0), we have alternating squares 0,1  (green,blue).
  • Otherwise, for k=1, we have a line of 0‘s  (green) in the positive direction (right or down) except for the last square a1,n=an,1=1  (blue).

Following this pattern, there are no sporadic examples so far.


These are just observations.

I am not yet sure what pattern will the sporadic examples Ie(n) follow.

I am also still trying to prove the non-sporadic pattern(s) for all n.

Attribution
Source : Link , Question Author : Witold , Answer Author : Vepir

Leave a Comment