Có 3 cặp vợ chồng qua đi picnic. Họ phải vượt qua một con sông trong khi họ chỉ có 1 chiếc thuyền gấp và thuyền này chỉ chở được 2 ngừoi. Hãy giúp họ đi qua sông biết rằng các ông chồng không cho phép vợ của mình ở với người đàn ông khác mà không có mặt mình ở đó.
Ví dụ: các cặp vợ chồng là Aa, Bb, Cc trong đó chữ cái hoa biểu hiện cho chồng
Aa Bb Cc ///
a và b sang sông A B Cc /// a b, a về Aa B Cc /// b, A và B sang a Cc /// A B b -----> A không chịu vì bà a ở lại với ông C
Chia làm các trường hợp sau:
TH1: 1 trong 3 ông chồng sang trước ==> loại vì bên kia có 3 bà vợ và 1 ông chồng (có 2 người "mất vợ")
TH2: 1 đàn ông, 1 đàn bà sang trước thì chỉ có thể là 1 cặp vợ chồng sang trước ==> chỉ có thể chồng quay lại, khi đó ta sẽ có trạng thái là:
Duy nhất có 1 người sang sông trước và là 1 người vợ.Phân làm các trường hợp nhỏ:
1. Người chồng đó đón 1 người vợ khác sang sông ==>loại.
2. Người chồng đó đón 1 người chồng khác sang sông ==> loại vì bên kia song còn 2 vợ + 1 chồng.
3. Bất kì 1 trong 2 người chồng káhc đưa bất kì ai sang sông ==> loại vì bên kia có vợ của người đàn ông đã ở bờ bên này.
4. 2 ngượi vợ sang sông ==> 1 ngwoif quay lại đưa bất kì người đàn ông nào qua đều bị loại.
Vậy trường hợp 2 bị loại.
TH3: 2 người đàn bà sang sông trước, 1 người quay lại ==>Quay về trường hợp 2:
Duy nhất có 1 người sang sông trước và là 1 người vợ.
Vậy không có cách nào để đưa cả 6 người sang sông thoả mãn yêu cầu bài toán. @: Editor xóa giúp mìhn bài trên với
THanks
Bài viết đã được chỉnh sửa nội dung bởi L_Euler: 17-06-2009 - 15:25