Due mariti devono attraversare il fiume con le rispettive mogli ma trovano una piccola barca che può trasportare al massimo due persone.
I mariti sono gelosissimi: una moglie è sempre accompagnata dal marito se è presente un altro uomo!
1° sponda BARCA 2° sponda A B a b 1. A B » a b » 2. A B ← a ← b 3. a » A B » b 4. a ← b ← A B 5. » a b » A B A B a b
oppure
1° sponda BARCA 2° sponda A B a b 1. A a » B b » 2. A a ← B ← b 3. a » A B » b 4. a ← A ← B b 5. » A a » B b A B a b
Nella 2° soluzione remano solo i mariti.
Tre mariti …
1° sponda BARCA 2° sponda A B C a b c 1. A B C c » a b » 2. A B C c ← b ← a 3. A B C » b c » a 4. A B C ← c ← a b 5. C c » A B » a b 6. C c ← B b ← A a 7. b c » B C » A a 8. b c ← a ← A B C 9. c » a b » A B C 10. c ← a ← A B C b 11. » a c » A B C b A B C a b c
Quattro mariti …
La barca deve avere almeno 3 posti e sono necessari (__) attraversamenti
1° sponda BARCA 2° sponda A B C a b c 1. A B C D d » a b c » 2. A B C D d ← c ← a b 3. A B C D » c d » a b 4. A B C D ← d ← a b c 5. D d » A B C » a b c 6. D d ← C c ← A B a b 7. d » C D c » A B a b 8. d ← D ← A B C a b c 9. » D d » A B C a b c A B C D a b c d
Cinque mariti …
La barca deve avere almeno 3 posti e sono necessari 11 attraversamenti
1° sponda BARCA 2° sponda A B C D E a b c d e 1. A B C D E d e » a b c » 2. A B C D E d e ← c ← a b 3. A B C D E e » c d » a b 4. A B C D E e ← d ← a b c 5. D E d e » A B C » a b c 6. D E d e ← C c ← A B a b 7. c d e » C D E » A B a b 8. c d e ← a ← A B C D E b 9. a » c d e » A B C D E b 10. a ← A ← B C D E b c d e 11. » A a » B C D E b c d e A B C D E a b c d e
Se le coppie sono più di 5 la barca deve avere almeno 4 posti con 2n-1 attraversamenti