matematikk.net

I en turnering med $n$ deltagere spilte hvert par av deltagere mot hverandre nøyaktig én gang (ingen kamp endte uavgjort). La $j,k$ være (ikkenegative) heltall mindre enn $n$ slik at
\[ j<1+\frac{ n\binom{\frac{n-1}{2}}{k}}{\binom{n}{k} } .\]
Vis at det eksisterer mengder $A$ og $B$ med henholdsvis $k$ og $j$ deltagere, slik at hver deltager i $A$ slo alle deltagerne i $B$.

Skriver opp noe muligens vrøvl, i håp mot å få svar fra tråd starter

[tex]j<1+\frac{ n\binom{\frac{n-1}{2}}{k}}{\binom{n}{k} } <=> (j-1)\binom{n}{k} < n\binom{\frac{n-1}{2}}{k}[/tex]

Se på mengden av unike kanter i [tex]K_n[/tex], hvilket
har [tex]\frac{n-1}{2}[/tex] unike kanter i gjennomsnitt per node. Det er n muligheter for feste av kant til node.
Dvs det er n mulige vinnere for k tapere, hvis en vilkårlig person kjempet og vant mot k personer.

Dette gir klart mindre antall kombinasjoner for tap, da en kamp mellom en
vilkårlig i A bortsatt fra en person som vinner mot hele B gir klart mindre kamper enn at en vilkårlig i [tex]A \cup B[/tex] vinner
mot k tilfeldige av sine konkurrenter.

Jeg kan ihvertfall gi et hint:

La $M$ være en (under)mengde med $k$ deltagere, og definér $f(M)$ som det maksimale antallet spillere utenfor $M$, slik at alle disse ble slått av alle deltagerne i $M$.