Problem 2

Consider a

100\times100

table, and identify the cell in row

a

and column

b

1\le a,b\le100

, with the ordered pair

(a,b)

. Let

k

be an integer such that

51\le k\le99

. A

k

-knight is a piece that moves one cell vertically or horizontally and

k

cells in the other direction; that is, it moves from

(a,b)

(c,d)

such that

(|a-c|,|b-d|)

is either

(1,k)

(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),\ldots,(x_n,y_n)

such that, for all

i=1,2,\ldots,n

1\le x_i,y_i\le100

and the

k

-knight can move from

(x_{i-1},y_{i-1})

(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.

Step 5 of 5: Parity invariant decides the answer

Previous step Next step

L(k)=100^2-(2k-100)^2\ (k\text{ even}),\qquad L(k)=\tfrac12\big(100^2-(2k-100)^2\big)\ (k\text{ odd})

Detailed analysis

A single $k$ -knight move changes $x+y$ by $\pm(k-1)$ or $\pm(k+1)$ , both of the same parity as $k+1$ . If $k$ is odd, $k+1$ is even, so $x+y\bmod2$ is invariant and only the $\big(100^2-(2k-100)^2\big)/2$ cells outside $S$ sharing $(1,1)$ 's color are reachable. If $k$ is even, $k+1$ is odd, so a single move already reaches a cell of the opposite color, and the previous step applied to that color shows every remaining cell outside $S$ is reachable too; hence all $100^2-(2k-100)^2$ cells outside $S$ are reachable.