Bài 2
Cho là số nguyên. Xét bàn cờ gồm ô vuông đơn vị. Một cách xếp 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 lớn nhất sao cho, với mọi cách xếp hòa bình quân xe, luôn tồn tại một hình vuông không chứa quân xe nào trong số ô vuông đơn vị của nó.
Bước 4 trên 5: Cận dưới: mở rộng cho n < ℓ²
Phân tích chi tiết
Với , bắt đầu từ cấu hình ở trên cho và xóa hàng dưới cùng với cột phải nhất. Việc xóa này không làm xuất hiện hình vuông 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 quân xe mà không có hình vuông trống nào.