MathLabs

Bài 2

Cho n≥2n\ge2 là số nguyên. Xét bàn cờ n×nn\times n gồm n2n^2 ô vuông đơn vị. Một cách xếp nn quân xe trên bàn cờ này gọi là hòa bình nếu mỗi hàng và mỗi cột chứa đúng một quân xe. Tìm số nguyên dương kk lớn nhất sao cho, với mọi cách xếp hòa bình nn quân xe, luôn tồn tại một hình vuông k×kk\times k không chứa quân xe nào trong số k2k^2 ô vuông đơn vị của nó.
Bước 3 trên 5: Cận dưới: một cách xếp hòa bình tường minh cho n = ℓ²
n=ℓ2:rook at (r,c), r=pℓ+q  ⟹  c≡qℓ+p(modℓ2)n = \ell^2 : \text{rook at } (r,c),\ r=p\ell+q \implies c \equiv q\ell+p \pmod{\ell^2}
Phân tích chi tiết

Với n=ℓ2n=\ell^2, đánh số hàng và cột là 0,…,ℓ2−10,\ldots,\ell^2-1, và viết hàng r=pℓ+qr=p\ell+q với 0≤p,q<ℓ0\le p,q<\ell, đặt quân xe của hàng rr ở cột qℓ+pq\ell+p; cách này dùng mỗi cột đúng một lần. Kiểm tra được mọi hình vuông ℓ×ℓ\ell\times\ell đều gặp một trong các vị trí này: với ℓ\ell hàng liên tiếp bắt đầu từ hàng pℓ+qp\ell+q, các cột bị chiếm, khi sắp xếp, tăng theo bước không quá ℓ\ell và bắt đầu không quá ℓ−1\ell-1, nên mọi khối ℓ\ell cột liên tiếp đều bắt được một trong số đó.