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 3 of 5: Two moves slide a cell by 2

Previous step Next step

(x,y)\to(x\pm k,y-1)\to(x,y-2)

Detailed analysis

For cells $(x,y)$ and $(x,y-2)$ both outside $S$ , one of the two-move paths $(x,y)\to(x+k,y-1)\to(x,y-2)$ or $(x,y)\to(x-k,y-1)\to(x,y-2)$ stays on the board, since $x\le100-k$ or $x\ge k+1$ lets us pick the sign of the $k$ -jump; symmetrically, $(x,y)$ and $(x-2,y)$ are joined by a two-move path that swaps the roles of the coordinates.