Počítání s většinou II.
Úloha číslo: 3743
Dvacet studentů psalo písemku, která měla čtyři úlohy. Pro každou dvojici studentů bychom v písemce našli úlohu, kterou oba vyřešili správně. Dokažte, že některou z úloh správně vyřešila více než polovina studentů.
Řešení
Předpokládejme pro spor, že každou úlohu vyřešilo nejvýše 10 studentů.
Dvěma způsoby odhadneme celkový počet úloh vyřešených dvojicemi studentů, neboli počet trojic \((s,t,u)\), znamenajících, že studenti \(s\) a \(t\) vyřešili úlohu \(u\).
\(\#(s,t,u)\ge\binom{20}{2}=190\), protože ke každou dvojici studentů \(s\) a \(t\) lze alespoň jednou z úloh doplnit na trojici.
\(\#(s,t,u)\le 4\cdot\binom{10}{2}=180\), protože každou ze čtyř úloh mohlo společně vyřešit nejvýše \(\binom{10}{2}\) dvojic studentů.
Porovnáním obou odhadů dostáváme \(190\le 180\). Z tohoto sporu plyne, že předpoklad neplatí a tedy existuje nějaká úloha vyřešená většinou studentů.
