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 2 trên 5: Cận trên: nguyên lý Dirichlet trên khối ℓ² × ℓ

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

n > \ell^2 \implies \text{some } \ell\times\ell \text{ square is empty}

Phân tích chi tiết

Giả sử $n>\ell^2$ . Lấy một hàng $R$ mà quân xe của nó nằm ở cột trái nhất trong số mọi hàng, và gọi $U$ là hợp của $\ell$ hàng liên tiếp bao gồm $R$ ; $U$ chứa đúng $\ell$ quân xe. Bỏ đi $n-\ell^2\ge1$ cột trái nhất khỏi $U$ (loại bỏ ít nhất quân xe của $R$ ) để lại một hình chữ nhật $\ell^2\times\ell$ với nhiều nhất $\ell-1$ quân xe, có thể chia thành $\ell$ hình vuông cỡ $\ell\times\ell$ ; theo nguyên lý Dirichlet, một trong các hình vuông này trống.