Combinatoria ricorsiva

Categoria:

Calcolo combinatorio

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 3×3 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, e quindi si potrebbe ripensare “su base 5 mosse” in quanto la 5° è obbligata. Però il fatto è che questo funziona solo se il re si trova in una casella perimetrale alla 5° mossa, se si trova al centro no… Quindi credo che bisogna trovare un modo per calcolare tutti i percorsi che alla 5° mossa non si trovano al centro ma non so come fare!!
Ringrazio in anticipo chi mi aiuterà!!

RISOLTO

Marked as spam

Pubblicato da Francesco Dresti (Domande: 1, Risposte: 1)

Domandato 03/03/2022 16:59

176 viste

▲

▼

Quesito molto interessante, non proprio banale. Ma con un po' di tentativi forse lo si riesce a risolvere. Alla peggio chiederemo una mano al prof. Computer. Ma prima di tutto un dubbio. La prima mossa può essere fatta in una qualunque delle 8 caselle perimetrali. Ma 4 sono d'angolo, e 4 sono di bordo. Vanno considerate come 8 mosse distinte o le possiamo considerare 2 mosse, a cui arrivare alle altre per simmetria?

(Claudio a 03/03/2022 18:47)

▲

▼

Io ho distinto due tipi di caselle: quelle di lato e quelle di vertice. Non so se si può effettivamente ragionare per simmetria (credo di sì comunque) ma non so a cosa può servire...

(Francesco Dresti a 04/03/2022 15:07)

▲

▼

Beh, ragionare per simmetria abbassa i numeri. Pensa alla prima mossa. Quante sono le prime mosse possibili? 2 o 8? Questo è un vincolo che devi porre tu, per permetterci di interpretare il problema come tu ce l'hai in testa.

(Claudio a 04/03/2022 17:58)

▲

▼

Si, hai ragione. Io non ci avevo pensato comunque credo che possa andare bene anche perché la scacchiera si può ruotare e quindi abbiamo 4 situazioni uguali. Ovviamente tutti i metodi che sono veri vanno bene. Ora però rimane il problema di capire come si riesce a dimostrare…

(Francesco Dresti a 04/03/2022 18:46)

▲

▼

Ho provato a risolverlo ma mi sembra che non serva a molto ragionare per simmetria in questo problema. Forse però sono io che mi sono fissato su un tipo di risoluzione e non riesco a trovarne altre... Se qualcuno ha qualche idea se vuole scriva qui. Grazie

(Francesco Dresti a 06/03/2022 00:27)

Risposte (1)

▲

▼

✔

Risposta privata

Alla fine ho preferito fare un conteggio senza considerare le simmetrie di partenza.

Si parte dalla casella centrale (indicata con la lettera C), per cui la prima mossa può essere fatta in uno delle 4 caselle d'angolo (indicate con la lettera A) o in una delle 4 caselle ai lati (indicate con la lettera L).

Se il re si trova su una casella A, la mossa successiva può essere o verso le 2 L adiacenti o verso C.

Se il re si trova su una casella L, la mossa successiva può essere o verso le 2 A adiacenti o verso C.

Indico con un "x2" o un "x4" il fatto che quel percorso va moltiplicato per il fattore riportato, proprio per indicare che simmetria di spostarsi su caselle dello stesso tipo.

Quindi i percorsi che portano alla sesta mossa nella casella C (ovvero alla quinta mossa in una casella A o L) e che partono con la prima mossa in una casella A sono:

Ax4 - Lx2 - Ax2 - Lx2 - Ax2 - Cx1 : 64 percorsi

Ax4 - Lx2 - Ax2 - Cx1 - Ax4 - Cx1 : 64 percorsi

Ax4 - Lx2 - Ax2 - Cx1 - Lx4 - Cx1 : 64 percorsi

Ax4 - Lx2 - Cx1 - Ax4 - Lx2 - Cx1 : 64 percorsi

Ax4 - Lx2 - Cx1 - Lx4 - Ax2 - Cx1 : 64 percorsi

Ax4 - Cx1 - Ax4 - Lx2 - Ax2 - Cx1 : 64 percorsi

Ax4 - Cx1 - Ax4 - Cx1 - Ax4 - Cx1 : 64 percorsi

Ax4 - Cx1 - Ax4 - Cx1 - Lx4 - Cx1 : 64 percorsi

Ax4 - Cx1 - Lx4 - Ax2 - Lx2 - Cx1 : 64 percorsi

Ax4 - Cx1 - Lx4 - Cx1 - Ax4 - Cx1 : 64 percorsi

Ax4 - Cx1 - Lx4 - Cx1 - Lx4 - Cx1 : 64 percorsi

Sarebbe interessate dimostrare questa costanza che, dato una qualunque sequenza tipo, il totale dei percorsi è 64.

In totale abbiamo 704 percorsi.

A questi dobbiamo aggiungere altrettanti percorsi aggiungendo le situazioni la cui prima mossa è verso una casella L.

Totale 1408 percorsi.

Se vogliamo togliere le simmetrie della prima mossa è sufficiente dividere per 4:

1408: 4 = 352 percorsi

Spero di essere stato chiaro e utile.

Marked as spam

Pubblicato da Claudio (Domande: 82, Risposte: 329)

Risposto 06/03/2022 17:10

▲

▼

Salve, sto scrivendo con questo account perché non riesco a entrare da quello vecchio. Ho letto la risposta ma ho notato che il risultato che ha dato non corrisponde a quello che dovrebbe essere (3200). Il problema credo che risieda nel fatto che se il re si trova in una casella L questo può andare nelle 2A adiacenti, in C ma anche nelle altre 2L… Il processo sembra poi un po’ lungo, però forse è solo un impressione e non ce ne sono di più brevi. Questa sera in caso provo a farlo correggendo questa cosa e le faccio sapere

( a 06/03/2022 17:34)

▲

▼

Oh cavolo! E' vero!!! Ho saltato un bel po' di casi. Ma spero almeno di averti tracciato una rotta!

(Claudio a 07/03/2022 16:26)

▲

▼

Si, grazie mille!!

(Francesco Dresti a 07/03/2022 18:35)

« Torna alla pagina precedente