Úloha 2.u1: Na plese (3 b)

Zadáno v čísle 24.2.

Řešeno v čísle 24.4.

Zadání

Na plese spolu tančilo 102 princů a 103 princezen. Po skončení plesu se zjistilo, že každý princ tančil se stejným počtem princezen. Dokažte, že existují dvě princezny, které si zatančily se stejným počtem princů.

Řešení

Úlohu budeme řešit sporem. Připusťme, že může nastat situace, kdy každá princezna tančí s jiným počtem princů a přitom každý princ tančí se stejným počtem princezen. Seřaďme si nyní vzestupně princezny podle počtu princů, s nimiž tančily. Protože máme 103 princezen a každá může tančit maximálně se 102 princi, tak jediná možnost, jak mohou princezny tančit s různým počtem princů, je, že 1. princezna netančí s nikým, 2. princezna tančí s 1 princem, 3. princezna se 2 princi, až nakonec 103. princezna tančí se 102 princi. Celkový počet tanečních párů tedy bude $0+1+2+\dots +102 = \frac{103\cdot 102}{2} = 103 \cdot 51$. Nyní se podívejme na prince – každý tančí s $n$ princeznami, tedy celkový počet tanečních párů je $102\cdot n$. Nyní si stačí všimnout, že $103\cdot 51$ není dělitelné 102 a máme spor, protože obě hodnoty vyjadřují počet tanečních párů. Proto musí existovat alespoň 2 princezny, které tančily se stejným počtem princů.

Téměř všichni, kteří tuto úlohu odeslali, se dobrali správného řešení. Dr.  Kateřina Rosická řešila úlohu pro obecný lichý počet princezen a o 1 méně princů. Doplňková otázka se proto téměř sama nabízí – jak je to v případě, že máme sudý počet princezen a princů o jednoho méně, než je princezen (například 4 princezny a 3 prince)? Umíte najít konstrukci, která umožní každé princezně tančit s jiným počtem princů, nebo taková konstrukce neexistuje? Pokud to správně vyřešíte a pošlete mi to1, tak u mě na soustředění máte čokoládu!

Petr


1) vincena.petr@gmail.com