“Bài toán qua đò” có bao nhiêu lời giải?

Đây là nội dung của một câu đố cổ: có một người cần chở một con sói, một con dê và một sọt rau cải qua sông. Giả thiết rằng sói không ăn thịt người. Bên bờ sông chỉ có một chiếc thuyền nhỏ, mỗi lần thuyền chỉ chở được người lái cùng một thứ; nếu chở hai thứ trở lên thì thuyền sẽ chìm. Mặt khác, nếu không có người giám sát thì sói sẽ ăn dê, còn dê sẽ ăn rau. Vậy phải làm thế nào để cả sói, dê và rau đều sang được bờ bên kia an toàn?

Đây chính là “bài toán chở qua sông”, còn gọi là bài toán “sói, dê, rau”. Với nhiều người, bài này không quá khó; chỉ cần thử vài lần là có thể tìm được cách qua sông. Nhưng nếu hỏi bài toán có bao nhiêu lời giải thì câu hỏi trở nên khó hơn.

Có thể liệt kê các trạng thái của hai bờ sông để tìm lời giải. Trạng thái đầu là mọi thứ còn ở bờ xuất phát, trạng thái cuối là sói, dê và rau đều sang bờ bên kia. Mỗi lần người lái thuyền chở một thứ qua sông hoặc quay về sẽ làm trạng thái thay đổi.

Bước đầu tiên, người lái buộc phải chở dê qua trước, vì nếu chở sói hoặc rau thì hai thứ còn lại ở bờ cũ sẽ gây hại cho nhau. Sau đó người quay thuyền về. Ở bước tiếp theo, người có thể chở rau hoặc chở sói qua, từ đó xuất hiện hai phương án đối xứng.

Nếu người chở rau qua trước, người không thể quay thuyền về tay không vì dê sẽ ăn rau. Vì vậy, người phải chở dê quay lại. Sau đó chở sói sang, rồi quay về tay không vì sói và rau có thể ở cùng nhau. Cuối cùng người chở dê sang lần nữa. Như vậy, mọi thứ đều qua sông an toàn.

Phương án còn lại tương tự, chỉ khác ở chỗ chở sói trước rồi chở rau sau. Nếu không cho phép lặp lại trạng thái, bài toán qua sông này có đúng hai lời giải cơ bản và cần ít nhất bảy lần đi thuyền.