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 4 of 5: One component per color outside S

Previous step Next step

x+y\equiv1\!\!\pmod2\implies(x,y)\text{ joined to }(1,1)\text{ outside }S

Detailed analysis

Repeating the slides of the previous step lets any cell outside $S$ be joined by a chain of two-move paths to any other cell outside $S$ with the same parity of $x+y$ , since each two-move path changes $x+y$ by an even amount, $\pm2$ or $\pm2k$ . Hence all cells outside $S$ sharing $(1,1)$ 's color, $x+y$ even, lie in one connected component containing $(1,1)$ .