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 1 of 5: When does a cell have a legal move

Previous step Next step

(x,y)\text{ has a legal move}\iff x\le100-k\lor x\ge k+1\lor y\le100-k\lor y\ge k+1

Detailed analysis

A $k$ -knight move changes one coordinate by $\pm1$ and the other by $\pm k$ , and the sign of the $\pm1$ part can always be chosen so that a coordinate already in $[1,100]$ stays in range. Hence $(x,y)$ has at least one on-board move exactly when the $k$ -part can be applied to $x$ or to $y$ , that is, when $x\le100-k$ or $x\ge k+1$ or $y\le100-k$ or $y\ge k+1$ . Since every move is reversible, the same condition governs whether $(x,y)$ has any on-board move at all, incoming or outgoing.