Matematika pro poučení i pro zábavu

Úlohy pro zábavu i pro poučení

Patnáct časopisů na stole

Matematik zašel s přítelkyní do kavárny. Posadili se k jedinému volnému stolku, který však byl zcela pokrytý časopisy. Přítelkyně svého partnera již dobře znala, a tak ji nepřekvapilo, když poznamenal: "Těch časopisů je patnáct. Sedm z nich bychom mohli odstranit a zbývajících osm by stále ještě pokrývalo nejméně osm patnáctin desky stolku." Měl pravdu?

Řešení

Zlomkové části plochy desky stolku, kterou pokrývají jednotlivé časopisy, označíme $s_i$, $i=1,\dots,15$ a seřadíme je podle velikosti, takže $0\le s_1\le s_2\le \cdots \le s_{15}\le1$, a protože tyto části pokrývají celou desku stolku, platí $\sum_{i=1}^{15} s_i=1$. Platí $\sum_{i=1}^7 s_i\le 7s_8$ a $8s_8\le \sum_{i=8}^{15} s_i$, takže ${1\over7}\sum_{i=1}^7 s_i\le {1\over8}\sum_{i=8}^{15} s_i$ (dokázali jsme intuitivně zřejmou skutečnost, že aritmetický průměr souboru čísel není větší než aritmetický průměr jiného souboru čísel, z nichž každé není menší než největší číslo z prvního souboru). Můžeme tedy psát $8\sum_{i=1}^7 s_i\le 7 \sum_{i=8}^{15} s_i = (15-8)\sum_{i=8}^{15} s_i$, odkud plyne $15\sum_{i=8}^{15} s_i\ge 8\sum_{i=1}^{15} s_i=8$, tj. $\sum_{i=8}^{15}s_i \ge{8\over15}$.

Existuje také důkaz sporem založený na vtipné kombinatorické úvaze. Kdyby tvrzení neplatilo, znamenalo by to, že každá skupina osmi časopisů ležících na stole zakrývá méně než osm patnáctin plochy stolku. Z patnácti časopisů lze vybrat celkem $\binom{15}{8}$ skupin po osmi, kde $\binom nk={n!\over k!(n-k)!}$ je tzv. kombinační číslo vyjadřující počet různých skupin o $k$ prvcích, které lze sestavit z $n$ prvků. Součet velikostí ploch částí desky stolku zakrytých těmito skupinami časopisů je tedy menší než $\binom{15}{8}\cdot{8\over15}S$, kde $S$ je velikost plochy desky stolku. Každý časopis se vyskytuje v $\binom{14}{7}$ různých skupinách po osmi časopisech (vybraný časopis doplňujeme sedmi časopisy vybíranými ze zbývajících čtrnácti). Všech $\binom{14}{7}$ skupin osmi časopisů tedy pokryje plochu stolku nejméně $\binom{14}{7}$-krát. Dostáváme $\binom{14}{7}S<\binom{15}{8}S={15!\over7!8!}S={15\over8}\cdot{14!\over7!7!}S=\binom{14}{7}S$, což samozřejmě není není možné.