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