Combinatoria

[anto_zoolander]

Ho trovato questo problema che è carino

data una tabella quadrata $3*3$. Si immagini di essere il Re(scacchisticamente parlando) e di muovere dalla casella centrale: quanti sono i possibili percorsi lunghi $5$ passi che puoi effettuare?

[kobeilprofeta]

26861

[anto_zoolander]

il risultato è 3840. Come l'hai svolto?

[Pachisi]

Il metodo è un po' brute force, ma non mi veniva altro.

Chiamo A i quattro angoli, B i quattro "pezzi centrali" (tra due angoli consecutivi), C il centro.
Dividiamo i percorsi per come fanno le prime due mosse:
AC,BC,AB,BA,BB

AC:
Abbiamo $4$ angoli e $1$ modo per arrivare al centro da ogni angolo. Il numero di percorsi di lunghezza $3$ partendo dal centro sono $168$. Quindi, abbiamo $4 \cdot 168$ percorsi.

BC:
Stesso ragionamento porta a $4 \cdot 168$ percorsi.

AB:
Abbiamo $4$ angoli e $2$ pezzi B da raggiungere per ogni angolo. Una volta raggiunto un pezzo B, abbiamo ancora $3$ mosse. Possiamo raggiungere un angolo, il centro, o un pezzo B. Abbiamo $2$ modi di raggiungere un angolo e $18$ percorsi di due mosse da fare dopo aver raggiunto l'angolo. Abbiamo un modo di raggiungere il centro e $32$ percorsi di due mosse da fare dopo averlo raggiunto. Abbiamo $2$ modi raggiungere un pezzo B e $24$ percorsi di due mosse da fare dopo averlo raggiunto. In totale, abbiamo $4 \cdot 2 (32+2\cdot18+2\cdot24)$ percorsi.

BA:
Il ragionamento è simile. Se serve lo scrivo/ Comunque, vengono $4\cdot2(32+2\cdot24)$ percorsi.

BB:
In modo simile, vengono $4\cdot2(32+2\cdot24+2\cdot18)$ percorsi.

Sommando tutto, viene $3840$.

Spero di essere stato chiaro.

[anto_zoolander]

@pachisi

il metodo è corretto e puoi formalizzarlo un po' di più usandovla combinatoria ricorsiva.

[Pachisi]

Hai ragione.
Però, alla fine, non mi sembra cambi molto.
Problema carino comunque.

[kobeilprofeta]

EDIT

Ho usato un calcolatore e mi viene 3840

[kobeilprofeta]

$n_c=8,n_b=5,n_a=3$
$n_5=4*n_{4a}+4*n_{4b}$
$n_{4b}=n_{3c}+2*n_{3b}+2*n_{3a}$
$n_{4a}=n_{3c}+2*n_{3b}$
$=>$
$n_5=8*n_{3a}+16*n_{3b}+8*n_{3c}$
$n_{3c}=4*n_{2b}+4*n_{2a}$
$n_{3b}=n_{2c}+2*n_{2b}+2*n_{2a}$
$n_{3a}=n_{2c}+2*n_{2b}$
$=>$
$n_5=48*n_{2a}+80*n_{2b}+24*n_{2c}$
$n_{2c}=4*n_{b}+4*n_{a}$
$n_{2b}=n_{c}+2*n_{b}+2*n_{a}$
$n_{2a}=n_{c}+2*n_{b}$
$=>$
$n_5=256*n_{a}+352*n_{b}+128*n_{c}=256*3+352*5+128*8=3552$

Non ci sono troppo lontano, dai...

[anto_zoolander]

@kobe

puoi considerare questo. Chiami le caselle di vertice $V_n$, le caselle di lato $L_n$ e la centrale $X_n$

ora è ovvio che

$X_n=4L_(n-1)+4V_(n-1)$

Puoi muovere dal centro in quattro modi verso le caselle di lato e puoi muovere in quattro modi verso i vertici.
Infatti i passi lunghi $n$ muovendo dal centro, sono tanti quanto la somma dei percorsi lunghi $n-1$ partendo da uno dei vertici più quelli di $n-1$ partendo da un lato.

Facendo i discorsi analoghi per la casella di vertice e quella di lato:
partendo da un vertice, hai due modi per andare in una casella di lato e un modo per andare nella casella di centro, da cui si ricava

$V_n=2L_(n-1)+X_n$

partendo da un lato, hai due modi per andare in una casella di vertice, due per andare in una casella di lato e uno solo per andare nella casella di centro, da cui si ricava

$L_n=2V_(n-1)+2L_(n-1)+X_(n-1)$

ora basta trovare le condizioni iniziali $X_1=8,L_1=5,V_1=3$

${(X_n=4L_(n-1)+4V_(n-1)),(V_n=2L_(n-1)+X_n),(L_n=2V_(n-1)+2L_(n-1)+X_(n-1)):}$ e ${(X_1=8),(L_1=5),(V_1=3):}$

[anto_zoolander]

rilancio:

tutto uguale a prima, soltanto bisogna contare i percorsi lunghi sei passi che terminano riportando il Re al centro della tabella.

[kobeilprofeta]

33920

?

[anto_zoolander]

Perché questi numeroni

Sono meno di quelli precedenti.

[kobeilprofeta]

uffa

ci riprovo

[kobeilprofeta]

"anto_zoolander":Perché questi numeroni

Sono meno di quelli precedenti.

stesso errore che ho fatto col cavallo, sono

3200

[Pachisi]

Per il rilancio:

Con $A_n$ indico i percorsi di $n$ mosse che terminano al centro, con $B_n$ indico i percorsi di $n$ mosse che non terminano al centro. Allora, $A_6=B_5=3840-A_5=3840-B_4=3840-(784-A_4)=3056+A_4=3056+B_3=3056+(168-A_3)=3224-A_3=3200$.