Zadanie: Na večierku žiadny chlapec netancoval s každou dievčinou, ale každé dievča tancovalo aspoň s jedným chlapcom. Dokážte, že existujú také dva páry a , ktoré spolu tancovali, a pritom netancoval s a netancoval s . Vieme pritom, že na večierku sa zúčastnili aspoň dve dievčatá a aspoň dvaja chlapci.

meno: e-mail:

[cituj]mišof napísal: Mňa napadlo takéto: Ako dievča $D$ zoberme (hociktoré) dievča, ktoré malo spomedzi všetkých dievčat najmenej tanečníkov. (A počet jej tanečníkov označme $t$.) Hociktorého jedného z nich nazveme $C$. Teraz keďže $C$ netancoval so všetkými dievčatami, existuje dievča $D'$, s ktorým netancoval. No a ostáva už len ukázať, že teraz existuje vyhovujúci $C'$ -- teda chlapec, ktorý tancoval s $D'$ a zároveň netancoval s $D$. Teraz sa nám vyplatí, že sme si šikovne zvolili $D$: - Dievča $D$ má medzi chlapcami inými ako $C$ len $t-1$ tanečníkov -- lebo dokopy ich má $t$, ale $C$ je jeden z nich. - Dievča $D'$ ich má aspoň $t$ -- lebo každé dievča malo aspoň $t$ tanečníkov a $D'$ s $C$ netancovala. Preto určite existuje chlapec, ktorý tancoval s $D'$ ale nie s $D$. Toho nazveme $C'$ a vyhrali sme.[/cituj]

V príspevku je na písanie matematických výrazov možné používať príkazy TeXu. Help k ich používaniu nájdete na kms.sk/tex.php.