OliForum Matematico

Una regione è composta da n città ciascuna unita alle altre da una strada.

Assegnando a ciascuna strada un senso unico a caso qual'è la probabilità che esista una città partendo dalla quale si riesca a tornare nella stessa.

Buon divertimento!

Parto con qualche considerazione elementare:

per n=1 il problema non ha senso

per n=2 qualunque sia il "verso" della strada che collega le due città non è possibile tornare alla città di partenza. Quindi la probabilità è 0.

per n=3, una volta scelto il "verso" della prima strada, le altre due devono essere consecutive, ovvero per ogni città vi deve essere una strada in entrata e una in uscita. Quindi la probabilità che esista un percorso per tornare alla città di partenza è $ (\frac{1}{2})^2=\frac{1}{4} $

per n>3 le cose sono molto più complesse....mi serve tempo!

Prima osservazione: Se non esiste un percorso chiuso, esiste una città in cui si può solo entrare.
Dimostrazione: (per assurdo) parto dalla città 1. Potrò andare in una città, chiamiamola 2. Da due posso ancora uscire, e andare in 3, e così via. Ma le città sono finite, quindi prima o poi andando così a caso tornerò in una città per cui sono già passato, chiamiamola K. Ma allora, uscito da K, posso tornare a K.

Ora il claim:
$ \displaystyle 1-p(n) = \frac{n!}{2^{n \choose 2}} $, dove p(n) è la probabilità che scegliendo a caso le direzioni con n città, esista una città in cui si può ritornare.

Dimostrazione (per induzione):
Date n città, il numero di grafi completi orientati (insomma di sensi unici) è dato da $ ~ 2^{n \choose 2} $, perchè per ogni coppia di vertici posso scegliere tra 2 direzioni.

Per n=3 è banale che il numero di grafi in cui da nessuna città, usciti, si può rientrare, è dato da 6 = 3!

Abbiamo n vertici. Se non esiste un percorso chiuso, esiste (e ovviamente è unico) una città in cui si può solo entrare, chiamiamola A. A posso sceglierlo in n modi. Per ogni scelta di A, voglio dimostrare che il numero di grafi senza percorsi chiusi è (n-1)!. Infatti, se nei restanti vertici non esiste un percorso chiuso (qui per ipotesi induttiva ci sono (n-1)! combinazioni), non esiste neanche un percorso chiuso che passa per A (perchè in A si può solo entrare). Quindi, con n vertici, il totale di situazioni senza percorsi chiusi è dato da n (scelte di A) * (n-1)! (possibilità per i restanti vertici) = n!

Carino! Bell'esercizio enomis

Suppongo che tra 2 qualsiasi città vi sia una strada con probabilità 0,5. Giusto?

Si Mind. Bella edriv!!

La soluzione che abbiamo spedito era una enomis old style (una paginetta e 4 step) però sta mattina sul pullman (mentre pensavo alle patate e zappe di edriv) ho trovato questa:

Lemma:
Se esiste un percorso chiuso allora esiste anche un percorso chiuso di lunghezza 3.
Nel percorso di lunghezza min (>3) considerando l'arco che connette due vertici distinti non adiacenti si trova facilmente un percorso più corto, assurdo.

Chiamo ordinamento di un'insieme una relazione in cui per a,b,c distinti valga:
se: a<b;b<c allora a<c

Ad ogni arco che esce da A e entra in B associo la relazione A>B.

Sse esiste un percorso chiuso allora avrò 3 vertici t.c.:
A>B,B>C,C>A ovvero la relazione definita non è un'ordinamento.

Il numero di ordinamenti di un'insieme di n elementi distinti è n! da cui facilmente il risultato ottenuto anche da edriv.