Non l’ho riletto bene e probabilmente ci sarà qualche imprecisione (leggete a vostro rischio e pericolo
)..
Step 1: se n è dispari o n<4 F(n)=0
Sia F(n) il numero di percorsi di lunghezza n fattibili da A fino a B passando solo una volta per B.
Per n<4 non ho abbastanza mosse per arrivare da A a B.
Per n dispari non posso perchè il numero di mosse minimo è 4, inoltre ad'ogni mossa effettuata nella direzione opposta al verso scelto per arrivare a B (posso sceglierlo in modo orario o antiorario..) ne corrisponde un'altra lungo il verso scelto; sia j il numero di mosse fatte nella direzione opposta al verso scelto ottengo: j+j+4=n; 2j+4=n e n deve essere pari.
Step 2: pongo n=2k; F(2k)=2*g(k)
ovvero: posso scegliere uno tra i 2 versi (orario e antiorario) e analizzare i possibili percorsi regolari che portano da A fino a B lungo quel verso; poi moltiplico per 2 e ottengo i percorsi totali.
Scelgo di considerare i percorsi lungo il verso orario.
Sia g(k) il numero di percorsi di lunghezza 2k che vanno da A fino a B lungo il verso orario.
Inoltre ogni percorso ha j mosse lungo il verso opposto (antiorario) e j+4 lungo il verso orario. 2j+4=2k da cui j+2=k.
Numero i vertici dell'ottagono ordinatamente da uno fino a 8 in modo tale che sia A il vertice 4 e B il vertice 8.
Sia C il vertice con la seguente proprietà: il primo vertice su cui passa il canguro e tale che si siano già effettuate tutte le j mosse in senso antiorario. Se j non è 0 allora C è il vertice su cui atterra il canguro dopo avere fatto l’ultima mossa in senso antiorario
Se j=0 e k=2 allora C=A.
g(k) risulta essere la somme dei percorsi che vedono C=1;C=2;....c=6 (si verifica facilmente che C non può essere B o 7).
Sia a(k)= numero percorsi di lunghezza 2k con C=1
b(k)= numero percorsi di lunghezza 2k con C=2
c(k)= numero percorsi di lunghezza 2k con C=3
d(k)= numero percorsi di lunghezza 2k con C=4=A
e(k)= numero percorsi di lunghezza 2k con C=5
f(k)= numero percorsi di lunghezza 2k con C=6
g(k)=a(k)+b(k)+c(k)+d(k)+e(k)+f(k)
Inoltre posso vedere a(k);b(k)... f(k) come il numero di percorsi che portano da A fino a C (con C=1,2,..) effettuando j=k-2 mosse in verso antiorario e non passando mai per B.
Step 3: relazione ricorsiva..
Il numero di percorsi con k=m+1 e C=1 è a(m+1).
Inoltre la mossa prima di arrivare nel vertice 1 necessariamente si era nel vertice 2.In quel momento le mosse in senso antiorario effettuate erano m-2.
Chiamo C' il vertice in cui si era effettuate la penultima mossa in senso antiorario. Quel vertice può essere solamente 1 o 2. Inoltre fissato C' esiste un unico possibile percorso che porta ad effettuare le ultime mosse (perchè posso fare solo un'altra mossa in senso antiorario e ne ho già deciso la posizione;inoltre le mosse restanti per arrivare a B sono in senso orario).
In generale C' può essere qualsiasi vertice tale che C sia distante da C' massimo una mossa in senso antiorario (se C=1 allora C' è 1 o 2) e quante mosse voglio in senso orario (sempre con la condizione di non passare da B..); (ovvero stando in C' posso arrivare in C facendo massimo una mossa in senso antiorario e quante ne voglio in senso orario senza però passare da B) quindi C'<C+2 e C'<7.
Inoltre (con C=1) i percorsi per andare da A fino a C' effettuando m-2 mosse in senso antiorario sono, se C'=1, a(m) e, se C'=2, b(m).
ottengo la relazione a(m+1)=a(m)+b(m).
Effettuando lo stesso identico ragionamento per C=2,3,4,5,6 ottengo le seguenti relazioni ricorsive:
b(m+1)=a(m)+b(m)+c(m)
c(m+1)=a(m)+b(m)+c(m)+d(m)
d(m+1)=a(m)+b(m)+c(m)+d(m)+e(m)
e(m+1)=a(m)+b(m)+c(m)+d(m)+e(m)+f(m)
f(m+1)=a(m)+b(m)+c(m)+d(m)+e(m)+f(m)
e quindi le relazioni:
g(k+1)=6a(k)+6b(k)+5c(k)+4d(k)+3e(k)+2f(k)
f(n)=e(n)
Inoltre g(2)=1 perchè in senso orario vi è un unico percorso con j=0.
g(2)=d(2)=1 e
a(2)=0
b(2)=0
c(2)=0
e(2)=0
f(2)=0
e queste relazioni bastano per definire g(k) e F(n).
Inoltre secondo le schede di Gobbino si possono riscrivere come relazioni che coinvolgano una sola successione (lascio ad altri la fatica) che si possa poi portare in funzione di k e quindi di n.
Buona serata. Simone
) salta sui vertici secondo queste regole:
