OliForum Matematico

Ad un torneo di scacchi ad eliminazione diretta partecipano n concorrenti.
<BR>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?

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...
<BR>
<BR>altro problema: stesso testo del precedente con l\'aggiunta gli iscritti sono 2^n, e chi perde va a casa...
<BR>
<BR>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<BR><BR>[ Questo Messaggio è stato Modificato da: psion_metacreativo il 07-02-2004 19:03 ]

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

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....
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>nel primo caso, mi spieghi come vengono fatti gli accoppiamenti se n non è una potenza di 2?
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>non è dato di saperlo...

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

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

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

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

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

Se le partite terminano con la patta?
<BR>
<BR>Ciao.

scelgono il vincitore con una moneta...

in effetti per n dispari l\'ultima relazione di ricorrenza non vale, dovrebbe essere sostituita da qualcosa tipo
<BR>
<BR>P(n)=P(n-1)/n + (n-2)/n*[1/(n-2) + (n-3)/(n-2)*1/2*1/2*P(n-2)]
<BR>
<BR>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

HINT
<BR>
<BR><font color=white>
<BR>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:
<BR>
<BR>1/2^(n-1) = 1/(n/2) = 2/n .... guarda caso strano, è una coincidenza?..
<BR>
<BR> <IMG SRC="images/forum/icons/icon_biggrin.gif"> <IMG SRC="images/forum/icons/icon_wink.gif"> <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR><font>

propongo la soluzione o volete ancora tempo?

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
<BR>
<BR>Soluzione
<BR>
<BR><font color=white>
<BR>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)
<BR>
<BR>il numero di partite programmabile tra 2 giocatori in n iscrizioni sono (n 2) (coefficente binomiale di n e 2)
<BR>
<BR>quindi p= (n-1)/(n 2)= (n-1)/( n!/2*(n-2)!)= 2*(n-1)/n*(n-1) = 2/n
<BR>
<BR>nel caso in cui n=2^n viene proprio la probabilità calcolata da talpuz:
<BR>1/2^(n-1)
<BR><font>