Initially, on the lower left and right corner of a $2018\times 2018$ board, there're two horses, red and blue, respectively. $A$ and $B$ alternatively play their turn, $A$ start first. Each turn consist of moving their horse ($A$-red, and $B$-blue) by, simultaneously, $20$ cells respect to one coordinate, and $17$ cells respect to the other; while preserving the rule that the horse can't occupied the cell that ever occupied by any horses in the game. The player who can't make the move loss, who has the winning strategy?
Problem
Source: All-Russian MO 2018 Grade 11 P8
Tags: combinatorics, analytic geometry, grid
28.04.2018 15:25
@below But that doesn't matter, because $B$ can always go the square $A$ is currently on, reflected over the line of symmetry
28.04.2018 15:46
AforApple wrote:
17.05.2018 18:03
I think the problem statement is mistranslated. The original russian sentence, "Запрещено создавать позицию, которая уже встречалась в игре (позиции совпадают, если в них красный скакун стоит на одном и том же поле, и синий — тоже)"(http://olympiads.mccme.ru/vmo/2018/final/sheets2.pdf) means "It is forbidden to create a position that already occurred in game (the positions are the same if the red horse is standing on the same field in them, and the blue one is also)". So, occupying the cell that ever occupied by any horses is not prohibited. But it is prohibited to repeat the pair $(a,b)$ where $a,b$ is $A,B$'s cell respectively. This problem is closely related to Grade 10-8.
17.05.2018 19:37
Are A and B allowed to occupy the same square simultaneously?
18.05.2018 16:19
Yes, I think so unless they break the rule.
19.05.2018 16:59
No, the russian texts says no horse can occupy a square the other horse is on at the same time. Also, as said above, a position can't happen twice. Let us imagine the squares as vertices of a graph $G$ and two of them $u,v$ are connected iff a horse with one jump can move from $u$ to $v$. It's easy to see $G$ has only cycles with even length, i.e. $G$ is bipartite, $G=(V_1,V_2)$. Also, it's easy to see $G$ is connected. In the beginning $A$ is on a vertex of $V_1$ and $B$ - on a vertex of $V_2$. Now, we are in the hypothesis of another problem given at the same competition, but to the grade 9, see it here. Thus, the second player(that's $B$) always wins. I admit, I've read the official solution of the linked problem.
21.12.2018 10:24
I think the right translation would be, Initially, on the lower left and right corner of a $2018\times 2018$ board, there're two horses, red and blue, respectively. $A$ and $B$ alternatively play their turn, $A$ start first. Each turn consist of moving their horse ($A$-red, and $B$-blue) by, simultaneously, $20$ cells respect to one coordinate, and $17$ cells respect to the other; while preserving the rule that "two horses cannot be on the same cell and the position of two horses (red, blue) cannot occur twice". The player who can't make the move loss, who has the winning strategy? Official solution can be seen on http://olympiads.mccme.ru/vmo/2018/final/v18.pdf.
25.12.2022 17:11
i think it is not the original question
15.02.2024 09:30
Very difficult but nice problem, as my 499th post. The answer is $B$ wins. Consider a path from the lower right corner $X$ to the lower left corner $Y$. By colouring the board into black and white like chessboard we know the number of grids in the path is even, suggest the Path is $X=A_1\to B_1\to A_2\to B_2\to\cdots\to A_n\to B_n=Y.$ Here is the strategy of $B:$ If $B$ is on $A_i,1\le i\le n,$ for the next step $B$ walks to $B_n.$ If $B$ is on $B_i,1\le i\le n$ and the next turn $A$ is on $Y,$ then $B$ walks to $A_{n+1}.$ If $B$ is on $B_i,1\le i\le n$ and the next turn $A$ is not on $Y,$ then $B$ walks back to $A_{n}.$ Note that by the colouring above, $A$ and $B$ can never walk to a same grid, we just need by the strategy $B$ can always keep wlaking, until the game ends, and it wins. We only need to prove the position of two horses will not occur twice, this is easily proved as if $B$ went on the same position, $A$ must have the position earlier than $B.$ so we are done.$\Box$