[Traum]

Câu b)
Trước hết điều kiện của bài toán tương đương với tìm q nhỏ nhất để tồn tại cách đánh dấu q ô của bảng sao cho không có hai ô được đánh dấu nào kề nhau và nếu chuyển $1 $ ô bất kì được đánh dấu sang ô bên cạnh của nó, thì sẽ có ô được đánh dấu kề nhau.

Với cách đánh dấu $n $ ô trên đường chéo chính của hình $n\times n $ thì nếu ta chuyển một ô đánh dấu bất kì sang ô bên cạnh nó, sẽ có $2 $ ô đánh dấu kề nhau. Do đó $q \le n $


Ta chứng minh $q \le n $ bằng cách chứng minh kết quả "tổng quát" hơn sau: Với mọi cách đánh dấu $q = \min\{m,n\} - 1 $ ô của một bảng $m\times n $ bất kì sao cho không có hai ô nào kề nhau, thì ta có thể tìm được một ô được đánh dấu mà khi chuyển nó sang một ô bên cạnh nào đó của nó thì sẽ thu được cách đánh dấu mới cũng thỏa mãn không có hai ô nào kề nhau.

Quy nạp theo $k = \min\{m,n\} $.
Với $k = 2 $ thì dễ thấy kết luận trên là đúng.

Xét bảng $m\times n $, do chỉ có $\le \min\{m,n\} - 1 $ ô nên tồn tại một hàng $i $ và một cột $j $ sao cho hàng $i $ và cột $j $ không chứa ô được đánh dấu nào. Chú ý ta có thể giả sử là hàng $i $ và cột $j $ đó không nằm ở biên, nếu không thì ta có thể chuyển ngay ô được đánh dấu gần biên nhất sang hướng ra biên, cách đánh dấu mới này thỏa mãn.
Hàng và cột trên chia bảng thành $4 $ bảng con là $A,B,C,D $. Ta cũng có thể giả sử là trên mỗi bảng con đều chứa các ô được đánh dấu, nếu không thì lý luận như trên, ta có cách đánh dấu mới thỏa mãn.
Giả sử số ô được đánh dấu ở các bảng con $A,B,C,D $ lần lượt là $x,y,z,t $ và kích thước của các bảng là $a\times c, a\times d, b\times c, b\times d $ với $a + b = m-1, c + d = n-1 $. Nếu $x\ge \min\{a,c\}, y\ge \min\{a,d\}, z\ge \min\{b,c\}, t\ge \min\{b,d\} $, thì dễ dàng chỉ ra rằng $x + y + z + t > \min\{m,n\} - 1 $ (chia trường hợp ra, vài phép so sánh đơn giản). Do đó ta có tồn tại chẳng hạn $1 \le x \le\ min \{a,c\} - 1 $, và theo giả thuyết quy nạp thì ta có thể chuyển 1 ô trong bảng con này sang một trong các ô cạnh nó để thu được cách đánh dấu mới thỏa mãn cho bảng con và hiển nhiên cho bảng lớn ban đầu.

Với $m = n $ thì ta có $q > n - 1 $, do đó đáp số là $q = n $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]