Combinatoria: Altro es. delle GaS

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Combinatoria: Altro es. delle GaS

Messaggio da nico lol »

Ciao ragazzi, sono sempre io, il tizio che propone un sacco di quesiti sulle GaS (perché mi piacciono un sacco)
Oggi, vorrei proporvi questo problema (che non so proprio come approcciare a differenza degli altri) ma vabbè.
Qualcuno può darmi qualche "hint"?Grazie in anticipo :D
Luke Randomwalker sta cercando un posto sicuro dove nascondersi, e per farlo viaggia in incognito
a bordo di navi mercantili. Le navi scelte da Luke seguono rotte che collegano tra loro n pianeti. Tra
di essi vi sono: Coruscantor, dove Luke si trova all’inizio; Banahch-Torsk, un ameno pianeta doppio
dove Luke si ferma immediatamente (se ci passa); Taodana, sede del covo di Maz Karamata, dove
ci sono così tante spie del Prim’Ordine che è certo che qualcuno lo riconosca e lo uccida. Da ogni
pianeta (esclusi Taodana e Banahch-Torsk) partono rotte unidirezionali verso esattamente altri due
pianeti, e da al massimo uno di questi due esiste una successione di rotte che consente di tornare
al pianeta appena lasciato. Ogni volta che lascia un pianeta, Luke sceglie a caso tra le due rotte
possibili (con uguale probabilità) e si ferma solamente se arriva su Banahch-Torsk oppure se viene
ucciso su Taodana. Sapendo che la probabilità che arrivi sano e salvo su Banahch-Torsk è 1/2016,
quanto vale n come minimo?
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Combinatoria: Altro es. delle GaS

Messaggio da afullo »

Prova a partire dal fatto che, a parità di [tex]n[/tex], la probabilità che arrivi su Banahch-Torsk è più piccola tanto è più grande il numero di pianeti che hanno una delle due rotte in uscita verso Taodana. ;)
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Combinatoria: Altro es. delle GaS

Messaggio da nico lol »

Inoltre, credo (e spero) che affinchè n sia minimo allora per ogni pianeta esiste una successione di rotte tale che lo faccia tornare indietro, giusto?
Di conseguenza è come se disponessi al centro TAODANA e su una circonferenza gli (n-3) pianeti, (n-3) perché taodana è al centro, mentre coruscantor, e banana (non so come si scrive :D :lol: ) si trovano collegati da qualche parte sulla circonferenza giusto?
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Combinatoria: Altro es. delle GaS

Messaggio da afullo »

Potrebbe essere un buon punto di partenza: non troverei così scontato che la presenza di cicli per tutti minimizzi la probabilità, ma con la tua costruzione in effetti BT ha una sola rotta in entrata, e bisogna passare prima per tutti i pianeti in mezzo. Però 2016 non è una potenza di due, quindi qualcosa devi modificare. Magari osservare che 1/2016 si può scrivere come somma di reciproci di potenze di due, come 1/2048 + 1/(2048*64) + 1/(2048*64^2) + ... ?
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Combinatoria: Altro es. delle GaS

Messaggio da nico lol »

Si, praticamente mi ero reso conto che non riuscivo a scrivere quella roba come potenza di due.
Di conseguenza ho provato (a intuito, si vede che non sono molto allenato nel "captare" la soluzione) ho provato a scrivere 2016=32*(64-1), e cioé
1/2016=1/(32*64*(1-(1/64))). Quel 1/64 ricorda tanto la somma di una serie geometrica e quindi posso scrivere 1/2016 come una serie geometrica INFINITA di 1/64 e 2^11 che sarebbe 2048 al denominatore.
Mettendo a fattor comune 1/2048 si evince che per arrivare fino a BT è necessario passare ALMENO 10 pianeti (escludendo Crusandor e Banah, ovviamente non tenendo conto di Taodana).
Adesso, credo comunque che a questo punto sia necessario costruire qualche "configurazione" che mi dica se è necessario aggiungere altri pianeti ai 13 che ho considerato.
Grazie comunque dell'aiuto Afullo :D :D
Ahm un altra domanda, ma per sviluppare "l'occhio" è sempre necessario fare tanti esercizi e notare le cose? Ad esempio la questione della serie geometrica l'ho notato "ad intuito"... poi bho
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Combinatoria: Altro es. delle GaS

Messaggio da afullo »

Poiché [tex]\dfrac{1}{2016} = \dfrac{1}{2^{11}} + \dfrac{1}{2^{17}} + \dfrac{1}{2^{23}} + \ldots[/tex], puoi vederla come il poterci arrivare dopo 11 bivi, dopo 17, dopo 23..., contando come tali quelli in cui una delle due strade porta a Taodana. Puoi provare a costruire un ciclo interno, e ad agganciare altri pianeti come precedenti al ciclo (da Coruscantor li deve attraversare prima di entrare nel loop), visto che la prima possibilità buona è appunto dopo 11; attenzione solo che non ci sarà un pianeta collegato sia a BT che a Taodana, altrimenti il viaggio si fermerebbe comunque (mentre devi contemplare la possibilità di arrivarci in [tex]6k+5[/tex] bivi, per [tex]k[/tex] arbitrariamente alto), quindi quello collegato a BT è collegato anche ad un pianeta diverso, e non conta come bivio (non si può fallire in quel passaggio). Dovrebbe poter bastare realizzare il ciclo con un pianeta in più (7 anziché 6), pure se converrebbe aiutarsi con un disegno.

Sì, l'occhio si allena con la pratica. L'intuito fa anche molto, ma certi meccanismi sono ricorrenti, con l'allenamento viene via via più naturale riconoscerli...
nico lol
Messaggi: 31
Iscritto il: 15/03/2017, 21:59

Re: Combinatoria: Altro es. delle GaS

Messaggio da nico lol »

Ok, praticamente, 1/2^11+...+1/2^(6k+5), è come se rappresentasse la probabilità di svoltare dopo l'11 pianeta verso banah, oppure la probabilità di svoltare al 6k+5-esimo.
Quindi è come se sommassi i casi esattamente come si fa in combinatoria giusto?
Grazie davvero della disponibilità, finalmente qualcuno che mi spiega le cose Aahahah :D :D
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Combinatoria: Altro es. delle GaS

Messaggio da afullo »

Sono eventi disgiunti a coppie, perché se arrivi in esattamente m passi, non puoi arrivarci in esattamente n, se m è diverso da n; dunque la probabilità dell'unione è la somma delle singole probabilità. Figurati, siamo qui per questo... :mrgreen:
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Combinatoria: Altro es. delle GaS

Messaggio da ronny »

Scusa nico lol non ho ben chiaro il testo del problema:
- ci sono n pianeti collegati da rotte unidirezionali. Quindi tra A e B esiste solo una rotta da A a B oppure da B ad A?
- una successione di rotte che consente di tornare al pianate è una successione che evita BT e Taodana o potrebbe includerli?
- dai n pianeti ci sono quindi tante configurazioni di rotte possibili che le collegano. La probabilità di arrivare su BT è quella minima
tra tutte le possibili configurazioni?

Ciao
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Combinatoria: Altro es. delle GaS

Messaggio da afullo »

(i) sì.
(ii) esiste da "al massimo uno dei due", quindi direi che uno possa essere compreso, tutti e due no, altrimenti esisterebbe da entrambi.
(iii) no, si deve cercare n minimo perché 1/2016 sia un valore possibile, cioè verificato per una configurazione.
Rispondi