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 3 trên 5: Cận dưới: một cách xếp hòa bình tường minh cho n = ℓ²
Phân tích chi tiết
Với , đánh số hàng và cột là , và viết hàng với , đặt quân xe của hàng ở cột ; 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 đều gặp một trong các vị trí này: với hàng liên tiếp bắt đầu từ hàng , các cột bị chiếm, khi sắp xếp, tăng theo bước không quá và bắt đầu không quá , nên mọi khối cột liên tiếp đều bắt được một trong số đó.