14
$\begingroup$

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"?"

$\endgroup$
12
  • 3
    $\begingroup$ In other words, you have a piece on a $(n+1)\times (n+1)$ chessboard whose legal moves are $\{(+1,0),(0,+1),(-1,-1)\}$, and it can't revisit a visited square. Players alternate moving the piece. The judge names the starting square. Question: Does the starting square count as already visited, or not? $\endgroup$
    – Vepir
    May 26 '20 at 15:06
  • 1
    $\begingroup$ @Vepir You correctly described the condition of the problem. Yes, the starting square is considered already visited. $\endgroup$
    – Witold
    May 26 '20 at 15:10
  • 2
    $\begingroup$ How? The central square is taken by the judge (Since you said that the starting square is considered already visited). The player I moves to the upper left corner. WLOG The player II is forced to go down. Then the player I is forced to go down. Then the player II is forced right. Then the player I is forced right. Then the player II has no moves, and loses? $\endgroup$
    – Vepir
    May 26 '20 at 16:03
  • 2
    $\begingroup$ It seems that if $k$ and $m$ are both even, then the second player wins. Otherwise, it is useful to consider the cases when $n$ is even and when $n$ is odd, separately. $-$ there are also some fixed patterns such as for example: "Second player always wins if we start at $(k,m)=(n,n)$ by only playing $\{(+1,0)\}$, or due to symmetry, by only playing $\{(0,+1)\}$, because then the first player is always forced to play $\{(-1,-1)\}$". $\endgroup$
    – Vepir
    May 26 '20 at 19:02
  • 3
    $\begingroup$ For $n=1,2,3$, the winning players at each starting square (as in @Vepir's setting with Player I and II denoted by A and B) are$$\begin{bmatrix}A&B\\B&A\end{bmatrix},\begin{bmatrix}B&A&B\\A&A&A\\B&A&B\end{bmatrix},\begin{bmatrix}B&B&A&B\\B&A&\color{blue}B&A\\A&\color{blue}A&A&B\\B&A&B&B\end{bmatrix}.$$ $\endgroup$
    – Saad
    May 27 '20 at 4:25
7
+150
$\begingroup$

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:

enter image description here

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$.

$\endgroup$
13
  • 1
    $\begingroup$ Thank you very much for your work! I have no doubt that your computer program is working correctly. I wrote a program in Pascal ( ideone.com/KDtrXG ). My program for $n = 0,1,...,7$ produces the same results as your program (if $n = 8,9$, then the time of the calculations performed by my program is too long). $\endgroup$
    – Witold
    May 27 '20 at 13:34
  • 2
    $\begingroup$ @Witold I have finished $(n=10)$ (i.stack.imgur.com/GHcIU.png), which has:$$ I_e(10)=\{(1,6),(5,6),(4,7),(6,7),(5,10),(10,5),(7,6),(7,4),(6,5),(6,1)\}$$ $\endgroup$
    – Vepir
    May 27 '20 at 15:11
  • 2
    $\begingroup$ @Witold Why accept my partial answer? We still do not know what will happen for larger even $n$, and the odd $n$ pattern wasn't formally proven. I think it is better to not accept my answer (you can remove the check-mark), if you are still curious about the full solution (I myself am curious, but am not able to complete the solution.). $-$ P.S. You could maybe try cross-posting the question on MO if you think you will not get a full answer here. (If you do that, make sure to mention that the question was originally asked here to keep both questions interlinked). $\endgroup$
    – Vepir
    Jun 2 '20 at 17:06
  • 2
    $\begingroup$ @Witold I have cross-posted the odd case of the problem on MO: Players alternate moving a $\{\swarrow,\uparrow,\rightarrow\}$ piece on a chessboard. $\endgroup$
    – Vepir
    Jun 15 '20 at 14:52
  • 1
    $\begingroup$ Yes. Problem №20 in tym.in.ua/2020/06/18/tym-2020-problems This is a math problem (not programming). $\endgroup$
    – Witold
    Jun 20 '20 at 13:42

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.