Počítání s většinou I.
Úloha číslo: 3742
Při zápočtové písemce každý student vyřešil aspoň třetinu všech úloh, a navíc alespoň polovina studentů vyřešila aspoň dvě třetiny úloh. Ukažte, že v písemce existuje úloha, kterou vyřešila alespoň polovina studentů.
Nápověda
Existenci dokazujte sporem.
Řešení
Předpokládejme pro spor, že každou úlohu vyřešilo měně než polovina studentů.
Označme si \(n\) počet studentů a \(m\) počet úloh.
Dvěma způsoby odhadneme celkový počet úloh vyřešených všemi studenty, neboli počet dvojic \((s,u)\), znamenajících, že student \(s\) vyřešil úlohu \(u\).
\(\#(s,u)<m\cdot\frac{n}{2}\), protože každou z \(m\) úloh vyřešilo méně než \(\frac{n}{2}\) studentů.
\(\#(s,u)\ge n\cdot\frac{m}{3} + \frac{n}{2}\cdot \frac{m}{3}\), protože každý z \(n\) studentů vyřešil alespoň \(\frac{m}{3}\) úloh a k tomu \(\frac{n}{2}\) studentů vyřešila ještě třetinu zadaných úloh navíc.
Porovnáním obou odhadů dostáváme \(\frac{mn}{2}<\frac{mn}{2}\). Z tohoto sporu plyne, že předpoklad neplatí a tedy existuje nějaká úloha vyřešená většinou studentů.