OliForum Matematico

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?

Ad ogni sottoinsieme di tre elementi è associata almeno una partita. I sottoinsiemi di 3 elementi sono $ n\choose 3 $ . Considerata la partita fra a e b, essa sarà associata agli insiemi del tipo $ \{a,b,x\} $, che sono $ n-2 $.
Il numero minimo di partite è $ \frac{n(n-1)}{3!} $

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 $