Cho một bàn cờ là một lưới ô vuông kích thước $7\times 8$, trên mỗi ô vuông đều đang có một quân cờ. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh hoặc chung một đỉnh. Hỏi phải nhắc ra khỏi bàn cờ ít nhất bao nhiêu quân cờ, để trong các quân còn lại, không có 5 quân nào nằm trên 5 ô vuông kề nhau thẳng hàng theo hàng dọc, hàng ngang và hàng chéo?

Lời giải:



Ta sẽ chứng minh số quân cờ tối thiểu cần nhắc ra là 11 quân. Thật vậy, đầu tiên ta sẽ chứng minh nếu chỉ nhắc ra 10 quân, thì không thể làm cho bàn cờ hết 5 quân liền nhau thẳng hàng. Ta ký hiệu ô $(i;j)$ là ô ở hàng $i$, cột $j$, với $1\le i\le 7;1\le j\le 8$ như hình vẽ; và ta cần nhắc ra 10 quân sao cho không còn 5 quân nào liền nhau thẳng hàng.

Ở 5 ô đầu tiên từ trái sang của mỗi hàng, ta phải nhắc ra ít nhất mỗi hàng 1 quân. Ở 3 cột 6, 7, 8: ở 5 ô từ trên xuống của mỗi cột, ta phải nhắc ra ít nhất 1 quân. Như vậy ta đã nhắc hết 10 quân, và ô chữ nhật $2\times 3$ ở góc dưới bên phải không được nhắc ra quân nào. Do tính đối xứng, nên 4 hình chữ nhật được tô đậm ở 4 góc trong hình, ta không được nhắc quân nào. | 1

Sau khi chắc chắn không nhắc các quân ở 4 góc như ý trên, ta làm lại: ở các hàng 1, 2, 6, 7: 2 ô giữa của mỗi hàng ta phải nhắc ra ít nhất 1 quân. Ở các cột 1, 2, 3, 6, 7, 8: 3 ô giữa của mỗi cột ta phải nhắc ra ít nhất 1 quân, tất cả đã là 10 quân; nên ô chữ nhật kích cỡ $3\times 2$ ở giữa, ta không nhắc quân nào. Như vậy 5 khu vực tô đậm trên hình, ta không được nhắc quân nào. | 1

Tiếp tục làm lại: bây giờ, ta phải nhắc ít nhất 1 quân từ 2 ô giữa của mỗi hàng 1, 2, 6, 7 và ít nhất 1 quân từ 3 ô giữa của mỗi cột 1, 2, 7, 8. Như vậy ta đã nhắc ít nhất 8 quân, nên ở 2 cột 3 và 6, ta chỉ còn được nhắc nhiều nhất 2 quân. Tuy nhiên các ô $(3;3)$, $(3;6)$, $(5;3)$ và $(5;6)$ (được ký hiệu lục giác trên hình) cần phải nhắc hết để không có đường chéo: ví dụ ô $(3;3)$ nếu để lại thì có một đường chéo từ $(1;1)$ tới $(5;5)$, vì thế chỉ nhắc tối đa 2 quân ở cột 3 và cột 6 là không đủ. Tóm lại chỉ nhắc 10 quân thì vẫn còn 5 quân liền nhau thẳng hàng.

Với 11 quân được nhắc ra ở ô được tô đậm trong hình dưới, thì sau khi nhắc, trên bàn cờ không còn 5 quân nào liên nhau thẳng hàng ngang, dọc hoặc chéo:



Như vậy đáp số là 11 quân. | 2đ