Bài toán qua sông

Học xong bài này

Mục tiêu bài học

Biết tổ chức dữ kiện của chuyên đề “Bài toán qua sông” bằng bảng, sơ đồ hoặc loại trừ.
Suy luận từng bước từ điều chắc chắn, không bỏ sót điều kiện.
Kiểm tra phương án cuối cùng với toàn bộ dữ kiện.

Nắm chắc trước khi làm bài

Kiến thức cần nhớ

Giải bằng trạng thái hai bờ: ghi người lái và từng vật ở bờ trái hay bờ phải. Một lượt là một chuyến thuyền đi qua sông, kể cả chuyến quay về.

Người lái luôn có mặt trên thuyền; mỗi chuyến chỉ chở không quá sức chứa được cho trong đề.
Chỉ chuyển sang trạng thái mới nếu tại bờ không có người lái không tồn tại cặp vật bị cấm ở chung.
Một vật được phép đưa quay lại nếu giúp tránh trạng thái nguy hiểm hoặc mở đường cho lượt kế tiếp.
Muốn chứng minh ít lượt nhất, có thể lập sơ đồ các trạng thái hợp lệ và xét lần lượt những trạng thái đến được sau 1, 2, 3… lượt; lần đầu gặp trạng thái đích là số lượt tối thiểu.

Quan sát cách làm

Ví dụ minh họa

Ví dụ 1: Bài toán quen thuộc về cáo, gà và bao thóc. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: cáo với gà, gà với bao thóc. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Hướng dẫn giải chi tiết:

Một cách chuyển hợp lệ: 1. trái → phải: gà; 2. phải → trái: không chở vật nào; 3. trái → phải: cáo; 4. phải → trái: gà; 5. trái → phải: bao thóc; 6. phải → trái: không chở vật nào; 7. trái → phải: gà.

Đáp án: ít nhất 7 lượt qua sông (tính cả lượt trở về). Sau mỗi lượt, không có cặp cấm nào ở cùng bờ khi thiếu người lái. Có thể kiểm tra tính tối thiểu bằng cách liệt kê các trạng thái hợp lệ theo số lượt.

Ví dụ 2: Một người phụ trách đưa bốn nhóm sinh vật và thức ăn qua bến. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: mèo với chim, chim với sâu, sâu với khay rau. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Hướng dẫn giải chi tiết:

Một cách chuyển hợp lệ: 1. trái → phải: mèo, sâu; 2. phải → trái: không chở vật nào; 3. trái → phải: chim, khay rau.

Đáp án: ít nhất 3 lượt qua sông (tính cả lượt trở về). Sau mỗi lượt, không có cặp cấm nào ở cùng bờ khi thiếu người lái. Có thể kiểm tra tính tối thiểu bằng cách liệt kê các trạng thái hợp lệ theo số lượt.

Ví dụ 3: Năm kiện hàng có các cặp phải được trông coi khi đứng cùng nhau. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: kiện A với kiện B, kiện A với kiện C, kiện A với kiện D, kiện A với kiện E. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Hướng dẫn giải chi tiết:

Một cách chuyển hợp lệ: 1. trái → phải: kiện A; 2. phải → trái: không chở vật nào; 3. trái → phải: kiện B, kiện C; 4. phải → trái: kiện A; 5. trái → phải: kiện A, kiện D; 6. phải → trái: kiện A; 7. trái → phải: kiện A, kiện E.

Luyện ngay sau ví dụ

Bài tập áp dụng

Bài 1: Hai con vật được đưa đến chuồng mới. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: mèo với chuột. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 2: Người chăn nuôi cần đưa chó, thỏ và cỏ về phía đối diện. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: chó với thỏ. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 3: Ba thùng hóa chất mô phỏng cần người giám sát nếu ở cùng bờ. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: thùng đỏ với thùng xanh, thùng đỏ với thùng vàng, thùng xanh với thùng vàng. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 4: Thêm một bao bắp vào tình huống cáo, gà và thóc. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: cáo với gà, gà với thóc. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 5: Bốn nhóm đồ vật và con vật được vận chuyển cùng một chuyến đò nhỏ. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: mèo với chim, chim với sâu, sâu với hạt kê. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Xem lời giải

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: mèo; 2. phải → trái: không chở vật nào; 3. trái → phải: chuột.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: chó; 2. phải → trái: không chở vật nào; 3. trái → phải: sọt cỏ; 4. phải → trái: không chở vật nào; 5. trái → phải: thỏ.

Đáp án: ít nhất 5 lượt qua sông (tính cả lượt trở về). Sau mỗi lượt, không có cặp cấm nào ở cùng bờ khi thiếu người lái. Có thể kiểm tra tính tối thiểu bằng cách liệt kê các trạng thái hợp lệ theo số lượt.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: thùng đỏ, thùng xanh; 2. phải → trái: thùng đỏ; 3. trái → phải: thùng đỏ, thùng vàng.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: gà; 2. phải → trái: không chở vật nào; 3. trái → phải: cáo; 4. phải → trái: gà; 5. trái → phải: thóc; 6. phải → trái: không chở vật nào; 7. trái → phải: bắp; 8. phải → trái: không chở vật nào; 9. trái → phải: gà.

Đáp án: ít nhất 9 lượt qua sông (tính cả lượt trở về). Sau mỗi lượt, không có cặp cấm nào ở cùng bờ khi thiếu người lái. Có thể kiểm tra tính tối thiểu bằng cách liệt kê các trạng thái hợp lệ theo số lượt.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: mèo, sâu; 2. phải → trái: không chở vật nào; 3. trái → phải: chim, hạt kê.

Tự kiểm tra mức độ thành thạo

Bài tập tự luyện

Bài 1: Khi người trông vắng mặt, chó không được đứng cùng một số con vật khác. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: chó với mèo, chó với chuột, chó với chim. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 2: Bốn kiện có những cặp không thể để cạnh nhau mà thiếu người giám sát. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: hộp A với hộp B, hộp A với hộp C, hộp A với hộp D, hộp B với hộp C, hộp B với hộp D. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 3: Năm sọt hàng được xếp theo các quy tắc an toàn ở bờ sông. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: sọt A với sọt B, sọt A với sọt C, sọt A với sọt D. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 4: Ba bình đầu trong lô năm bình không được để cạnh nhau khi thiếu người. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: bình A với bình B, bình A với bình C, bình B với bình C. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 5: Một nhân viên đưa năm lồng trưng bày qua sông. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: lồng A với lồng B, lồng A với lồng C, lồng A với lồng D, lồng A với lồng E. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 6: Năm thùng cần được vận chuyển với quy tắc bảo quản riêng. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: thùng A với thùng B, thùng A với thùng C, thùng A với thùng D, thùng B với thùng E. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 7: Một người lái thuyền chở năm kiện được đánh số. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: kiện số 1 với kiện số 2, kiện số 2 với kiện số 3, kiện số 3 với kiện số 4, kiện số 4 với kiện số 5. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 8: Năm vật trên bến được mô phỏng bằng kí hiệu P, Q, R, S, T. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: vật P với vật Q, vật Q với vật R, vật R với vật S, vật P với vật T. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 9: Bốn thứ cần được chuyển sang bờ kia, chỉ có một cặp phải trông coi. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: chó với mèo. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 10: Bài khó hơn: đò chỉ chở được người cùng một thùng mỗi lượt. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 1 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: thùng 1 với thùng 2, thùng 1 với thùng 3. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 11: Bốn gói hàng bị ràng buộc bởi nhiều cặp phải có người giám sát. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: gói A với gói B, gói A với gói C, gói A với gói D, gói B với gói C, gói B với gói D. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Bài 12: Bài tổng hợp cuối: năm mẫu được chuyển qua sông theo quy tắc ghép cặp. Người lái luôn đi cùng thuyền; mỗi lượt chở được người và tối đa 2 vật. Khi người lái không có mặt ở một bờ, các cặp sau không được ở lại cùng bờ: mẫu A với mẫu B, mẫu A với mẫu C, mẫu A với mẫu D, mẫu A với mẫu E, mẫu B với mẫu C, mẫu B với mẫu D. Ban đầu tất cả ở bờ trái. Hãy đưa toàn bộ sang bờ phải bằng ít lượt nhất; liệt kê từng lượt cả chiều về.

Xem lời giải bài tập tự luyện

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: chó; 2. phải → trái: không chở vật nào; 3. trái → phải: mèo, chuột; 4. phải → trái: chó; 5. trái → phải: chó, chim.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: hộp A, hộp B; 2. phải → trái: hộp A; 3. trái → phải: hộp C, hộp D; 4. phải → trái: hộp B; 5. trái → phải: hộp A, hộp B.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: sọt A, sọt B; 2. phải → trái: sọt A; 3. trái → phải: sọt C, sọt D; 4. phải → trái: không chở vật nào; 5. trái → phải: sọt A, sọt E.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: bình A, bình B; 2. phải → trái: bình A; 3. trái → phải: bình A, bình D; 4. phải → trái: bình A; 5. trái → phải: bình A, bình E; 6. phải → trái: bình A; 7. trái → phải: bình A, bình C.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: lồng A; 2. phải → trái: không chở vật nào; 3. trái → phải: lồng B, lồng C; 4. phải → trái: lồng A; 5. trái → phải: lồng A, lồng D; 6. phải → trái: lồng A; 7. trái → phải: lồng A, lồng E.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: thùng A, thùng B; 2. phải → trái: thùng A; 3. trái → phải: thùng C, thùng D; 4. phải → trái: không chở vật nào; 5. trái → phải: thùng A, thùng E.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: kiện số 2, kiện số 4; 2. phải → trái: không chở vật nào; 3. trái → phải: kiện số 1; 4. phải → trái: kiện số 2; 5. trái → phải: kiện số 3, kiện số 5; 6. phải → trái: kiện số 4; 7. trái → phải: kiện số 2, kiện số 4.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: vật P, vật R; 2. phải → trái: không chở vật nào; 3. trái → phải: vật Q; 4. phải → trái: vật P, vật R; 5. trái → phải: vật S, vật T; 6. phải → trái: không chở vật nào; 7. trái → phải: vật P, vật R.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: chó; 2. phải → trái: không chở vật nào; 3. trái → phải: sọt cỏ; 4. phải → trái: không chở vật nào; 5. trái → phải: hũ mật; 6. phải → trái: không chở vật nào; 7. trái → phải: mèo.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: thùng 1; 2. phải → trái: không chở vật nào; 3. trái → phải: thùng 2; 4. phải → trái: thùng 1; 5. trái → phải: thùng 3; 6. phải → trái: không chở vật nào; 7. trái → phải: thùng 4; 8. phải → trái: không chở vật nào; 9. trái → phải: thùng 5; 10. phải → trái: không chở vật nào; 11. trái → phải: thùng 1.

Đáp án: ít nhất 11 lượt qua sông (tính cả lượt trở về). Sau mỗi lượt, không có cặp cấm nào ở cùng bờ khi thiếu người lái. Có thể kiểm tra tính tối thiểu bằng cách liệt kê các trạng thái hợp lệ theo số lượt.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: gói A, gói B; 2. phải → trái: gói A; 3. trái → phải: gói C, gói D; 4. phải → trái: gói B; 5. trái → phải: gói A, gói B.

Lời giải:

Một cách chuyển hợp lệ: 1. trái → phải: mẫu A, mẫu B; 2. phải → trái: mẫu A; 3. trái → phải: mẫu A, mẫu E; 4. phải → trái: mẫu A; 5. trái → phải: mẫu C, mẫu D; 6. phải → trái: mẫu B; 7. trái → phải: mẫu A, mẫu B.

Chốt lại kiến thức

Ghi nhớ

Đánh dấu vị trí từng vật trước và sau mỗi lượt, không kiểm tra chỉ ở điểm kết thúc.
Mỗi chuyến có thể phải mang vật trở về để giữ an toàn cho hai bờ.
Khi hỏi ít lượt nhất, đếm cả lượt người lái quay về và kiểm chứng không có đường đi ngắn hơn.