Torneo con [tex]2^n[/tex] squadre (facile)

[kalu]

$ 2^n $ squadre partecipano ad un torneo ad eliminazione diretta (per intenderci: il torneo si compone di $ n $ fasi $ F_1, F_2, ..., F_n $ ; ad ogni fase $ F_i $ partecipano $ 2^{n-i+1} $ squadre che si affrontano in $ 2^{n-i} $ partite). Qual è la probabilità che due squadre qualsiasi si affrontino durante il torneo? (Ovviamente i sorteggi per stabilire gli incontri del primo turno non si sono ancora fatti)

[LukasEta]

Ad ogni fase si risorteggiano gli incontri? Cioè....se $n$ squadre passano il primo turno, è già determinato chi affronterà chi nel secondo turno, oppure ogni turno prevede scontri casuali tra le squadre "sopravvissute"?

[staffo]

edit, ho sbagliato a leggere...

[kalu]

Ad ogni fase si risorteggiano gli incontri?

Beh no... una volta che si fanno i sorteggi, poi è già tutto stabilito. I tornei sono sempre così... hai presente la champions' league?
Comunque sinceramente non credo che la situazione cambi...

[Strangeloop]

Definisco la distanza tra due squadre come il numero di incontri che devono fare per incontrarsi (compreso il loro scontro). Ci sono $ 2^{n-1} $ squadre a distanza $ n $ e la probabilità che due squadre a questa distanza si incontrino è $ 2^{-2(n-1)} $ Allora scelta una squadra, calcolo la somma delle probabilità di prendere una seconda squadra a distanza $ n $ che si incontri con la prima, cioè $ \frac {1} {2^n-1}\sum_{n=0}^{N-1} 2^{n-2n}=\frac {1} {2^ {n-1}} $ usando la formula della somma di progressioni geometriche

[max tre]

Allora, ogni partita elimina una squadra e alla fine del torneo ne rimane solo una, quindi ci sono $ 2^-1 $ partite; ovvero le squadre scendono in campo $ 2(2^n-1) $ volte (in pratica, sommo il numero di partite giocate da tutte le squadre).
Allora in media ogni squadra gioca $ \frac{2(2^n-1)}{2^n}=\frac{2^n-1}{2^{n-1}} $ partite.
Ora, prendiamo una squadra A, questa può incontrare $ 2^n-1 $ diverse squadre, quindi incontra $ \frac{\frac{2^n-1}{2^{n-1}}}{2^n-1}=\frac{1}{2^{n-1}} $ delle altre squadre (intendo dire, il $ \frac{100}{2^{n-1}}\% $ delle altre squadre).
Quindi la probabilità che una squadra B sia tra queste squadre che incontrano la squadra A è $ \frac{1}{2^{n-1}} $.

[max tre]

hai presente la champions' league?

OT: A parte che è scritto sbagliato, hai scelto l'esempio sbagliato
Infatti c'è un sorteggio per i soli ottavi di finale e uno per quarti-semifinali-finale.
Diciamo come FA Cup e Carling Cup a partire dal turno in cui entrano le squadre della Premier (che, in quanto teste di serie, saltano un paio di turni di qualificazioni)
Comunque anch'io credo non cambi niente

[kalu]

Io l'ho risolto così (e credo sia il modo più semplice e immediato): nel torneo si giocano in totale $ 2^{n-1}+2^{n-2}+...+2^0=2^n-1 $ incontri, ovviamente tutti diversi (due squadre non si affrontano per due volte); invece il numero totale di incontri distinti che si possono giocare con $ 2^n $ squadre è $ \displaystyle\dbinom{2^n}{2}=\frac{2^n(2^n-1)}{2} $. Quindi la probabilità che un certo incontro si verifichi è $ \displaystyle\frac{2^n-1}{\frac{2^n(2^n-1)}{2}}=2^{-n+1} $.