sortite casuali

[Venux]

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?

[Dudin]

Non ne sono sicuro al 100%

Testo nascosto:

[tex]\frac{2^{25} - 1} {2^{27} }[/tex]

Modifica correzione

[Venux]

Non ne sono sicuro al 100%

Testo nascosto:

[tex]\frac{2^{25} - 1} {2^{27} }[/tex]

Modifica correzione

giusto, come lo hai fatto?

[Dudin]

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

[mr96]

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.

[Davide12345]

Dove posso guardarmi la teoria sul root of unity filter?

[Lasker]

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)$).