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ů.

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze