Edit $4.$ $-$ Proposing to reopen the question (the related competition should be over by now).
Edit $3.$ $-$ I have just found out that the linked competition (see the "Edit $1$.") is still ongoing. Please close and hide this question and its counterpart (see the "Remark."), until the competition is over.
Edit $2$. $-$ I've added strategies for solving some simple squares (tiles).
Edit $1$. $-$ This problem is equivalent to the problem $20.\space b)$ from Завдання ХХIIІ ТЮМ (2020 р.) which talks about the divisors of $10^{2k}$ where legal moves are $\{\div 10, \times 2,\times 5\}$ to move from the previous divisor to the next one, and you can't revisit a divisor. But, it appears they did not publish the solutions. $-$ Thank you Witold for the reference.
Remark. This problem is equivalent to the even case of the exponent $n=2k$ of the following problem: Winning strategy in a game with the positive divisors of $10^n$ from MSE. (This is a partial cross-post.)
The $\{\swarrow,\uparrow,\rightarrow\}$ piece game
Consider an odd sized chessboard $(2k+1)\times(2k+1)$ with WLOG bottom left corner square at $(0,0)$ and top right corner square at $(2k,2k)$. A piece whose allowed moves are $\{(-1,-1),(0,+1),(+1,0)\}$ is placed on one of the squares.
Two players then alternate moving the piece, such that the piece never stands on the same square twice. (The piece can't revisit the squares.) The player that can't move the piece, loses. (The player that last moved, wins.)
On which starting squares will the first player have a winning strategy?
I have brute-forced the game for boards of sizes $(2k+1)=3,5,7,9,11$ with C++ (run it on repl.it). If the second player has a winning strategy, the square is colored blue. Otherwise, the first player has a winning strategy and the square is colored green.
It seems that if the piece starts on a square $(x,y)$ where $x,y$ are both even, then the second player can always force a win. Can we prove this?
Otherwise, if $x,y$ are not both even, then it seems the first/green player can force a win, unless the square is one of the "exceptions". (Additional blue squares.)
WLOG due to symmetry we list only the exceptions below the main diagonal:
- If $n\le2$ there are no exceptions.
- If $n=3$, the exceptions below the diagonal are $(4,3),(6,3)$.
- If $n=4$, the exceptions below the diagonal are $(8,3),(5,4),(8,5)$.
- If $n=5$, the exceptions below the diagonal are $(6,1),(7,4),(6,5),(10,5),(7,6)$.
But what will be the exceptions for $n\ge 6$? I do not see a pattern.
I do not know how to solve all squares in general, but I can solve specific examples.
Let $n=2k$ and consider some $(n+1)\times(n+1)$ chessboard.
$i)$ Solving the corners
It is easy to show that if the piece starts on any of the four corners $(0,0),(n,0),(0,n),(n,n)$ then the second player has a winning strategy.
Starting on $(0,0)$, the second player can keep returning to the main diagonal until the first player can no longer move. ("The main diagonal climber".)
Starting on $(n,n)$, the first player is forced to move diagonally. Then, the second player can keep forcing the diagonal move by repeating either the $(+1,0)$ or the $(0,+1)$ move until the first player can no longer move. ("The wall crawler".)
Starting on $(0,n)$ we have a forced $(+1,0)$ move for the first player. This can be forced again and again, by responding with the $(-1,-1)$ move, until we reach $(0,0)$. Now the moves to $(1,0),(2,0)$ are forced. Finally, the second player can keep returning to the corresponding diagonal until the piece reaches $(n,n)$ where we apply "The wall crawler".
Strategy for starting on $(n,0)$ is symmetric to the previous corner $(0,n)$.
$ii)$ Extending the solutions around the $(0,0)$ corner
It can be shown that $(0,0),(2,0),(0,2),(2,2)$ are always a win for the second player, and that $(1,0),(0,1),(1,1),(2,1),(1,2)$ are always a win for the first player.
When starting on $(0,2)$ or $(2,0)$, the second player can stay on the diagonal to force the piece to reach $(n,n)$ where they apply "The wall crawler" to beat the first player. Consequently, if we start on $(0,1)$ or $(1,0)$ then the first player can move to $(0,2)$ or $(2,0)$ respectively, and apply the same strategy to beat the second player.
When starting on $(2,2)$, the first player must use the diagonal move. (Otherwise, the second player can apply "The main diagonal climber".) But, then the second player moves to $(0,0)$ and forces the first player to move to either $(1,0)$ or $(0,1)$. This is losing for the first player because then the second player moves to $(2,0)$ or $(0,2)$ respectively, and applies the previous winning strategy.
Consequently (to the previous strategy), we have that $(1,1)$ is a win for the first player.
Consequently (to the previous bullet points), we have that the $(1,2)$ and $(2,1)$ are wins for the first player if they decide to move to the $(2,2)$ square.
It looks like extending these strategies to $(4,4)$ is not as simple as the previous extension to $(2,2)$, because the $(3,4),(4,3)$ squares depend on $(n+1)$ (the chessboard dimension) itself. These two squares appear to be a win for the first player, unless the dimension is $(2k+1)=7$ where they are a win for the second player. (According to my brute force solutions.)
That is, the general strategy needs to account for the observed "exceptions".
Remark. Although the question is about the odd sizes of the chessboard, the strategies mentioned above work for both the odd and the even dimensions of the chessboard. If we want to extend these strategies further (to more squares), we do need to also account for the parity of the dimension. (According to my brute force solutions.)
