Combinatoria ricorsiva - scacchiera

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Fα⟂⟂oriα!e
Messaggi: 2
Iscritto il: 21 giu 2021, 20:31

Combinatoria ricorsiva - scacchiera

Messaggio da Fα⟂⟂oriα!e »

Buonasera a tutti,
è da un po' che provo a risolvere questo problema di combinatoria ma proprio non riesco a venirne a capo...
In pratica abbiamo una scacchiera 3x3 e viene richiesto di calcolare i possibili percorsi di 6 mosse che un re, posizionato al centro di essa, può fare per ritornare al punto di partenza.
Ho ragionato inserendo più variabili e sapendo che, al 5° passo, se il re si trova in una casella perimetrale, può fare una e una sola mossa per ritornare al punto di partenza. Quindi il problema si potrebbe vedere con solo 5 mosse in quanto l'ultima è obbligata. Però non in tutti i casi, perché se alla 5° mossa il re si trova al centro, non si potrà trovare nello stesso punto il passo successivo. Quindi in qualche modo bisognerebbe togliere quelle che alla 5° mossa si trovano al centro, ma non saprei come fare...
Ringrazio in anticipo chi mi aiuterà!

Risultato:
Testo nascosto:
3200
Fα⟂⟂oriα!e
thomas.leihkauf
Messaggi: 3
Iscritto il: 04 giu 2022, 15:41

Re: Combinatoria ricorsiva - scacchiera

Messaggio da thomas.leihkauf »

ciao,
ti propongo una soluzione molto semplice e abbastanza veloce al problema.
Prima di tutto osserviamo che esistono tre tipi di casella nella scacchiera 3x3, infatti esiste la casella centrale che chiamiamo A, la casella laterale (non negli angoli) che chiamiamo B, e la casella negli angoli che chiamiamo C. Per capirci: [math].
Facciamo questa distinzione, perché possiamo osservare che per ovvie ragioni il numero di percorsi partendo da caselle dello stesso tipo per arrivare alla casella A è uguale, questo ci permette di semplificare moltissimo i calcoli. Per sfruttare questa proprietà possiamo ad ogni passo contare il numero di modi di arrivare in una casella di tipo A, il numero di modi di arrivare in una casella di tipo B, e il numero di modi di arrivare in una casella di tipo C.
Allora per cominciare osserviamo che dalla casella A si può andare in 4 modi su una casella B e in 4 modi su una casella C. Da una casella B si può andare in un solo modo su una casella A, in 2 modi su una casella B, e in 2 modi su una casella C. Infine da una casella C si può andare in un modo su una casella A, e in 2 modi su una casella B.
Ora, se chiamiamo [math] il numero di modi di arrivare nella casella A in n mosse (partendo ovviamente dalla casella A, come richiesto dal problema), [math] il numero di modi di arrivare nella casella b in n mosse, e uguale per [math] (sempre partendo da A), troviamo grazie ai dati del problema che:
[math]
Inoltre usando le regole scritte precedentemente sappiamo che:
[math]
Siccome sono solamente 6 passi, puoi molto velocemente trovare che [math]

Qui sotto scrivo i passaggi intermedi, anche se sono conti relativamente facili:
[math]

Spero di esserti stato utile!

Thomas Leihkauf
Rispondi