Trên sân trường có một bảng ô vuông kích thước 6m × 5m. Có 15 học sinh mặc áo màu xanh (trong
Trên sân trường có một bảng ô vuông kích thước 6m × 5m. Có 15 học sinh mặc áo màu xanh (trong đó chỉ có đúng một học sinh tên An và một học sinh tên Bảo) và 14 học sinh mặc áo màu trắng xếp hình thành chữ LS (viết tắt chữ Lam Sơn) sao cho mỗi học sinh đứng ở một ô vuông 1m × 1m, dư lại một ô vuông trống (đánh dấu X), hai học sinh mặc áo xanh tên An và Bảo đứng ở hai ô vuông góc đối diện như hình vẽ (bảng 1).
Cho phép đổi vị trí các học sinh trong bảng theo quy tắc: Mỗi lần, chọn một học sinh đứng ở ô vuông kề với ô vuông trống rồi chuyển học sinh đó sang ô vuông trống. Hỏi bằng cách thực hiện liên tiếp một số hữu hạn lần phép chuyển học sinh theo quy tắc trên đối với bảng 1 ta có thể nhận được cách xếp sao cho An và Bảo đổi chỗ cho nhau còn các học sinh khác giữ nguyên vị trí như hình vẽ (bảng 2) hay không? Vì sao?
Quảng cáo
Sử dụng lý thuyết về tính bất biến của tính chẵn lẻ trong hoán vị và khoảng cách của ô trống.
Tại thời điểm ban đầu ta gán cho 29 học sinh đứng trên sân trường các số 1, 2, 3, ..., 29 như trong bảng sau:
Dưới đây là nội dung văn bản được chuyển đổi chính xác từ hình ảnh của bạn:
Xét dãy S = (a_1, a_2, ... , a_{28}, a_{29}) gồm các số được gán cho 29 học sinh trên sân trường theo thứ tự từ trái sang phải và từ trên xuống dưới. Tại thời điểm đầu dãy S là 1, 2, 3, ..., 28, 29 với a_1 = 1; a_2 = 2; ..... ; a_{28} = 28; a_{29} = 29.
Nếu sau một số phép chuyển mà An và Bảo đổi chỗ cho nhau thì ta có dãy S là 29, 2, 3, ..., 28, 1.
Khi đó a_1 = 29; a_2 = 2; ..... ; a_{28} = 28; a_{29} = 1.
Xét n là số các cặp (i; j) trong đó $1 \leq i < j \leq 29$ nhưng $a_{i} > a_{j}$.
Tại thời điểm đầu ta có n = 0.
Tại thời điểm cuối cùng với dãy S là 29, 2, 3, ..., 28, 1 thì ta có 55 cặp (i; j) như trên là
(1; 2), (1; 3), ..., (1; 28), (1; 29), (2; 29), (3; 29) , ...., (28; 29). Do đó n = 55.
Chú ý rằng với mỗi phép chuyển học sinh sang ô vuông trống thì chỉ có 2 khả năng xảy ra:
- Nếu học sinh di chuyển sang trái hoặc phải trên cùng 1 hàng của bảng thì dãy S không thay đổi, nên n không thay đổi.
- Nếu học sinh di chuyển lên hàng trên hoặc xuống hàng dưới thì số được gán cho học sinh đó đã tiến 4 vị trí hoặc lùi 4 vị trí trong dãy S. Khi đó n tăng 4 hoặc giảm 4.
Ví dụ khi học sinh gán số 8 chuyển sang ô X thì dãy S mới là 1, 2, ..., 7, 9, 10, 11, 12, 8, 13,
14, ..., 28, 29 ta thấy có thêm 4 cặp (i; j) trong đó $1 \leq i < j \leq 29$ nhưng $a_{i} > a_{j}$ là (8; 12), (9; 12); (10; 12), (11; 12).
Vậy lúc đầu n = 0 thì sau một số hữu hạn phép chuyển không thể nhận được n = 55.
Do đó không thể nhận được cách xếp sao cho An và Bảo đổi chỗ cho nhau còn các học sinh khác
giữ nguyên vị trí.
PH/HS 2K10 THAM GIA NHÓM ĐỂ CẬP NHẬT ĐIỂM THI, ĐIỂM CHUẨN MIỄN PHÍ!
>> Học trực tuyến lớp 9 và Lộ trình UP10 trên Tuyensinh247.com Đầy đủ khoá học các bộ sách: Kết nối tri thức với cuộc sống; Chân trời sáng tạo; Cánh diều. Lộ trình học tập 3 giai đoạn: Học nền tảng lớp 9, Ôn thi vào lớp 10, Luyện Đề. Bứt phá điểm lớp 9, thi vào lớp 10 kết quả cao. Hoàn trả học phí nếu học không hiệu quả. PH/HS tham khảo chi tiết khoá học tại: Link
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
