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 incontrano sulla riva del fiume due ragazzini con una piccola barca…
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 incontrano sulla riva del fiume due ragazzini con una piccola barca…
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 » S r 8. S r ← r ← S S 9. S » r r » S S 10. S ← r ← S S r 11. r » S » S S r 12. r ← r ← S S S 13. » r r » S 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