Bài 2

Xét một bảng

100\times100

, và đồng nhất ô ở hàng

a

cột

b

1\le a,b\le100

, với cặp có thứ tự

(a,b)

. Gọi

k

là số nguyên với

51\le k\le99

. Một

k

-mã là quân cờ di chuyển một ô theo chiều dọc hoặc ngang và

k

ô theo chiều còn lại; nghĩa là nó đi từ

(a,b)

đến

(c,d)

sao cho

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

bằng

(1,k)

hoặc

(k,1)

. Quân

k

-mã xuất phát tại ô

(1,1)

và thực hiện một số nước đi. Một dãy nước đi là một dãy các ô

(x_0,y_0)=(1,1),(x_1,y_1),\ldots,(x_n,y_n)

sao cho với mọi

i=1,2,\ldots,n

, ta có

1\le x_i,y_i\le100

và quân

k

-mã có thể đi từ

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

đến

(x_i,y_i)

. Khi đó mỗi ô

(x_i,y_i)

được gọi là đến được. Với mỗi

k

, tìm

L(k)

, số ô đến được.

Bước 1 trên 5: Khi nào một ô có nước đi hợp lệ

Bước trước Bước tiếp

(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

Phân tích chi tiết

Một nước đi $k$ -mã thay đổi một tọa độ đi $\pm1$ và tọa độ kia đi $\pm k$ , và có thể luôn chọn dấu của phần $\pm1$ sao cho tọa độ vốn đã thuộc $[1,100]$ vẫn nằm trong phạm vi. Do đó $(x,y)$ có ít nhất một nước đi trong bảng đúng khi phần $k$ có thể áp dụng cho $x$ hoặc cho $y$ , tức là khi $x\le100-k$ hoặc $x\ge k+1$ hoặc $y\le100-k$ hoặc $y\ge k+1$ . Vì mọi nước đi đều có thể đảo ngược, cùng điều kiện này quyết định liệu $(x,y)$ có bất kỳ nước đi nào trong bảng hay không, dù là đi vào hay đi ra.