sortite casuali

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

sortite casuali

Messaggioda Venux » 18/10/2017, 14:57

Durante l’assedio di Gerusalemme ogni giorno gli arabi tentavano una sortita da una delle
quattro diverse porte della città, situate nei quattro punti cardinali. Il primo giorno di assedio usarono la porta a Nord, e dal
secondo giorno adottarono uno stratagemma particolare per disorientare l’esercito di Goffredo di Buglione: all’alba tiravano
una moneta, e se fosse uscita testa sarebbero usciti dalla stessa porta del giorno precedente, altrimenti da quella successiva
in senso antiorario. (la successione è quindi Nord-Ovest-Sud-Est).
Qual è la probabilità che il 52-esimo giorno di assedio gli arabi prendano la porta a Nord?
Ultima modifica di Venux il 18/10/2017, 16:18, modificato 1 volta in totale.
Venux
 
Messaggi: 5
Iscritto il: 15/03/2017, 12:44

Re: sortite casuali

Messaggioda Dudin » 18/10/2017, 15:41

Non ne sono sicuro al 100%
Testo nascosto:
[tex]\frac{2^{25} - 1} {2^{27} }[/tex]


Modifica correzione
Dudin
 
Messaggi: 112
Iscritto il: 15/02/2017, 14:13

Re: sortite casuali

Messaggioda Venux » 18/10/2017, 16:18

Dudin ha scritto:Non ne sono sicuro al 100%
Testo nascosto:
[tex]\frac{2^{25} - 1} {2^{27} }[/tex]


Modifica correzione


giusto, come lo hai fatto?
Venux
 
Messaggi: 5
Iscritto il: 15/03/2017, 12:44

Re: sortite casuali

Messaggioda Dudin » 18/10/2017, 18:03

Soluzione:

Testo nascosto:
Fondamentalmente ho utilizzato un approccio ricorsivo:
Nx = N(x-1) + E(x-1)
(I percorsi che arrivano a nord alla x-esima mossa sono quelli che arrivano a nord alla (x-1)-esima mossa + quelli che arrivano ad est alla (x-1)-esima mossa)
Ox = O(x-1) + N(x-1)
Sx = S(x-1) + O(x-1)
Ex = E(x-1) + S(x-1)
E la somma Px raddoppiava ad ogni mossa cioè Px = 2P(x-1)
Da qui non sapendo come trovare una formula chiusa ho visto come varia la probabilità nel tempo...
è dietro c'è uno schema che si ripete ogni 8 mosse (2^n-1)/(2^(n+2) poi (2^n)/(2^n) oppure (2^n+1)(2^(n+2))
alla 52 esima mossa era della forma (2^n-1)/(2^(n+2) e ho trovato l'esponente sempre vedendo come cresceva la probabilità

probabilmente c'è una soluzione migliore
Dudin
 
Messaggi: 112
Iscritto il: 15/02/2017, 14:13

Re: sortite casuali

Messaggioda mr96 » 19/10/2017, 8:48

Si può fare un po' più velocemente così
Testo nascosto:
Considero il polinomio [tex]p(x)=(1+x)^{52}[/tex] (che sarebbe la funzione generatrice della moneta), la probabilità cercata è la probabilità che ci sia un numero multiplo di 4 di teste in 52 lanci, quindi mi basta cercare la somma dei coefficienti multipli di 4 del polinomio. Per farlo uso il root of unity filter, che mi dice che sono [tex]\frac{p(1)+p(\omega)+p(\omega^2)+p(\omega^3)}{4}[/tex] con $\omega$ radice quarta dell'unità. Facendo i conti viene $\frac{2^{52}-2^{27}}{4}$ che diviso poi per $2^{52}$ ci porta al risultato.
mr96
 
Messaggi: 1398
Iscritto il: 11/02/2014, 20:37

Re: sortite casuali

Messaggioda Davide12345 » 09/11/2017, 22:09

Dove posso guardarmi la teoria sul root of unity filter?
Davide12345
 
Messaggi: 14
Iscritto il: 17/02/2016, 17:45

Re: sortite casuali

Messaggioda Lasker » 10/11/2017, 8:22

Non c'è teoria, è solo una formuletta facile da dimostrare se sai dei fatterelli base sui numeri complessi. A me l'hanno introdotto facendo in successione i tre problemi
  • Quant'è la somma dei coefficienti di un polinomio $p(x)$?
  • Quant'è la somma dei coefficienti di grado pari di un polinomio $p(x)$?
  • Quant'è la somma dei coefficienti di grado multiplo di $3$ di un polinomio $p(x)$?
Se vuoi provare a farli sono esercizi istruttivi e non dimenticherai più la formula dopo averli dimostrati una volta (probabilmente il primo sai già che la risposta che voglio sentire è $p(1)$).
Cur enim scribere tre numeri quando se ne abbisogna di due? Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani.

PRIMA FILA TUTTI SBIRRI!

#FREELEPORI
Lasker
 
Messaggi: 781
Iscritto il: 17/03/2013, 16:00


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti