Hướng dẫn chi tiết cách giải bài toán quân xe di chuyển qua 64 ô bàn cờ vua - O30/4. Tìm GTNN của hiệu số lớn nhất giữa hai ô kề cạnh bằng phản chứng.
Giải chi tiết câu toán rời rạc trên bàn cờ vua 8x8
Trong các kỳ thi học sinh giỏi và tuyển sinh chuyên, các bài toán tổ hợp và rời rạc trên bàn cờ luôn là những thử thách thú vị. MathVN xin giới thiệu lời giải chi tiết cho bài toán về quân xe di chuyển trên bàn cờ ($8 \times 8$) dưới đây.
Đề bài toán
[Câu 5. (4 điểm) - Đề Olympic 30/4 lần thứ XXX môn Toán khối 10]Một quân xe di chuyển $63$ nước đi trên bàn cờ vua ($8 \times 8$), đi qua tất cả các ô, mỗi ô đúng một lần và mỗi nước đi nó chỉ di chuyển từ một ô sang một ô có chung cạnh. Đánh số các ô của bàn cờ từ 1 đến 64 theo thứ tự mà quân xe đi qua (vị trí ban đầu của quân xe được đánh số 1).
Gọi $n$ là hiệu số lớn nhất giữa các số của hai ô có chung cạnh. Hỏi giá trị nhỏ nhất có thể có của $n$ là bao nhiêu?
Lời giải chi tiết
1. Xét một trường hợp cụ thể (Cách đi hình con rắn)
Trước hết, xét cách đi hình con rắn của quân xe: Bắt đầu từ góc dưới bên trái, đi sang phải, mỗi nước sang ô bên cạnh cho đến hết hàng, sau đó đi lên ô ở hàng ngay trên, rồi đi sang trái, mỗi nước sang ô bên cạnh cho đến hết hàng, rồi đi lên ô ở hàng phía trên, v.v.
Với cách đi này, ta dễ thấy rằng hiệu số lớn nhất của 2 ô chung cạnh bằng 15.
2. Chứng minh giá trị nhỏ nhất cần tìm là 15
Ta chứng minh đây là giá trị nhỏ nhất cần tìm bằng phương pháp phản chứng.
Giả sử ngược lại rằng $n < 15$.
Xét các số ở hàng trên cùng:
- Vì hiệu giữa hai số kề nhau trong hàng này không vượt quá 14, nên quân xe đi từ một số nhỏ hơn đến một số lớn hơn ở trên hàng này mà không đi qua một ô ở hàng dưới cùng (vì để xuống đó cần ít nhất 7 nước, và để quay lại cũng cần ít nhất 7 nước, cộng thêm một nước trong chính hàng dưới).
- Do đó quân xe đã đi qua tất cả các ô của hàng trên cùng mà không đi xuống hàng dưới cùng.
Tương tự, quân xe di chuyển qua các ô của hàng dưới cùng mà không đi lên hàng trên cùng. Điều này có nghĩa là tất cả các số ở hàng trên cùng đều lớn hơn (hoặc đều nhỏ hơn) các số ở hàng dưới cùng.
Lập luận tương tự cho các cột:
- Tất cả các số ở cột ngoài cùng bên trái đều lớn hơn (hoặc đều nhỏ hơn) các số ở cột ngoài cùng bên phải.
- Không mất tính tổng quát, giả sử các số ở cột ngoài cùng bên trái lớn hơn các số ở cột ngoài cùng bên phải, còn các số ở hàng dưới cùng lớn hơn các số ở hàng trên cùng.
Bây giờ, gọi $A$ là số của ô góc trên cùng bên trái và $B$ là số của ô góc dưới cùng bên phải.
Theo giả thiết:
Điều này dẫn đến mâu thuẫn.
3. Kết luận
Giá trị nhỏ nhất có thể có của $n$ là $\boxed{\mathbf{15}}$.
