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 2 of 5: The central square with no moves

Previous step Next step

S=\{(x,y):101-k\le x,y\le k\},\qquad|S|=(2k-100)^2

Detailed analysis

Negating the condition of the previous step, a cell $(x,y)$ has no legal move at all exactly when $101-k\le x\le k$ and $101-k\le y\le k$ ; this is a square $S$ of side $k-(101-k)+1=2k-100$ , so $|S|=(2k-100)^2$ . Cells in $S$ are isolated, while the remaining $100^2-(2k-100)^2$ cells each have at least one move. Since $101-k\ge2$ for $k\le99$ , the starting cell $(1,1)$ is never in $S$ .