IMO Shortlist 2010 C5 [L06]

[Stef2008]

Mi sono imbattutto in questo problema. L'ho trovato interessante. Magari qualcuno può provare a farlo. Lascio anche qualche piccolo hint dopo il testo.

n ≥4 giocatori hanno partecipato a un torneo di tennis. Due giocatori qualsiasi hanno giocato esattamente una partita e non c'è stata alcuna partita in pareggio. Noi diciamo che
una quaterna di quattro giocatori è cattiva se un giocatore viene sconfitto da altri tre giocatori, e questi tre giocatori formavano una terna ciclica (un insieme (A, B, C) tale che A batte B, B batte C e C batte A). Supponiamo che non ci sono quaterne cattive in questo torneo. Siano [tex]w_i[/tex] e [tex]l_i [/tex] rispettivamente il numero di vittorie e sconfitte dell'i-esimo giocatore. Dimostrare che:
[tex]\sum_{i=1}^{n}(w_i-l_i)^3 \geq 0[/tex]


Hint 1

Testo nascosto:

Rappresanta il problema come grafo orientato e usa il double counting

Hint 2

Testo nascosto:

La tesi viene provata se dimostri: [tex]\sum_{i=1}^{n}(w_i^3-l_i^3) \geq 0[/tex] e [tex]\sum_{i=1}^{n}(w_il_i^2-l_iw_i^2) \geq 0[/tex]

Hint 3

Testo nascosto:

Usa i seguenti lemmi:
[tex]\sum_{i=1}^{n}w_i=\sum_{i=1}^{n}l_i[/tex]
[tex]\sum_{i=1}^{n}w_i^2= \sum_{i=1}^{n}l_i^2[/tex]