Scacchiera
MI sono imbattuto nel seguente esercizio, ma non riesco a risolverlo.
SI consideri una scacchiera con 64 caselle. Muovendosi di una casella alla volta e non in diagonale, in quanti modi diversi è possibile andare da un angolo all'angolo opposto col numero minimo di passi.
Ho provato ad esplorare i possibili percorsi, ma non riesco a "trovare ordine" nell'esplosione combinatoria.
E dire che sono un appassionato di scacchi
Qualcuno riesce ad aiutarmi?
SI consideri una scacchiera con 64 caselle. Muovendosi di una casella alla volta e non in diagonale, in quanti modi diversi è possibile andare da un angolo all'angolo opposto col numero minimo di passi.
Ho provato ad esplorare i possibili percorsi, ma non riesco a "trovare ordine" nell'esplosione combinatoria.
E dire che sono un appassionato di scacchi
Qualcuno riesce ad aiutarmi?
Risposte
Ciao,
prova a pensare a delle mosse di $2$ passi, soprattuto al caso che produca una $L$. Immagina che questa $L$ sia un puzzle, prova a vedere in quanti modi riesci ad incastrarlo nella scacchiera. Poi generalizza e vedi quando queste due mosse producono una $I$ e vedi quale dei due sia minimo. Direi che così potrebbe funzionare, dopo cmq provo a ragionarci meglio
prova a pensare a delle mosse di $2$ passi, soprattuto al caso che produca una $L$. Immagina che questa $L$ sia un puzzle, prova a vedere in quanti modi riesci ad incastrarlo nella scacchiera. Poi generalizza e vedi quando queste due mosse producono una $I$ e vedi quale dei due sia minimo. Direi che così potrebbe funzionare, dopo cmq provo a ragionarci meglio
Ciao,
supponi di dover partire dall'angolo in basso a sinistra per raggiungere quello in alto a destra.
siccome il numero di passi dev'essere minimo, è chiaro che ti puoi spostare ad ogni mossa solo verso destra o verso l'alto.
In particolare, devi fare $8$ mosse verso destra e $8$ mosse verso l'alto: basta calcolare quanti sono i percorsi di questo tipo.
supponi di dover partire dall'angolo in basso a sinistra per raggiungere quello in alto a destra.
siccome il numero di passi dev'essere minimo, è chiaro che ti puoi spostare ad ogni mossa solo verso destra o verso l'alto.
In particolare, devi fare $8$ mosse verso destra e $8$ mosse verso l'alto: basta calcolare quanti sono i percorsi di questo tipo.
ci siamo quasi
supponendo di partire dalla casella A1 e di dover raggiungere la casella H8, e di spostarmi prima tutto a destra e poi, raggiunta la casella H1, di spostarmi verso l'alto, ho fatto 14 mosse
questo è il percorso minimo, quindi devo calcolare tutti i possibili spostamenti di 14 mosse
implicitamente questo numero obbliga ogni spostamento ad essere rivolto verso destra o verso l'alto
detto questo, non so come continuare
supponendo di partire dalla casella A1 e di dover raggiungere la casella H8, e di spostarmi prima tutto a destra e poi, raggiunta la casella H1, di spostarmi verso l'alto, ho fatto 14 mosse
questo è il percorso minimo, quindi devo calcolare tutti i possibili spostamenti di 14 mosse
implicitamente questo numero obbliga ogni spostamento ad essere rivolto verso destra o verso l'alto
detto questo, non so come continuare
"milizia96":
In particolare, devi fare $8$ mosse verso destra e $8$ mosse verso l'alto: basta calcolare quanti sono i percorsi di questo tipo.
Perchè 8 mosse? Una mossa è l'arco che unisce una coppia di caselle, perciò son $7$ mosse ed $8$ caselle. basta mettersi d'accordo sull'unità di misura...
Il percorso più breve è sempre un insieme di $14$ mosse. Le combinazioni sono i sottoinsiemi di $14$ elementi da un insieme di $7*7=49$. Ora lascio te pensare a quale combinazioni, disposizione di calcolo combinatorio si parla (per intenderci combinazioni semplici...), ricorda che si parla di "percorsi diversi".
"hamming_burst":
Perchè 8 mosse? Una mossa è l'arco che unisce una coppia di caselle, perciò son 7 mosse ed 8 caselle.
Giusto! Mi sono lasciato prendere dalla fretta e ho scritto male.
"hamming_burst":
Le combinazioni sono i sottoinsiemi di $14$ elementi da un insieme di $7⋅7=49$.
Ora sono io che non capisco il tuo ragionamento.
Io direi che tutte le possibili soluzioni sono i sottoinsiemi di 7 elementi da un insieme di 14.
Cioè ci chiediamo: "in che modo le 7 mosse verso destra si possono distribuire insieme alle altre 7 che vanno verso l'alto?"
se non ho capito male le possibili mosse sono $sub_14,_7$
Esattamente!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo