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

Question

There are two players and referee. We mark players I and II. Referee says any positive divisor of the number $10^n$. 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 $10^n$ 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) \times (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 1

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\in[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 $\{(\cdot 2),(\cdot 5),(\div 10)\}$. The top-left corner is $(0,0)$ equivalent to $2^05^0$ and the bottom-right corner is $(n,n)$ equivalent to $2^n5^n$.

We can represent the solutions as a $(n+1)\times (n+1)$ matrix $A$ where the $a_{ij}$ entry is $0$ if the first player has a winning strategy starting on square $(i,j)$ equivalent to referee picking the number $2^i5^j$, 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:

Where notice the following patterns (Conjectures):

---

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

$$ a_{ij}= \begin{cases} 1, & (i\text{ is even, }j\text{ is even}), & (\color{blue}{\text{blue}})\\ 1, & (i,j)\in I_e(n), & (\color{darkblue}{\text{dark blue}})\\ 0, & \text{otherwise}, & (\color{green}{\text{green}}) \end{cases} $$

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

So far for $n\le 9$, we observed the sporadic examples:

• $I_e(0)=I_e(2)=I_e(4)=\emptyset$
• $I_e(6)=\{(3,4),(3,6),(6,3),(4,3)\}$
• $I_e(8)=\{(3,8),(5,8),(4,5),(5,4),(8,5),(8,3)\}$

---

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

• $a_{ij}$ alternates $1,0$ $\text{ }(\color{blue}{\text{blue}},\color{green}{\text{green}})$ on the main diagonal and specially $a_{n,n}=1$ $\text{ }(\color{blue}{\text{blue}})$.
• Else (if we are not on the main diagonal), as we are moving away from some diagonal square $a_{k,k}$ for $k\ne 1$ in the positive direction (right or down):

1. If $(a_{k,k}=1)$, we have a single $0$ $\text{ }(\color{green}{\text{green}})$ followed by a line of all $1$'s $\text{ }(\color{blue}{\text{blue}})$.
2. If $(a_{k,k}=0)$, we have alternating squares $0,1$ $\text{ }(\color{green}{\text{green}},\color{blue}{\text{blue}})$.

• Otherwise, for $k=1$, we have a line of $0$'s $\text{ }(\color{green}{\text{green}})$ in the positive direction (right or down) except for the last square $a_{1,n}=a_{n,1}=1$ $\text{ }(\color{blue}{\text{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 $I_e(n)$ follow.

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