Salti dell'orso

[hamming_burst]

Propongo un giochino simpatico adatto a tutti (risolvibile in più modi):

Un orsacchiotto deve arrampicarsi in cima ad un abete. Ci sono da superare $M$ ramificazioni prima di arrivare in alto.
Con un salto (se non si spezza) può distanziarsi di $1$ oppure $2$ rami. Quanti percorsi diversi può fare l'orsacchiotto per arrivare alla punta?

es. con $M=1$ ci possono essere due scelte: $2$ salti singoli oppure $1$ salto doppio.

hint:

i vari metodi di soluzione hanno un legame ben noto

[milizia96]

"hamming_burst":con $M=1$ ci possono essere due scelte: $2$ salti singoli oppure $1$ salto doppio.

Non basterebbe un salto singolo? Oppure sono io che non ho capito bene come funzionano i salti...

[hamming_burst]

Ciao,

"milizia96":[quote="hamming_burst"]con $M=1$ ci possono essere due scelte: $2$ salti singoli oppure $1$ salto doppio.

Non basterebbe un salto singolo? Oppure sono io che non ho capito bene come funzionano i salti...[/quote]
Rispiego l'esempio:
$M=0$ ha un solo modo di salire, da terra con un singolo salto arriva in cima, non ci sono rami in mezzo.
$M=1$ vuol dire che c'è in mezzo un ramo, perciò salta due volte (terra-ramo, ramo-cima) oppure un salto unico (terra-cima).

Quello che si chiede: in generale quanti percorsi diversi ci possono essere.

[milizia96]

Ah, ora ho capito.

Chiamo con $f(n)$ il numero di percorsi possibili con $n$ rami.
Per arrivare in cima (dopo $M$ rami) ci sono due possibilità:
1) L'ultimo salto è singolo: questo caso si presenta $f(M-1)$ volte.
2) L'ultimo salto è doppio: questo caso si presenta $f(M-2)$ volte.
In totale, $f(M)=f(M-1)+f(M-2)$.
Cioè si tratta della successione di Fibonacci con i primi due termini $f(0)=1$ e $f(1)=2$.

Intanto propongo una variante del problema: l'orsacchiotto, invece di essere costretto a fare salti da $1$ o da $2$, può compiere salti alti quanto vuole. Quanti sono in questo caso i percorsi possibili?

[hamming_burst]

@milizia96:

Ottimo!
Conosco almeno un altro metodo di soluzione, riesci a trovarlo?

[marco99991]

@milizia96

per la variante io direi che se $M$ è il numero di rami le possibilità sono $2^M$. Prendendo spunto dalla tua dimostrazione, si ha che
$f(M)$=$f(M-1)$+...$f(1)$+$f(0)$+$1$ (l'$1$ è dovuto al fatto che c'è la possibilità di raggiungere la cima dell'albero con un solo salto, cosa che non potevi fare nel problema proposto inizialmente).
Quindi si trova una sequenza in cui ciascun numero è la somma di tutti i precedenti aumentata di $1$, in pratica le potenze di $2$.

[milizia96]

@marco9999

Benissimo
Anche per la mia variante c'è almeno un altro metodo di soluzione, che a mio avviso è molto più immediato di quello che hai proposto tu (che comunque va benissimo). Vediamo se riesci a trovarlo!

[marco99991]

@milizia96

forse c'entrano i binomiali. Per ogni $M$ il numero di percorsi con $n$ salti è $((M),(n))$, però questo almeno per me non è immediato, ho visto che funziona per valori di $M$ piccoli quindi dovrebbe essere così. Si sa poi che la somma dei numeri di una riga qualsiasi del triangolo di Tartaglia è una potenza di $2$.
E' giusta l'idea o avevi pensato ad altro?

[milizia96]

@marco9999

Anche quella dimostrazione andrebbe bene... ma non è quella a cui pensavo io (che rimane a mio parere la più semplice).
Pensa in che modo l'orsacchiotto può scegliere un percorso per salire.

[marco99991]

@milizia96

ho capito! Scegliere un percorso per l'orsacchiotto vuol dire scegliere quali rami considerare nell'arrampicata e quali no. Quindi è equivalente a contare tutti i sottoinsiemi che si possono formare con $M$ elementi, cioè $2^M$.

[milizia96]

@marco9999

Perfetto