IMO 1998 - Kombinatoryka

Question

Próbuję tego problemu IMO Combinatorics $1998$ P2, który wygląda tak:

W konkursie są $m$ zawodnicy i $n$ sędziowie, gdzie $n \geq 3$jest nieparzystą liczbą całkowitą. Każdy sędzia ocenia każdego zawodnika jako „zdał” lub „przegrał”. Przypuszczać$k$ to liczba taka, że ​​dla dowolnych dwóch sędziów ich oceny pokrywają się co najwyżej $k$zawodnicy. Udowodnij to$$\frac{k}{m}\geq \frac{n-1}{2n}$$

Jestem kompletnie zdziwiony, jak zacząć, czy możesz mi dać jakieś wskazówki?

Answer 1

Rozważ liczbę kombinacji $(\{j_1, j_2\},c)$, gdzie $\{j_1, j_2\}$ to para różnych sędziów, i $c$jest zawodnikiem, na którego się zgadzają. Możesz osiągnąć tę liczbę na dwa sposoby:

1. Suma nad zawodnikami, liczba par sędziów, którzy się na to zgadzają.

2. Suma na parach sędziów, liczbie zawodników, których zgadzają się.

Wówczas ilość sumowana w 1. może być ograniczona poniżej wyrażeniem obejmującym $n$ (Zapamiętaj $n$ jest nieparzysta), podczas gdy ilość sumowana w 2. może być ograniczona powyżej $k$. Łączenie daje pożądaną nierówność.