44. troppe rotonde...

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

44. troppe rotonde...

Messaggio da nassus95 »

il problema non è difficile ma spero che il testo sia chiaro

Ho $n$ macchine posizionate sui vertici di un $n-agono$ regolare (inscritto in una circonferenza di raggio trascurabile) con i vertici numerati da $1$ a $n$. Dal centro dell' $n-agono$ partono $n$ strade rettilinee che incontrano i vertici dell' $n-agono$ e proseguono radialmente. Ogni strada prende il nome del vertice che incontra. Sappiamo inoltre che ci sono $k$ "rotonde" concentriche (con lo stesso centro dell' $n-agono$) con raggi via via crescenti.
A questo punto tutte le macchine entrano nella prima rotonda dalla strada su cui si trovano inizialmente e, una volta entrate, iniziano a girare perdendo l'orientamento e dimenticandosi così da che strada sono arrivate. Tuttavia vogliono proseguire il loro percorso per superare tutte le rotonde (ovvero devono entrare in ogni rotonda per poi proseguire a quella successiva fino ad oltrepassare la $k-esima$ ) e quindi imboccano una strada a caso che le condurrà alla rotonda seguente. L'unica cosa che sanno è che due macchine distinte non possono uscire da una rotonda per una stessa strada.
Arrivano così alla seconda rotonda ed iniziano a girare... (tutto si ripete come prima)
Continuano in questo modo fino a superare la $k-esima$ rotonda.

Qual è la probabilità $p$ che tutte le macchine arrivino in fondo (ovvero superino la $k-esima$ rotonda) entrando in ogni rotonda da una strada e uscendone da un'altra?
Calcolare $\lim_{k \to \infty} {k(p^{- \frac{1}{k^2}} -1 )} $
Testo nascosto:
hint
Qual è la probabilità che tutte le macchine entrino in una rotonda da una strada e ne escano da un'altra?
Qual è la probabilità che arrivino in fondo continuando in questo modo?
Qual è una buona approssimazione di $p$ per $n$ molto grande?
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 44. troppe rotonde...

Messaggio da Gottinger95 »

Mi pare che \(p\) sia
Testo nascosto:
\[ \left (\sum_{i=1}^n \frac{(-1)^{i+1} }{i!} \right )^k \]
Infatti, possiamo rappresentare ognuna delle \(k\) rotonde con un \(n\)-upla, e ogni entrata in una rotonda è una permutazione degli \(n\) elementi. La probabilità che cerchiamo è che nessuna di queste permutazioni sia una dismutazione; visto che il rapporto dismutazioni / permutazioni è
\[t = \sum_{i=1}^n \frac{(-1)^{i+1} }{i!}\]
La probabilità che questo succeda \(k\) volte è proprio quella sopra. Dunque il limite è
\[ \lim_{ k \to \infty } k\left [ \left ( \frac{1}{t} \right)^{1/k} -1 \right ] \]
Sostituendo \(x=1/k, s=1/t\) abbiamo
\[ \lim_{x \to 0} \frac{ s^x-1}{x} = \lim_{x \to 0} s^x \ln s = \ln s \]
Per de l'hopital. Tra l'altro per \(n \to \infty\) si ha che \(s \to e\), perciò quel limite va a 1. Spero di non aver preso cantonate!
Ah, per i più fighi che lo vogliono in termini di \(n\) si può pure scrivere \( \displaystyle \ln \frac{n!}{!n} \)
Ultima modifica di Gottinger95 il 06 mar 2014, 19:16, modificato 1 volta in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 44. troppe rotonde...

Messaggio da matpro98 »

Spero di non dire io una sciocchezza, ma la probabilità non è (1-t)^k ?
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 44. troppe rotonde...

Messaggio da Gottinger95 »

\(t\) è la probablità che non vada nella stessa strada da cui è entrato, \(1-t\) che vada nella stessa! ( prova con \ ( e \ ) senza spazi per le formule)

Dismutazione at http://it.wikipedia.org/wiki/Dismutazione_(matematica)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 44. troppe rotonde...

Messaggio da matpro98 »

Grazie per le formule ;)
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 44. troppe rotonde...

Messaggio da nassus95 »

Testo nascosto:
Gottinger95 ha scritto:
La probabilità che cerchiamo è che nessuna di queste permutazioni sia una dismutazione
sicuro?
Testo nascosto:
Gottinger95 ha scritto: il rapporto dismutazioni / permutazioni è
\[\sum_{i=1}^n \frac{(-1)^{i+1} }{i!}\]
quello che hai scritto è il rapporto tra le permutazioni meno le dismutazioni e le permutazioni ( $\frac {n!-!n}{n!} )$
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 44. troppe rotonde...

Messaggio da nassus95 »

Testo nascosto:
matpro98 ha scritto:Spero di non dire io una sciocchezza, ma la probabilità non è $(1-t)^k$ ?
yes
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 44. troppe rotonde...

Messaggio da Gottinger95 »

Ok ho flesciato il rapporto dismutazioni / permutazioni !!
Si, cerchiamo la configurazione in cui non ci sia nessuna dismutazione; il limite rimane \( \displaystyle \ln \frac{n!}{!n} \)
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 44. troppe rotonde...

Messaggio da nassus95 »

Gottinger95 ha scritto: cerchiamo la configurazione in cui non ci sia nessuna dismutazione
Ma perché?????? Semmai il contrario
il limite rimane \( \displaystyle \ln \frac{n!}{!n} \)
Ok
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 44. troppe rotonde...

Messaggio da Gottinger95 »

Intendevo nessun PUNTO FISSO*, quindi tutte dismutazioni! Sono proprio dislessico, scusa
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 44. troppe rotonde...

Messaggio da nassus95 »

Ok perfetto

Vai pure :)
Rispondi