Maths Olympiad Prep

Library / /24 of 48

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Consider a 100×100100 \times 100 table, and identify the cell in row aa and column bb, 1a,b1001 \leq a, b \leq 100, with the ordered pair (a,b)(a, b). Let kk be an integer such that 51k9951 \leq k \leq 99. A kk-knight is a piece that moves one cell vertically or horizontally and kk cells to the other direction; that is, it moves from (a,b)(a, b) to (c,d)(c, d) such that (ac,bd)(|a-c|,|b-d|) is either (1,k)(1, k) or (k,1)(k, 1). The kk-knight starts at cell (1,1)(1,1), and performs several moves. A sequence of moves is a sequence of cells (x0,y0)=(1,1)(x_{0}, y_{0})=(1,1), (x1,y1)(x_{1}, y_{1}), (x2,y2),,(xn,yn)(x_{2}, y_{2}), \ldots, (x_{n}, y_{n}) such that, for all i=1,2,,ni=1,2, \ldots, n, 1xi,yi1001 \leq x_{i}, y_{i} \leq 100 and the kk-knight can move from (xi1,yi1)(x_{i-1}, y_{i-1}) to (xi,yi)(x_{i}, y_{i}). In this case, each cell (xi,yi)(x_{i}, y_{i}) is said to be reachable. For each kk, find L(k)L(k), the number of reachable cells.
Answer: L(k)={1002(2k100)2 if k is even 1002(2k100)22 if k is odd L(k)=\left\{\begin{array}{ll}100^{2}-(2 k-100)^{2} & \text{ if } k \text{ is even } \\ \frac{100^{2}-(2 k-100)^{2}}{2} & \text{ if } k \text{ is odd }\end{array}\right..

Solution

Cell (x,y)(x, y) is directly reachable from another cell if and only if xk1x-k \geq 1 or x+k100x+k \leq 100 or yk1y-k \geq 1 or y+k100y+k \leq 100, that is, xk+1x \geq k+1 or x100kx \leq 100-k or yk+1y \geq k+1 or y100ky \leq 100-k (*). Therefore the cells (x,y)(x, y) for which 101kxk101-k \leq x \leq k and 101kyk101-k \leq y \leq k are unreachable. Let SS be this set of unreachable cells in this square, namely the square of cells (x,y)(x, y), 101kx,yk101-k \leq x, y \leq k.
If condition (*) is valid for both (x,y)(x, y) and (x±2,y±2)(x \pm 2, y \pm 2) then one can move from (x,y)(x, y) to (x±2,y±2)(x \pm 2, y \pm 2), if they are both in the table, with two moves: either x50x \leq 50 or x51x \geq 51; the same is true for yy. In the first case, move (x,y)(x+k,y±1)(x,y±2)(x, y) \rightarrow (x+k, y \pm 1) \rightarrow (x, y \pm 2) or (x,y)(x±1,y+k)(x±2,y)(x, y) \rightarrow (x \pm 1, y+k) \rightarrow (x \pm 2, y). In the second case, move (x,y)(xk,y±1)(x,y±2)(x, y) \rightarrow (x-k, y \pm 1) \rightarrow (x, y \pm 2) or (x,y)(x±1,yk)(x±2,y)(x, y) \rightarrow (x \pm 1, y-k) \rightarrow (x \pm 2, y).
Hence if the table is colored in two colors like a chessboard, if k50k \leq 50, cells with the same color as (1,1)(1,1) are reachable. Moreover, if kk is even, every other move changes the color of the occupied cell, and all cells are potentially reachable; otherwise, only cells with the same color as (1,1)(1,1) can be visited. Therefore, if kk is even then the reachable cells consists of all cells except the center square defined by 101kxk101-k \leq x \leq k and 101kyk101-k \leq y \leq k, that is, L(k)=1002(2k100)2L(k)=100^{2}-(2 k-100)^{2}; if kk is odd, then only half of the cells are reachable: the ones with the same color as (1,1)(1,1), and L(k)=12(1002(2k100)2)L(k)=\frac{1}{2}\left(100^{2}-(2 k-100)^{2}\right).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.