TST 2002, problema 5.
Ad un torneo partecipano n>2 squadre. Alla fine, comunque scelte 3 squadre, almeno 2 di esse si sono affrontate in una partita. Quante partite sono state disputate come minimo?
Il torneo di Cortona 2002
C'è qualcosa che non mi torna.
Sicuramente non ci possono essere meno partite di quante dici tu, ma non hai esibito una configurazione valida: a me viene un risultato diverso.
Prendiamo un grafo che ha $ n $ vertici e (ciascuno dei quali corrisponde ad una squadra) e stabiliamo che 2 vertici sono collegati sse le squadre corrispondenti non si sono affrontate.
Supponiamo $ n $ pari.
Per il teorema di Mantel (si dimostra facilmente, se qualcuno non trova la dimostrazione lo dica che la posto) questo grafo ha al massimo $ \frac{n^2}{4} $ archi. Una configurazione con $ \frac{n^2}{4} $ archi esiste. Prendiamo un grafo bipartito completo $ \frac{n}{2},\frac{n}{2} $
Abbiamo che esso ha esattamente $ \frac{n^2}{4} $ archi.
Quindi consideriamo il grafo "complementare" a questo, ovvero quello delle partite giocate. Esso dunque ha come minimo $ {n\choose {2}} - \frac{n^2}{4}=\frac{n(n-2)}{4} $ archi.
Supponiamo $ n $ dispari.
Allora il grafo delle partite non giocate ha al massimo $ \frac{n^2-1}{4} $ archi. Una configurazione con $ \frac{n^2-1}{4} $ archi esiste. Prendiamo un grafo bipartito completo $ \frac{n+1}{2},\frac{n-1}{2} $
Abbiamo che esso ha esattamente $ \frac{n^2-1}{4} $ archi.
Quindi consideriamo il grafo "complementare" a questo, ovvero quello delle partite giocate. Esso dunque ha come minimo $ {n\choose {2}} - \frac{n^2-1}{4}=\frac{(n-1)^2}{4} $ archi.
Quindi il minimo numero di partite giocate è $ \lfloor \frac{n^2-2n+1}{4} \rfloor $
Sicuramente non ci possono essere meno partite di quante dici tu, ma non hai esibito una configurazione valida: a me viene un risultato diverso.
Prendiamo un grafo che ha $ n $ vertici e (ciascuno dei quali corrisponde ad una squadra) e stabiliamo che 2 vertici sono collegati sse le squadre corrispondenti non si sono affrontate.
Supponiamo $ n $ pari.
Per il teorema di Mantel (si dimostra facilmente, se qualcuno non trova la dimostrazione lo dica che la posto) questo grafo ha al massimo $ \frac{n^2}{4} $ archi. Una configurazione con $ \frac{n^2}{4} $ archi esiste. Prendiamo un grafo bipartito completo $ \frac{n}{2},\frac{n}{2} $
Abbiamo che esso ha esattamente $ \frac{n^2}{4} $ archi.
Quindi consideriamo il grafo "complementare" a questo, ovvero quello delle partite giocate. Esso dunque ha come minimo $ {n\choose {2}} - \frac{n^2}{4}=\frac{n(n-2)}{4} $ archi.
Supponiamo $ n $ dispari.
Allora il grafo delle partite non giocate ha al massimo $ \frac{n^2-1}{4} $ archi. Una configurazione con $ \frac{n^2-1}{4} $ archi esiste. Prendiamo un grafo bipartito completo $ \frac{n+1}{2},\frac{n-1}{2} $
Abbiamo che esso ha esattamente $ \frac{n^2-1}{4} $ archi.
Quindi consideriamo il grafo "complementare" a questo, ovvero quello delle partite giocate. Esso dunque ha come minimo $ {n\choose {2}} - \frac{n^2-1}{4}=\frac{(n-1)^2}{4} $ archi.
Quindi il minimo numero di partite giocate è $ \lfloor \frac{n^2-2n+1}{4} \rfloor $
"Sei la Barbara della situazione!" (Tap)