scacchiera 8x8

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

scacchiera 8x8

Messaggioda tartaglia_2017 » 10/03/2017, 21:08

ciao a tutti, vorrei che qualcuno mi da una mano con questo esercizio di calcolo combinatorio:
es. una pulce si trova sulla casella in basso a sinistra di una scacchiera standard 8x8 e deve andare alla casella diagonalmente opposta, effettuando 16 salti tra caselle contigue( cioè aventi un lato in comune). quanti sono i diversi percorsi che può fare?
grazie mille in anticipo.
tartaglia_2017
 
Messaggi: 2
Iscritto il: 10/03/2017, 20:58

Re: scacchiera 8x8

Messaggioda Luke99 » 10/03/2017, 21:46

Le mosse possibili sono 2 : o va in su oppure a destra chiama S la mossa su e D quella destra i possibili modi sono tutte le permutazioni della stringa SSSSSSSSDDDDDDDD cioé[tex]\binom{16}{8}[/tex]
Luke99
 
Messaggi: 161
Iscritto il: 22/03/2015, 20:44

Re: scacchiera 8x8

Messaggioda tartaglia_2017 » 12/03/2017, 17:36

ciao luke, scusa se ti ho risposto solo ora ma la risposta è 160160, quindi la tua è sbagliata......
tartaglia_2017
 
Messaggi: 2
Iscritto il: 10/03/2017, 20:58

Re: scacchiera 8x8

Messaggioda Luke99 » 12/03/2017, 18:01

Hai ragione, é perché ho considerato una scacchiera 9x9, ci riprovo più tardi con quella giusta hahah
Luke99
 
Messaggi: 161
Iscritto il: 22/03/2015, 20:44

Re: scacchiera 8x8

Messaggioda Salvador » 11/04/2017, 12:20

Sei sicuro che sia 160160? A me esce 180180...
Salvador
 
Messaggi: 266
Iscritto il: 26/11/2016, 11:55

Re: scacchiera 8x8

Messaggioda Salvador » 11/04/2017, 18:47

Ho fatto questi ragionamento...
Testo nascosto:
Per poter arrivare alla casella finale la pulce deve compiere almeno 7 salti a destra e 7 in alto. Inoltre non può compiere un ulteriore salto a destra o in alto senza compiere un altro in direzione opposta: detto S un salto a sinistra, D uno a destra, A uno in alto e B uno in basso, si possono avere le due seguenti configurazioni: 8A+1B+7D oppure 8D+1S+7A.
Ovviamente né il primo né l'ultimo salto possono essere a sinistra o in basso. Consideriamo la prima configurazione: vi sono 4 possibilità:
- il primo e l'ultimo salto sono entrambi verso destra: ciò significa che dei restanti 14 salti 8 sono in alto, 1 in basso e 5 a destra, per i quali si hanno $\dfrac{14!}{8!5!1!}=18018$ percorsi possibili;
- il primo salto è a destra e il secondo in alto o viceversa oppure il primo e il secondo sono entrambi verso l'alto: in ogni caso vi sono $\dfrac{14!}{7!6!1!}=24024$ possibilità, e in totale 3*24024=72072 possibilità
Vi sono dunque in totale 18018+72072=90090 possibilità.
La seconda configurazione è "simmetrica" alla prima, per cui ripetendo lo stesso ragionamento si ottengono altri 90090 percorsi.
In totale vi sono dunque 180180 percorsi.

C'è qualche errore?
Salvador
 
Messaggi: 266
Iscritto il: 26/11/2016, 11:55

Re: scacchiera 8x8

Messaggioda teodella99 » 12/04/2017, 13:14

Devi stare attento che non si esca mai dalla scacchiera
teodella99
 
Messaggi: 11
Iscritto il: 23/02/2017, 18:20

Re: scacchiera 8x8

Messaggioda Gizeta » 05/12/2017, 15:46

Confermo il risultato di Salvador.
Per hintare in maniera non eccessivamente rivelatoria posso dire che il risultato può essere scritto nella forma

[tex]\displaystyle \boxed{4 \sum_{i=0}^7{\left ( (14-i)\binom{13-i}{6} \right)}}[/tex]

dove il fattore [tex]4[/tex] salta fuori da un'osservazione sulle configurazioni.
Su richiesta posso dare indicazioni più precise.

---------------

Hint configurazione

Testo nascosto:
Immagine
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Re: scacchiera 8x8

Messaggioda Dudin » 05/12/2017, 17:14

Nope fa 160160
Dudin
 
Messaggi: 127
Iscritto il: 15/02/2017, 14:13

Re: scacchiera 8x8

Messaggioda mr96 » 05/12/2017, 19:48

Testo nascosto:
[tex]2\left(\frac{16!}{7!\cdot 8!}-\frac{2\cdot 16!}{9!\cdot 7!}\right)[/tex] dove il primo termine sono i percorsi totali del tipo 8 passi a destra, uno a sinistra, e 7 in alto, mentre il secondo termine sono i due casi in cui esco dalla tabella (facendo uno step a sinistra prima del primo a destra o facendo tutti quelli a destra prima di quello a sinistra). Il 2 davanti è per simmetria con l'altro caso (8 alto, 1 basso, 7 destra)
mr96
 
Messaggi: 1455
Iscritto il: 11/02/2014, 20:37


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti