Câu hỏi 189
Tất cả ghế trong lớp học được sắp xếp thành mảng $n \times n$ hình vuông (nói cách khác là cột $n$ và hàng $n$), và mỗi ghế đều có một học sinh ngồi. Giáo viên quyết định sắp xếp lại học sinh theo hai quy tắc sau:
a. Mỗi học sinh phải chuyển sang ghế mới.
b. Học sinh chỉ có thể di chuyển sang ghế liền kề trong cùng một hàng hoặc sang ghế liền kề trong cùng một cột. Nói cách khác, mỗi học sinh chỉ được di chuyển một chiếc ghế theo chiều ngang hoặc chiều dọc.
(Lưu ý rằng các quy tắc trên cho phép hai học sinh ngồi ở ghế liền kề đổi chỗ cho nhau.)
Chứng minh rằng quy trình này có thể thực hiện được nếu $n$ là số chẵn và không thể thực hiện được nếu $n$ là số lẻ.
a. Mỗi học sinh phải chuyển sang ghế mới.
b. Học sinh chỉ có thể di chuyển sang ghế liền kề trong cùng một hàng hoặc sang ghế liền kề trong cùng một cột. Nói cách khác, mỗi học sinh chỉ được di chuyển một chiếc ghế theo chiều ngang hoặc chiều dọc.
(Lưu ý rằng các quy tắc trên cho phép hai học sinh ngồi ở ghế liền kề đổi chỗ cho nhau.)
Chứng minh rằng quy trình này có thể thực hiện được nếu $n$ là số chẵn và không thể thực hiện được nếu $n$ là số lẻ.