Bài 2

Cho

n\ge2

là số nguyên. Xét bàn cờ

n\times n

gồm

n^2

ô vuông đơn vị. Một cách xếp

n

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

k

lớn nhất sao cho, với mọi cách xếp hòa bình

n

quân xe, luôn tồn tại một hình vuông

k\times k

không chứa quân xe nào trong số

k^2

ô vuông đơn vị của nó.

Bước 1 trên 5: Nêu đáp số và kế hoạch chứng minh

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

k = \left\lfloor \sqrt{n-1} \right\rfloor

Phân tích chi tiết

Đáp số là $k=\lfloor\sqrt{n-1}\rfloor$ . Điều này được chứng minh bằng cách chỉ ra, với mỗi số nguyên dương $\ell$ : (i) nếu $n>\ell^2$ thì mọi cách xếp hòa bình đều có một hình vuông $\ell\times\ell$ trống, và (ii) nếu $n\le\ell^2$ thì có một cách xếp hòa bình không có hình vuông nào như vậy; hai điều này cùng xác định $\ell$ lớn nhất thỏa mãn là $\lfloor\sqrt{n-1}\rfloor$ .