Numero dei percorsi del Paroliere
Non so se conoscete il paroliere, in pratica si tratta di individuare in mezzo alle sequenze di lettere ammissibili delle parole in italiano o nella lingua di riferimento.
Volevo sapere quante percorsi si possono formare da una scacchiera 4x4 come questa
I percorsi si possono formare partendo da una qualsiasi casella spostandosi in quelle adiacenti (in orizzontale verticale o in diagonale) senza ripassare mai sulla stessa casella. La lunghezza minima di un percorso è di 2 passi.
Ad esempio LO, LABI, LOD, LODG, LODE, LODA sono percorsi ammissibili, LODLO no, perché passa due volte sulla stessa casella.
Ecco... La domanda è: quanti percorsi (di almeno due passi che non ripassino sulla stessa casella) si possono formare?
Volevo sapere quante percorsi si possono formare da una scacchiera 4x4 come questa
I percorsi si possono formare partendo da una qualsiasi casella spostandosi in quelle adiacenti (in orizzontale verticale o in diagonale) senza ripassare mai sulla stessa casella. La lunghezza minima di un percorso è di 2 passi.
Ad esempio LO, LABI, LOD, LODG, LODE, LODA sono percorsi ammissibili, LODLO no, perché passa due volte sulla stessa casella.
Ecco... La domanda è: quanti percorsi (di almeno due passi che non ripassino sulla stessa casella) si possono formare?
Risposte
Non è facile. Iniziamo così:
Distinguo
S: spigoli (quelli che hanno 5 caselle adiacenti)
V: vertici (3 caselle adiacenti)
C: centrali (8 caselle adiacenti)
Consideriamo le parole di lunghezza 2.
Si puó partire da una delle 16 caselle, considerando che ci sono 8 S, 4 V e 4 C, le parole sono:
$8*5+4*3+4*9=88$
Ora, abbiamo detto che da una V partono 3 parole, da una S 5 parole e da una C 9 parole.
Puoi verificare che il numero di volte in cui una casella è la prima lettera (=quante parole partono) è uguale anche al numero in cui quella casella è la seconda lettera. Da cui:
Parole di 3 lettere:
$(9*4+3*4+8*5)*(8*4+2*4+4*8)=6336$ ho scritto la stessa formula di prima ma con un fattore di ogni moltiplicazione diminuito di 1 perchè non si puó ritornare sulla stessa casella da cui proveniva la parola.
Credo che per le parole di lunghezza superiore si possa fare un ragionamento analogo.
Distinguo
S: spigoli (quelli che hanno 5 caselle adiacenti)
V: vertici (3 caselle adiacenti)
C: centrali (8 caselle adiacenti)
Consideriamo le parole di lunghezza 2.
Si puó partire da una delle 16 caselle, considerando che ci sono 8 S, 4 V e 4 C, le parole sono:
$8*5+4*3+4*9=88$
Ora, abbiamo detto che da una V partono 3 parole, da una S 5 parole e da una C 9 parole.
Puoi verificare che il numero di volte in cui una casella è la prima lettera (=quante parole partono) è uguale anche al numero in cui quella casella è la seconda lettera. Da cui:
Parole di 3 lettere:
$(9*4+3*4+8*5)*(8*4+2*4+4*8)=6336$ ho scritto la stessa formula di prima ma con un fattore di ogni moltiplicazione diminuito di 1 perchè non si puó ritornare sulla stessa casella da cui proveniva la parola.
Credo che per le parole di lunghezza superiore si possa fare un ragionamento analogo.
Non ho ben capito ancora, per i percorsi di lunghezza 2 il tuo calcolo è corretto, ma come lo si estende?
I percorsi di lunghezza 16 ad esempio, quanti ce ne sono? (Ne esistono di lunghezza 16). Tieni presente che i percorsi non devono ripassare sulla stessa casella (che non è necessariamente solo quella di partenza). In cosa consiste il ragionamento analogo?
I percorsi di lunghezza 16 ad esempio, quanti ce ne sono? (Ne esistono di lunghezza 16). Tieni presente che i percorsi non devono ripassare sulla stessa casella (che non è necessariamente solo quella di partenza). In cosa consiste il ragionamento analogo?
"kobeilprofeta":
Si puó partire da una delle 16 caselle, considerando che ci sono 8 S, 4 V e 4 C, le parole sono:
$8*5+4*3+4*9=88$
Forse volevi dire
$8*5+4*3+4*7=80$
Poi neanche io capisco come estendere il ragionamento a percorsi più lunghi.
Io non sto riuscendo a trovare un modo furbo e "umanamente accettabile" di contare tutti i possibili percorsi, però se ti interessa il risultato ti posso dire (quasi) con certezza che esso è:
12029624
Risultato ottenuto con l'ausilio del computer...
Per la verità io non ho osservato se i numeri erano corretti, ho seguito solo il ragionamento di kobeilprofeta per calcolare i percorsi di lunghezza 2 e mi sembrava corretto. A me sembra che la formula giusta sia questa per i percorsi di lunghezza 2
\( 8*5+4*3+4*8=40+12+32=84\)
speramo bene che non mi sono imbrogliato pure io
Ho calcolato manualmente quelli di lunghezza 3 e mi trovo 408, chissà se è giusto, provate pure voi. Comunque non può venir fuori un numero così grande 6000 per i percorsi di lunghezza 3.
milizia96 cosa hai usato per calcolare il numero? Esiste qualche applicazione in rete?
Io ho cercato un po' prima di postare il messaggio, ma non ho trovato nulla.
\( 8*5+4*3+4*8=40+12+32=84\)
speramo bene che non mi sono imbrogliato pure io
Ho calcolato manualmente quelli di lunghezza 3 e mi trovo 408, chissà se è giusto, provate pure voi. Comunque non può venir fuori un numero così grande 6000 per i percorsi di lunghezza 3.
milizia96 cosa hai usato per calcolare il numero? Esiste qualche applicazione in rete?
Io ho cercato un po' prima di postare il messaggio, ma non ho trovato nulla.
No, mi sono creato da solo un programmino in C++ 
Hai ragione mi sono incasinato anch'io
"bub":
A me sembra che la formula giusta sia questa per i percorsi di lunghezza 2
\( 8*5+4*3+4*8=40+12+32=84\)
Hai ragione mi sono incasinato anch'io
Ci vorrebbe qualcun altro che sappia programmare velocemente come te milizia96 e lo calcoli, così vediamo se esce lo stesso numero. in rete questa informazione non l'ho trovata eppure è un giochino molto noto.
Ho adattato un vecchio programmino che avevo scritto per fare dei calcoli con dei grafi e mi trovo con te milizia96 ... 12029624. Qualcun altro ci ha provato? Vi trovate con noi?
Caspita ma non c'è un modo più semplice per calcolarli i percorsi?
.
Comunque grazie
... 12029624. Qualcun altro ci ha provato? Vi trovate con noi?Caspita ma non c'è un modo più semplice per calcolarli i percorsi?
.Comunque grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo