An $n \times n$ board is given. In the top left corner cell there is a fox, whereas in the bottom left corner cell there is a rabbit. Every minute, the fox and the rabbit jump to a neighbouring cell at the same time. The fox can jump only to neighbouring cells that are below it or on its right, whereas the rabbit can only jump to the cells above it or in its right. They continue like this until they have no possible moves. The fox catches the rabbit if at a certain moment they are in the same cell, otherwise the rabbit gets away. Find all natural numbers $n$ for which the fox has a winning strategy to catch the rabbit. (Note: Two squares are considered neighbours if they have a common side.)
Problem
Source: Kosovo National Olympiad 2025, Grade 11, Problem 1
Tags: combinatorics
18.11.2024 13:51
For all $n$, the fox has a winning strategy. Let $a_{ij}$denote the position of the fox at the $i$-th row and $j$-th column of the $n \times n$ cell, and let $b_{ij}$ denote the position of the rabbit at the $n \times n$ cell. The fox can go right and down, and the rabbit can go up and right. Here, $i$ denotes the $i$-th row and $j$ denotes the $j$-th column. If at some instance $i_{\text{rabbit}} < i_{\text{fox}}$ happens, then the fox loses to catch the rabbit. So the strategy of the fox will be to maintain \[ j_{\text{fox}} = j_{\text{rabbit}} - 1 \]after the rabbit's move. And when the rabbit makes 1 move up, then the fox must make one move down. If the fox starts the game, the first move for the fox will be to go one step down. If the rabbit starts the game, it would be trivial to win for the fox according to the given strategy.
18.11.2024 17:11
Rohit-2006 wrote: For all $n$, the fox has a winning strategy. Let $a_{ij}$denote the position of the fox at the $i$-th row and $j$-th column of the $n \times n$ cell, and let $b_{ij}$ denote the position of the rabbit at the $n \times n$ cell. The fox can go right and down, and the rabbit can go up and right. Here, $i$ denotes the $i$-th row and $j$ denotes the $j$-th column. If at some instance $i_{\text{rabbit}} < i_{\text{fox}}$ happens, then the fox loses to catch the rabbit. So the strategy of the fox will be to maintain \[ j_{\text{fox}} = j_{\text{rabbit}} - 1 \]after the rabbit's move. And when the rabbit makes 1 move up, then the fox must make one move down. If the fox starts the game, the first move for the fox will be to go one step down. If the rabbit starts the game, it would be trivial to win for the fox according to the given strategy. Try again brother
18.11.2024 18:16
I think the answer is for all odd numer n, the fox has a winning strategy. First of all, it is trivial that the rabit can get away if n is even. Indeed, the rabit just need to jump up for the first (n/2 + 1) jump, at the same time if the fox ever made a jump to the right it wouldn't ever catch the rabit because the column it in is greater than the column the rabit in (always in the first column for the first (n/2 + 1) jump), if the fox just jump down the first column for the first (n/2 + 1) jump, it also wouldn't ever catch the rabit because n is even (eventually the fox will jump past the rabit on the (n/2 + 1)-th jump) . For any odd number n, set n=2m+1 , we will show that the fox has the strategy to catch the rabit. Firstly, let the fox jump down the first column for the first (m+1) jump and jump to the right from that time on. Suppose that the rabit lie on the k-th row afer the first (m+1) jump, it's easy to show that the rabit has jumped (m+1- k) times to the right. We will show that the rabit has to reach the (m+1)-th row in the next (2m+1) jumps. Because the rabit has jumped to the right (m+1-k) times it can only jump to the right (n-(m+1-k)) = (m+k) times more so in the next (2m+1) jumps the rabit has to jump up (m+1-k) times eventually reach the (m+1)-th row at some instance. Now we show that the cell the rabit reach at the (m+1)-th row is the cell that has the fox in it. Let h is the times the rabit jumps to the right before it reach the (m+1)-th row, this show that the rabit has jumped to the right m+1+ h times before it reaches the (m+1)-th row (after the first (m+1) jumps) so in the end the rabit lies at the (m+1+h)-th column while at that time, the fox also jump to the right m+1+h times after the first (m+1) jumps so eventually the fox will catch the rabit on the cell at the (m+1+h)-column and (m+1)-th row. P/s: It's my first time posting a solution on Aops and moreover I don't know much about the coding so I'm afraid that my solution is hard to understand (It may be doubly true beacuse of my bad english) so feel free to correct if it has any mistakes.
19.11.2024 20:33
For n even its clear why the bunny runs away. While for n odd the fox just goes to (n+1)/2th row (so just upp for (n-1)/2 moves) after this the fox just moves horizontaly for each move, we know they will meet cus at some point the bunny has to cross that row so at some point it will have (n-1)/2 upp or down moves similarly the number of moves of them overall has to equal so they also have the same ammount of horizontal moves so they are destined to meet on the (n+1)/2th row at some point. So for all n odd there exists a strategy.
19.11.2024 22:25
For even $n$, color the grid black and white in a checkerboard pattern. Then the fox and rabbit will always be on different colored squares so the fox cannot catch the rabbit. For odd $n$, the fox first moves down. For every subsequent move $i$, the fox must copy the rabbit's move $i-1$, where instead of moving up the fox moves down. After some time the fox position at time $t$ will be $1$ above the rabbit's position at time $t-1$. Hence the rabbit's move $t$ must be to the right. Eventually the rabbit hits the right edge, and the fox is $1$ above and $1$ to the left of the rabbit. The rabbit is forced to go up, and the fox goes right and catches the rabbit. $\square$
20.11.2024 16:57
We claim that the answer is all odd positive integers $n$. For even $n$, the rabbit's strategy is to move continuously up along the leftmost column. This works since if the fox ever strays from the leftmost column he cannot return, so in order to capture the rabbit he has to stay in the leftmost column, moving down. If the rabbit and fox find themselves in the same square (say square $i$ from the top) then, \[i=n+1-i \implies n+1=2i\]which is a clear contradiction since $n$ is even. Thus, this strategy works, and the rabbit can escape the fox for all even $n$. For odd $n=2k+1$, the fox's strategy is to move down in the first $k$ moves and right for the next $2k$ moves. We claim that this way, the fox always manages to trap the rabbit. Let the $i$-diagonal for all $i\ge 0$ denote the $i^{th}$ up-left/down-right diagonal moving rightwards, from the bottom-left square. Note that after the $i^{th}$ move, the rabbit lies on the $i^{th}$ diagonal. Now, if the rabbit can escape the fox, (since the rabbit can do a total of $2n-2$ moves) he must eventually reach a cell in the $k+1^{st}$ row from the top. Say the cell he first reaches in this row is $(k+1,r)$. This cell belongs to the $(k+r-2)^{th}$ diagonal so the rabbit reaches it in his $(k+r-2)^{th}$ move. Further note that due to the nature of the fox's move, the fox will be on this cell on his $(k+r-2)^{th}$ move as well. Thus, the rabbit is caught in this move, so the rabbit cannot escape the fox.
21.11.2024 02:11
Here is my solution I found during the contest Claim: If $n$-even then the fox cannot catch the rabbit Proof: If the rabbit from the initial position continues to walk up, then if the fox continues to walk down too, then they will not meet since $n $is even, after the rabbit reaches the upper left corner cell, then it continues to the right to the upper right corner cell, so it does not meet the fox. (This ends because the rabbit can’t move anymore.) So if the fox does not just continue down but at a certain moment turns to the right, then the rabbit uses the same strategy without fearing that the rabbit will catch it. $\square$ Claim: If the $n$-odd then the fox has a winning strategy Proof: We will show the winning strategy. Let's denote the squares in the middle column by $X_1$, $X_2$, $\dots$ $X_n$. First the fox in the first $\frac{n-1}{2}$ moves goes down reaching square $X_1$. If the rabbit in the first $\frac{n-1}{2}$ moves goes up then they both meet in square $X_1$. So the fox catches the rabbit. On the contrary, if the rabbit does not only go up, then we know that the rabbit must pass one of the squares in the middle column. After reaching the square $X_i$, $\forall i=\{2,3,... n\}$ (we have checked the case for $X_1$) then the rabbit needs$\frac{n-1}{2}+i-1$ moves to reach the square $X_i$. Also, the fox needs$\frac{n-1}{2}+i-1$ moves too to reach square $X_i$. So the fox catches the rabbit for all odd numbers. $\blacksquare$ My 90th post