Průvodce IB000 Matematické základy informatiky
Kdo na sebe vidí a nevidí
Představte si skupinu dětí, jak se rozestaví na rovném přehledném hřišti tak, že žádní čtyři z nich nestojí v jedné přímce (tři však v jedné přímce stát mohou). Pak platí, že každé dvě děti A,B takové, že na úsečce z A do B nestojí jiné z dětí, na sebe vidí. Naopak pokud tři děti C,D,E v tomto pořadí stojí v jedné přímce, tak C nevidí na E (a naopak). Děti si v tomto pohledu modelujeme jako bezrozměrné body.
- Najděte rozestavení dětí na hřišti (jako body v rovině) takové, že žádné z dětí nevidí na všechny ostatní. Kolik nejméně musíte pozvat dětí, aby to takto vyšlo? Dokažte to.
- Najděte rozestavení dětí na hřišti (zase jako body v rovině) takové, že každé z dětí nevidí na alespoň dvě další z dětí. Opět zkuste najít co nejmenší počet dětí, se kterými toho dosáhnete, a dokazujte.
- Nakonec rozhodněte (a pak dokažte), zda takto můžeme postupovat dál a dál... Přesně, zda pro každé K existuje rozestavení dětí na hřišti takové, že každé z dětí nevidí na alespoň K dalších z dětí. Nebo zda naopak existuje konstanta C taková, že v každém rozestavení libovolného počtu N dětí na hřišti některé z nich vidí na alespoň N-C ostatních z dětí.
(Nezapomínejte, že žádné čtyři z dětí nesmí stát v jedné přímce.)