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 4 trên 5: Cận dưới: mở rộng cho n < ℓ²
n<ℓ2:trim rows/columns, then re-pair empty onesn < \ell^2 : \text{trim rows/columns, then re-pair empty ones}
Phân tích chi tiết

Với n<ℓ2n<\ell^2, bắt đầu từ cấu hình ở trên cho ℓ2\ell^2 và xóa ℓ2−n\ell^2-n hàng dưới cùng với ℓ2−n\ell^2-n cột phải nhất. Việc xóa này không làm xuất hiện hình vuông ℓ×ℓ\ell\times\ell trống nào, nhưng một số hàng và cột còn lại có thể trở nên không có quân xe; vì số hàng trống và số cột trống bằng nhau, ghép chúng tùy ý và đặt một quân xe tại mỗi giao điểm (hàng trống, cột trống) được ghép để khôi phục một cách xếp hòa bình với nn quân xe mà không có hình vuông ℓ×ℓ\ell\times\ell trống nào.