Soldati e ragazzini

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