Consider a $100 \times 100$ table, and identify the cell in row $a$ and column $b$, $1 \leq a, b \leq 100$, with the ordered pair $(a, b)$. Let $k$ be an integer such that $51 \leq k \leq 99$. A $k$-knight is a piece that moves one cell vertically or horizontally and $k$ cells to the other direction; that is, it moves from $(a, b)$ to $(c, d)$ such that $(|a-c|, |b - d|)$ is either $(1, k)$ or $(k, 1)$. The $k$-knight starts at cell $(1, 1)$, and performs several moves. A sequence of moves is a sequence of cells $(x_0, y_0)= (1, 1)$, $(x_1, y_1), (x_2, y_2)$, $\ldots, (x_n, y_n)$ such that, for all $i = 1, 2, \ldots, n$, $1 \leq x_i , y_i \leq 100$ and the $k$-knight can move from $(x_{i-1}, y_{i-1})$ to $(x_i, y_i)$. In this case, each cell $(x_i, y_i)$ is said to be reachable. For each $k$, find $L(k)$, the number of reachable cells.
Problem
Source: APMO 2024 P2
Tags: combinatorics, APMO 2024
30.07.2024 07:11
The write-up for this problem is quite annoying.
30.07.2024 13:00
Actually problem is easy, and it is not hard to find answer(similar pr can be found on IMO SL 2000). Mine answer is same as previous one's, and yes, $2k-100 \times 2k-100$ is not reachable. And If k is odd, reachable coordinates $(a,b)$ must have a and b have same parity, and that other cells with same parity coordinates are reachable can be proven easily by induction by denoting $n=100$, same thing works for $k$ even (this time other all cells are reachable).
31.07.2024 00:40
The answer is $$\boxed{L(k)=\begin{cases} 4k(100-k),& k\equiv 0\pmod{2}\\ 2k(100-k),& k\equiv 1\pmod{2} \end{cases}}$$ Claim: $(i, j)$ with $i, j\in[101-k, k]$ is not reachable. Proof. For the sake of contradiction, say it was reachable. In that case, there would be a path from $(i, j)$ to $(1,1)$ too. However, there are no moves for the $k$-knight from that position without going out of bounds, a contradiction. $\blacksquare$ Delete the square formed by the set of cells $(i, j)$ with $i, j\in[101-k, k]$: This region is subsequently considered out of bounds. Note that the number of deleted cells is $(2k-100)^2$. Lemma: $(i, j)$ is reachable iff $(i-2, j)$, $(i+2, j)$, $(i, j-2)$ or $(i, j+2)$ is reachable, given that $(i, j)$ is within the bounds. Proof. If $(i, j)$ is reachable, at least one of $(i-2, j)$, $(i+2, j)$, $(i, j-2)$ and $(i, j+2)$ must be within the bounds as well; so suppose the cell $(i-2, j)$ is within the bounds. Either $(i-1, j-k)$ or $(i-1, j+k)$ is always within the bounds, so the $k$-knight goes along the path $(i, j)\to(i-1, j\pm k)\to(i-2, j)$. This shows it is reachable, and we can use similar arguments for the other cells. The converse is implicit. $\blacksquare$ Let the parity of $i+j$ be the parity of the cell $(i, j)$. Case 1: $k\equiv 0\pmod{2}$. It is possible to reach any $(i, j)$ within the bounds from $(1,1)$ such that $i\equiv j\equiv 1\pmod{2}$. After covering all such cells, move the $k$-knight from $(1,1)$ to $(k+1, 2)$. Since $k+1\equiv 1\pmod{2}$ and $2\equiv 0\pmod{2}$, it is possible to reach any $(i, j)$ within the bounds such that $i\equiv 1\pmod{2}$ and $j\equiv 0\pmod{2}$. After covering all such cells, move the $k$-knight from $(1,1)$ to $(2, k+1)$. Since $2\equiv 0\pmod{2}$ and $k+1\equiv 1\pmod{2}$, it is possible to reach any $(i, j)$ within the bounds such that $i\equiv 0\pmod{2}$ and $j\equiv 1\pmod{2}$. Since all odd cells within the bounds are reachable, the $k$-knight can go from $(1,1)$ to $(k+2, 1)$ and then to $(2,2)$. Since $2\equiv 0\pmod{2}$, it is possible to reach any $(i, j)$ within the bounds such that $i\equiv j\equiv 0\pmod{2}$. Therefore, we covered every cell within the bounds, and the number of such cells is $$100^2-(2k-100)^2=4k(100-k),$$as claimed. $\blacksquare$ Case 2: $k\equiv 1\pmod{2}$. Claim: Odd cells are not reachable. Proof. The parity of reachable cells is invariant. If at any point the $k$-knight is at $(i, j)$, then on the next move it would go to a cell of the same parity, because $i+j\pm k\pm 1\equiv i+j\pmod{2}$. Since we start at $(1,1)$, an even cell, it follows that a reachable cell must be even. $\blacksquare$ It is possible to reach any $(i, j)$ within the bounds from $(1,1)$ such that $i\equiv j\equiv 1\pmod{2}$. After covering all such cells, move the $k$-knight from $(1,1)$ to $(k+1, 2)$. Since $k+1\equiv 2\equiv 0\pmod{2}$, it is possible to reach any $(i, j)$ within the bounds such that $i\equiv j\equiv 0\pmod{2}$. Therefore, we covered all the even cells within the bounds, and the number of such cells is $$\frac{100^2-(2k-100)^2}{2}=2k(100-k),$$as claimed, and we are done. $\blacksquare$
31.07.2024 11:42
Let's make some observations: 1.If $(a,b)\to (c,d)$ then $(c,d)\to (a,b)$ 2.If $101-k\le a,b \le k $ then $(a,b)$ is not reachable because WLOG we add/subtract $k$ from $b$ we see that $b-k\le 0$ and $b+k \ge 101$ so is not in the square. 3. If $k$ is odd we can see by induction that $a\equiv b \pmod 2$ This is enough for the bound now it remains to give the construction and final answer: Case 1: k is even We claim that $(a,b)$ is reachable as long as it doesn't satisfy 2.We will do this by strong induction on $a+b$ with a trivial base case: If $max(a,b)\ge k+1$ it is easy: WLOG $a\ge k+1$ and we have that $(1,1)\to (a-k,b+1)\to (a,b)$ and we are done. Otherwise $a,b\le k$ and WLOG $b\le 100-k$.If $a\ge 3$ we have $(1,1)\to (a-2,b)\to (a-1,b+k)\to (a,b)$ and we are done. Otherwise $a\in \{1,2\}$ and if $b\ge 3$ we have $a\le 100-k$ and do similar as above. It remains to check $(1,2)$ and $(2,2)$ $(1,1)\to (2,k+1)\to (k+2,k+2)\to (k+1,2)$ and now subtact $1$ form the $x$ coordinate and alternate $+k$ and $-k$ on the other coordinate.Since $k$ is even you will get $(1,2)$. $(1,1)\to (2,k+1)\to^{(*)} (2+k,2)\to^{(**)} (2,2)$ for (*) add and subtract $k, k-1$ times and since odd it will be $2+k$ and on the other coordinate subtract $1$ and you will get $2$ and for (**) subtract $1 k$ times and on the other alternate $+k$ and $-k$ Case 2: $k$ is odd Do the exact same induction step as in case 1 and you only have to check $(2,2)$ which is easy Now the final answwer is $\boxed{100^2-(2k-100)^2}$ for k even and $\boxed{2\cdot 50^2-2\cdot (k-50)^2}$ for k odd
31.07.2024 20:26
This problem must be a joke. I think it's unsuitable for a math olympiad, more like an exercise to train students to write a proof rigorously. The answer is not hard to guess, but the write-up is a total pain. I thought the write-up of ISL 2007 C1 was already bad, but this one is a disaster!