Mariti e mogli

Due mariti …

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!

Remano solo i maschi…

	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

oppure

	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

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	← B ←	A B C
11		→ A C →	A B C B
			A B C A B C

Quattro mariti …

La barca deve avere almeno 3 posti

	1° sponda	barca	2° sponda
	A B C D A B C D
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