IMO 1998 - Combinatoria

Question

Sto provando questo problema combinatorio IMO$1998$P2 che fa così:

In una competizione, ci sono$m$concorrenti e$n$giudici, dove$n \geq 3$è un numero intero dispari. Ogni giudice valuta ogni concorrente come "superato" o "fallito". Supponiamo$k$è un numero tale che, per due giudici qualsiasi, le loro valutazioni coincidono al massimo$k$concorrenti. Prova che$$\frac{k}{m}\geq \frac{n-1}{2n}$$

Sono completamente perplesso su come iniziare, potresti darmi qualche suggerimento?

Answer 1

Considera il numero di combinazioni$(\{j_1, j_2\},c)$, dove$\{j_1, j_2\}$è una coppia di giudici distinti, e$c$è un concorrente su cui sono d'accordo. Puoi arrivare a questa quantità in due modi:

1. Somma sui concorrenti, il numero di coppie di giudici che sono d'accordo su di loro.

2. Somma su coppie di giudici, il numero di concorrenti su cui concordano.

Quindi la quantità che viene sommata in 1. può essere delimitata in basso da un'espressione che coinvolge$n$(ricordare$n$è dispari), mentre la quantità che viene sommata in 2. può essere delimitata sopra da$k$. La combinazione produce la disuguaglianza desiderata.