Bé An có một bộ cờ gồm 32 quân cờ. An chơi trò chơi đặt lần lượt các quân cờ lên một bàn cờ kích thước $n\times n$. Trên bàn cờ, một ô gọi là hợp lệ nếu ô đó chưa có quân cờ nào đồng thời tổng số quân cờ đang có trên $2n-2$ ô cùng hàng hoặc cùng cột với ô đó là một số chẵn. Mỗi bước An đặt một quân cờ vào một ô hợp lệ.

a) Xét $n=8$ và bàn cờ được tô trắng đen như bàn cờ vua tiêu chuẩn. Chứng minh rằng An có thể đặt hết 32 quân cờ vào 32 ô trắng của bàn cờ.

b) Với $n=8$, chứng minh rằng nếu với mỗi bước đặt quân cờ An chọn ngẫu nhiên một ô hợp lệ thì An luôn đặt được toàn bộ 32 quân cờ lên bàn cờ.

c) Với $n=7$, hỏi nếu với mỗi bước đặt quân cờ An chọn ngẫu nhiên một ô hợp lệ thì có còn đảm bảo luôn đặt được toàn bộ 32 quân cờ lên bàn cờ hay không? Vì sao?

Gọi $r_i$ là số quân cờ trên hàng $i$ và $c_j$ là số quân cờ trên cột $j$. Vì ô $(i,j)$ đang trống nên tổng số quân trên các ô cùng hàng hoặc cùng cột với nó bằng $r_i+c_j$. Do đó
$$(i,j)\text{ hợp lệ }⟺r_i+c_j\equiv 0(\mathrm{mod}2),$$
Gọi $u$ là số hàng chứa lẻ quân và $v$ là số cột chứa lẻ quân. Ban đầu $u=v=0$. Mỗi nước đi hợp lệ có đúng một trong hai dạng:
- Đặt tại giao của một hàng chẵn và một cột chẵn, khi đó $u,v$ cùng tăng 1;
- Đặt tại giao của một hàng lẻ và một cột lẻ, khi đó $u,v$ cùng giảm 1.
Vì thế, trong suốt trò chơi ta luôn có bất biến là $u=v$.

a) Gọi $M_0$ là các ô màu xanh nước biển, $M_1$ là các ô màu xanh lá cây, $M_2$ là các ô màu cam, $M_3$ là các ô màu đỏ. An lần lượt đặt hết các quân trong $M_0,M_1,M_2,M_3$ và để ý mọi bước đều hợp lệ.



b) Giả sử An bị kẹt sau khi đã đặt $m$ quân. Khi đó không còn ô trống hợp lệ. Theo bất biến, có cùng $u$ hàng lẻ và $u$ cột lẻ. Do không còn ô hợp lệ nên mọi giao điểm của hai cột với hàng cùng tính chẵn lẻ đều đã có quân. Vì vậy
$$m⩾u^2+(8-u{)}^2=2(u-4{)}^2+32⩾32.$$
Suy ra trước khi đặt đủ 32 quân, An không thể bị kẹt, ta có điều phải chứng minh.

c) Câu trả lời là không. Ban đầu An điền các ô như sau:



Sau khi điền xong, An đã đặt 25 quân. Ba hàng và ba cột của khối $3\times 3$ đều lẻ; bốn hàng và bốn cột còn lại đều chẵn. Vì thế mọi ô trống đều nối một hàng lẻ với một cột chẵn hoặc ngược lại, nên không hợp lệ. An bị kẹt và còn thừa 7 quân; do đó câu trả lời là không.

Nhận xét. Ngoài ra với bảng $n\times n$ tổng quát, An có thể luôn đặt được tối đa $\frac{n^2+1}{2}$ quân với $n$ lẻ, và $\frac{n^2+2n}{2}$ quân với $n$ chẵn. Bạn đọc có thể thử sức để chỉ ra điều này.