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.

  1. 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.
  2. 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.
  3. 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.)

Při rozdělování bonusových bodů se bude hledět především na to, nakolik bude váš matematický výkon vyčnívat na výkony ostatních studentů řešících tento úkol. Tento úkol nemusíte řešit jen čistě teoreticky na papíře, ale můžete si pomoci počítačem v chytrém prohledávání všech "malých" možností. Případně můžete zkusit spojit ruční práci s vhodným pomocným počítačovým programem, třeba GeoGebra.