Un soldato…
Un soldato incontra sulla riva del fiume due ragazzini con una piccola barca.
Tutti vogliono attraversare il fiume ma la barca può trasportare al massimo un soldato oppure due ragazzini.
| 1° sponda | barca | 2° sponda | |
|---|---|---|---|
| S R R | |||
| 1 | S | → R R → | |
| 2 | S | ← R ← | R |
| 3 | R | → S → | R |
| 4 | R | ← R ← | S |
| 5 | → R R → | S | |
| S R R |
Due soldati…
| 1° sponda | barca | 2° sponda | |
|---|---|---|---|
| S S R R | |||
| 1 | S S | → R R → | |
| 2 | S S | ← R ← | R |
| 3 | S R | → S → | R |
| 4 | S R | ← R ← | S |
| 5 | S | → R R → | S |
| 6 | S | ← R ← | S R |
| 7 | R | → S → | S R |
| 8 | R | ← R ← | S S |
| 9 | → R R → | S S | |
| S S R R |
Tre soldati…
| 1° sponda | barca | 2° sponda | |
|---|---|---|---|
| S S S R R | |||
| 1 | S S S | → R R → | |
| 2 | S S S | ← R ← | R |
| 3 | S S R | → S → | R |
| 4 | S S R | ← R ← | S |
| 5 | S S | → R R → | S |
| 6 | S S | ← R ← | S R |
| 7 | S R | → S → | R |
| 8 | S R | ← R ← | S |
| 9 | S | → R R → | S |
| 10 | S | ← R ← | S R |
| 11 | R | → S → | S R |
| 12 | R | ← R ← | S S |
| 13 | → R R → | S S | |
| S S S R R |
Se n è il numero di soldati
- n = 0, attraversamenti = 1
- n = 1, attraversamenti = 5
- n = 2, attraversamenti = 9
- n = 3, attraversamenti = 13
- …
numero di attraversamenti: 4·n+1