scacchi e probabilità

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

Ad un torneo di scacchi ad eliminazione diretta partecipano n concorrenti.
 Supponendo che ogni giocatore abbia il 50% probabilità di vittoria, e i risultati degli incontri sono eventi indipendenti, qual\'è la probabilità che Andrea e Luca si affrontino?

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

P.S. è interessante notare che n potrebbe anche non essere multiplo di 2, perchè nel testo non si trova scritto che il calendario sarà equo e tutti i giocatori qualificati a un turno giocheranno lo stesso numero di partite...
 
 altro problema: stesso testo del precedente con l\'aggiunta gli iscritti sono 2^n, e chi perde va a casa...
 
 e già che ci siete stabilire in quale delle due formule del torneo scacchistico dei due problemi è più facile che i nostri 2 eroi si scontrino [ Questo Messaggio è stato Modificato da: psion_metacreativo il 07-02-2004 19:03 ]

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

per il secondo
 
 assumo che gli accoppiamenti per le prima partite siano casuali
 
 (se non è così specificalo)
 
 indico con P(n) la probabilità cercata
 
 focalizziamo l\'attenzione su Andrea: se Luca è il suo rivale alla prima partita siamo a posto, e questo succede con probabilità 1/(2n-1) se questo non succede, per affronatrsi entrambi devono vincere le rispettive partite, e a questo punto ricadiamo in P(n-1)
 
 quindi
 
 P(n)=1/(2n-1) + (2n-2)/(2n-1)*1/2*1/2*P(n-1)
 
 e per ora mi fermo qui (mettendo a posto la formula, un paio di prove su valori di n bassi e l\'induzione dovrebbero bastare)
 
 nel primo caso, mi spieghi come vengono fatti gli accoppiamenti se n non è una potenza di 2? [ Questo Messaggio è stato Modificato da: talpuz il 07-02-2004 19:07 ]

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

ok 6 vicino alla soluzione del secondo e mi pare corretta la strada che vuoi perseguire anche se ce n\'è una + veloce e bellina che se la trovi capisci anche come affrontare il primo... in teoria è + facile il primo e poi passare al secondo ragionando in un certo modo....
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 nel primo caso, mi spieghi come vengono fatti gli accoppiamenti se n non è una potenza di 2?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 non è dato di saperlo...

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

e ti dirò di più, nel primo n potrebbe anche essere dispari....

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

qualche prova suggerisce che
 
 P(n)=1/2n-1
 
 e questo si dimostra facilmente per induzione utilizzando la relazione di ricorrenza trovata
 
 ah, non si può sapere...beh, adesso ci penso...

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 
 P(n)=1/2n-1
 
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 ok è giusto, se ragioni 1 secondo trovi che questo problema è un caso particolare del primo...
 
 caso particolare dove numero partecipanti, n, vale 2^n... e con questo smetto con gli aiuti... [ Questo Messaggio è stato Modificato da: psion_metacreativo il 07-02-2004 19:20 ]

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

boh, a me viene da ripetere il ragionamento di prima anche in questo caso..
 
 facciamo fare le loro prime due partite ai due: se sono accopiati, bon
 
 probabilità: 1/n-1 (ragionando come prima)
 
 altrimenti devono vincere, e ricadiamo in P(n-2)
 
 probabilità: (n-2)/(n-1)*1/2*1/2*P(n-2)
 
 quindi
 
 P(n)=1/(n-1) + (n-2)/(n-1)*1/2*1/2*P(n-2)
 
 ancora prove, ancora induzione e dovrebbe saltar fuori il tutto

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

mi sa che la tua strada stavolta ha parecchie curve ed è complicata cmq se ce la fai bravo... cmq esiste un modo molto semplice....

cosma2000 · Messaggio da **cosma2000** » 01 gen 1970, 01:33

Se le partite terminano con la patta?
 
 Ciao.

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

scelgono il vincitore con una moneta...

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

in effetti per n dispari l\'ultima relazione di ricorrenza non vale, dovrebbe essere sostituita da qualcosa tipo
 
 P(n)=P(n-1)/n + (n-2)/n*[1/(n-2) + (n-3)/(n-2)*1/2*1/2*P(n-2)]
 
 però stavolta non ne sono troppo sicuro, e comunque effettivamente questa strada sembra un po\' casinosa (anche perchè provando a computare P(n) per qualche valore basso di n non salta fuori qualcosa di buono)...bah

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

HINT
 
 
 come già scritto in precedenza il 2° problema è un caso particolari del primo dove n vale 2^n, quidni sostituendo questo nella Probabilità calcolata da Talpuz viene fuori:
 
 1/2^(n-1) = 1/(n/2) = 2/n .... guarda caso strano, è una coincidenza?..
 
 <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_wink.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

propongo la soluzione o volete ancora tempo?

psion_metacreativo · Messaggio da **psion_metacreativo** » 01 gen 1970, 01:33

Scrivo la soluzione in bianco perchè mi sembra un problema bellino e magari qualcuno vuol divertirsi a trovarla da solo o ne trova una diversa, inoltre non mi piace lasciare le cose in sospeso quindi ecco la
 
 Soluzione
 
 
 il numero di partite da giocare in un torneo a eliminazione diretta con n iscritti è n-1 (infatti ci deve essere una partita per ogni perdente)
 
 il numero di partite programmabile tra 2 giocatori in n iscrizioni sono (n 2) (coefficente binomiale di n e 2)
 
 quindi p= (n-1)/(n 2)= (n-1)/( n!/2*(n-2)!)= 2*(n-1)/n*(n-1) = 2/n
 
 nel caso in cui n=2^n viene proprio la probabilità calcolata da talpuz:
 1/2^(n-1)