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$.
Kombinatorikk
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
pit
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.
[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.