[Kombinatoryka] Kombinatoryka z Hong Kongu 94'
: 22 sty 2010, o 22:55
Zadanie z jakiegoś konkursu w Hong Kongu z 94':
W turnieju tenisowym udział bierze 10 zawodników, każda para uczestników gra ze sobą jeden raz.
TRÓJKĄTEM będziemy nazywać trójkę uczestników: A, B, C, takich, że A wygrał z B, B wygrał z C, C wygrał z A.
Niech ponadto \(\displaystyle{ W_i}\) oznacza ilość gier wygranych przez i-tego zawodnika, \(\displaystyle{ L_i}\)- ilość gier przegranych.
Wiemy, że jeżeli i-ty zawodnik wygrał z j-tym, to \(\displaystyle{ L_i+W_j \ge 8}\).
Udowodnij, że w turnieju wystąpiło DOKŁADNIE 40 trójkątów.
Doszedłem do kilku nierówności, np. dla wszystkich zawodników powinno zachodzić \(\displaystyle{ 3 \le W_i \le 6}\), ale to chyba tylko bardziej gmatwa zadanie. Więc jak, pomożecie
?
W turnieju tenisowym udział bierze 10 zawodników, każda para uczestników gra ze sobą jeden raz.
TRÓJKĄTEM będziemy nazywać trójkę uczestników: A, B, C, takich, że A wygrał z B, B wygrał z C, C wygrał z A.
Niech ponadto \(\displaystyle{ W_i}\) oznacza ilość gier wygranych przez i-tego zawodnika, \(\displaystyle{ L_i}\)- ilość gier przegranych.
Wiemy, że jeżeli i-ty zawodnik wygrał z j-tym, to \(\displaystyle{ L_i+W_j \ge 8}\).
Udowodnij, że w turnieju wystąpiło DOKŁADNIE 40 trójkątów.
Doszedłem do kilku nierówności, np. dla wszystkich zawodników powinno zachodzić \(\displaystyle{ 3 \le W_i \le 6}\), ale to chyba tylko bardziej gmatwa zadanie. Więc jak, pomożecie
?